VIZITAŢI GORJUL DE SUB MUNTE !!

De Alex, Elisa, George şi Patricia

CUM PUTEM FOLOSI GRAFURILE ÎN VIAŢA DE ZI CU ZI?

Reprezentăm grupa „Pasionaților de călătorii” și vom fi ghizi pentru grupul de elevi și profesori de la un liceu din Franța cu care liceul nostru este în parteneriat.

Grupul din Franța va fi cazat la internatul liceului nostru pentru 3 zile și dorește să viziteze toate locurile interesante din zona Novaci-Rânca.

Obiectivele turistice şi instituţiile pot reprezenta vârfurile sau nodurile unui graf, iar drumurile ce le leagă vor fi muchiile sau arcele. Cum în zonă nu există străzi cu sens unic, graful va fi neorientat, chiar dacă am străbate traseul pe jos sau cu un mijloc de transport.

Pentru început, am construit o „hartă” a principalelor instituții și obiective turistice din zonă și a legăturilor dintre acestea.

Am făcut măsurători aproximative ale distanțelor și am încercat să nu omitem străduțele mai mici.

Ceea ce a rezultat, nu este altceva decât un graf neorientat:

S P

Pociovaliștea

Liceul Novaci

PolițiaSpitalul

Primăria

Biserica Monument istoric

Biserica

Peștera Muierii Baia de Fier

Mânăstirea Polovragi

Peștera Polovragi

Spre

Ho

rezu

Spre Tg-Jiu

Stațiunea Rânca

Spre Tg-Jiu

Centrul Orașului

Cernădia

Siteşti

Bumbeşti

Poenari

Polovragi

Spre Bumbeşti-Jiu

3000 m

1300 m

200 m

200 m

200 m

150 m

200 m

200

m200

m200

m200

m

1000 m

30000 m

1600 m

300 m

6000

m

3000

m

6000 m

3200 m

7000 m

100 m

600 m2000 m

200 m

2500 m

200 m

300 m

15000

m

1500

m

3500

m

3000 m9000 m

DE CE ÎNVĂŢĂM NOŢIUNI DE TEORIA GRAFURILOR? CUM PUTEM MODELA O SITUAŢIE PRACTICĂ FAMILIARĂ ELEVILOR ÎN TERMENII TEORIEI GRAFURILOR?CUM FOLOSIM UN LIMBAJ DE PROGRAMARE PENTRU A MODELA GRAFURILE?

Răspunsurile la aceste întrebări le-am descoperit atunci când ni s-a propus să stabilim un orar al excursiilor pe care grupul de turişti îl vor efectua în cele 3 zile, cu respectarea anumitor condiţii pentru traseele stabilite.

ZIUA 1: FAMILIARIZAREA CU ORAŞUL. Condiţii: Se pleacă de la liceu şi trebuie vizitate toate obiectivele,

fiecare o singură dată. Distanţa dintre fiecare două obiective poate fi parcursă numai într-un singur sens, pe care noi îl stabilim dinainte.

ZIUA 2: EXCURSIE: NOVACI – BAIA DE FIER – POLOVRAGI ŞI RETUR. Condiţii: Vizitarea fiecărui obiectiv o singură dată. ZIUA 3: NOVACI – RÂNCA Condiţii:Cel mai scurt traseu.

ORARUL IMPUS

Am simplificat puţin graful, am notat vârfurile cu cifre sau litere, am considerat că distanţa dintre două vârfuri reprezintă costul muchiei ce le uneşte, apoi am construi un fişier în care am salvat muchiile şi costul asociat.

Am scris o procedură care citeşte muchiile din fişier şi construieşte matricea costurilor asociată grafului.

S19

7

4

5

H

A

E

K J

I

R

ML

N

P

O

3000 m

1300 m

200 m

200 m

200 m

150 m

200 m

200

m200

m200

m200

m

1000 m

30000 m

1600 m

300 m

6000

m

3000

m

6000 m

3200 m

7000 m

100 m

600 m2000 m

200 m

2500 m

200 m

300 m

15000

m

1500

m

3500

m

3000 m9000 m

23

68

BC

DFG

ZIUA 1: FAMILIARIZAREA CU ORAŞUL. Condiţii: Se pleacă de la liceu şi trebuie vizitate toate obiectivele, fiecare o singură dată.

Distanţa dintre fiecare două obiective poate fi parcursă numai într-un singur sens, pe care noi îl stabilim dinainte.

Am înţeles că ceea ce trebuia să determinăm nu era altceva decât un graf turneu al unui subgraf din graful iniţial. De fapt, trebuia să construim un ciclu elementar care să conţină toate nodurile cerute.

Ne-am propus să nu folosim metoda backtracking . De altfel, cu backtracking s-ar genera toate traseele posibile, ori noi trebuie să găsim un singur traseu, deci utilizarea acestei tehnici nu este neapărat necesară.

Memorăm drumul într-un vector de noduri, în ordinea în care urmează a fi “vizitate”. Introducem iniţial în vector nodul cu numărul 1. În continuare, pentru fiecare din celelalte noduri încercăm să găsim poziţia pe care o va avea în cadrul drumului (în vector). Fiecare nod k se va adăuga fie în interior, fie la sfârşit, aşa încât vectorul să păstreze statutul de drum, ca în exemplu:

Se adaugă iniţial vârful 1: Vârful 2 se adaugă la sfârşit, pentru că există muchia (1,2): Vârful 3 se adaugă la sfârşit, pentru că nu există muchia (1,3), dar există (2,3): Din aceleaşi motive, vârfurile 4 şi 7 se adaugă la sfârşit: Vârfurile 5 şi 6 se adaugă în interior, după vârful 2, pentru că există muchia (2,5):

şi, în final:

1-Liceu – 2 – 5-Poliţie – 6 – 3 – 4-Primărie – 7-Spital – 8 – A-Biserica Monument – B – C – 9-Centrul – H-Biserica – R – S – 1-Liceu

11 2

1 2 31 2 3 4

1 2 5 3 46

1 2 5 6 3 4 7 8 A B C 9 H R S

7

S19

7

4

5

H

A

E

K J

I

R

ML

N

P

O

30000 m

1600 m

6000

m

3000

m

6000 m

3200 m

7000 m

100 m

600 m2000 m

2500 m

200 m

300 m

15000

m

3500

m

3000 m9000 m

23

68

BC

DFG

ZIUA 2: EXCURSIE: NOVACI – BAIA DE FIER – POLOVRAGI ŞI RETUR. Condiţii: Vizitarea fiecărui obiectiv o singură dată. Am înţeles că trebuie să determinăm cel mai scurt ciclu elementar care să pornească şi să revină în

vârful 1. Am folosit metoda backtracking pentru a determina toate ciclurile elementare care pleacă din vârful 1

şi am păstrat soluţia care a determinat cel mai scurt astfel de ciclu. Astfel, într-o stivă, iniţial vidă, am introdus vârful de pornire, 1. Pe fiecare din următoarele niveluri, am

introdus unul dintre celelalte noduri care nu au mai fost adăugate, aşa încât să existe muchie între nodul aflat pe nivelul k-1 şi nodul nou introdus. Dacă pe un nivel nu mai există noduri pe care să le putem introduce, dar nu am obţinut o soluţie, atunci coborâm pe nivelul anterior şi căutăm un alt nod care îndeplineşte condiţiile de continuare. Dacă am obţinut o soluţie atunci o tipărim. De asemenea, pentru fiecare soluţie, calculăm distanţa care ar trebui parcursă pentru a putea determina distanţa minimă dintre toate soluţiile găsite.

Pe nivelul 1, am introdus 1. Pe nivelul 2 am introdus 2, pentru că există muchia (1,2). Pe nivelul 3, am introdus următorul vârf “nevizitat” 3 care face muchie cu vârful de pe nivelul anterior. Analog pentru nivelul 4. Pe nivelul 5 încercăm să introducem vârful 5, care nu există pe un alt nivel, dar cum nu există muchia (4,5), nu e posibil. Analog pentru vârful 6. Vârful 7 se poate adăuga pe nivelul 5, pentru că nu a mai fost introdus şi există muchia (4,7). Pe nivelurile 6 şi 7 se pot adăuga vârfurile 8 şi 9 care îndeplinesc condiţiile de continuitate. Se procedează asemănător pentru celelalte niveluri şi celelalte vârfuri, ţinându-se cont că este obligatorie introducerea la un moment dat în stivă a vârfurilor J, I, M şi că vom obţine o soluţie dacă există muchie între un

vârf introdus pe un nivel superior şi vârful aflat pe nivelul 1, adică 1. Astfel se generează toate soluţiile posibile dintre care am păstrat-o pe cea cu lungimea cea mai mică.1 1

21234

12347

1234789

S19

7

4

5

H

A

E

K J

I

R

ML

N

P

O

3000 m

1300 m

200 m

200 m

200 m

150 m

200 m

200

m200

m200

m200

m

1000 m

30000 m

1600 m

300 m

6000

m30

00

m6000 m

3200 m

7000 m

100 m

600 m2000 m

2500 m

200 m

300 m

15000

m

1500

m

3500

m

3000 m9000 m

23

68

BC

DFG

ZIUA 3: NOVACI – RÂNCA Condiţii:Cel mai scurt traseu. Am folosit algoritmul lui Dijkstra pentru a determina cel mai scurt traseu de la nodul 1 la nodul

E. Algoritmul selectează nodurile grafului, unul câte unul, în ordinea crescătoare a costului

drumului de la nodul 1 la ele, într-o mulţime S, care iniţial conţine numai nodul 1. În prelucrare, am folosit 3 vectori: D, S şi T:

Vectorul D este vectorul lungimii drumurilor de la nodul 1 la celelalte noduri ale grafului, fiecare D[i] reprezentând lungimea drumului de la nodul 1 la nodul i.

Vectorul T indică drumurile găsite între nodul 1 şi celelalte noduri ale grafului. Vectorul S, indică mulţimea nodurilor selectate: S[i]=0 dacă nodul i este neselectat şi 1 dacă i

este selectat. De exemplu, pentru graful nostru, câteva dintre valorile iniţiale ale lui S, D, T sunt: D . . . S . . . T . . . Cel mai apropiat nod de 1 este nodul 2. Se selectează succesiv celelalte noduri, transformându-se vectorii iniţiali: D[3]=∞>D[2]+a[2,3]=200+100=300, D[3]=300, T[3]=2 D[4]=∞>D[3]+a[3,4]=300+100=400, T[4]=3 etc. Se transformă pas cu pas vectorii D, S şi T, obţinându-se drumul cel mai

scurt de la nodul 1 la nodul E: 1, 2, 3, 4, 9, C, D, E.

0 200 ∞ ∞ 3000∞1 0 0 0 0 00 1 0 0 0 1

S19

7

4

5

H

A

E

K J

I

R

ML

N

P

O

3000 m

1300 m

200 m

200 m

200 m

150 m

200 m

200

m200

m200

m200

m

1000 m

30000 m

1600 m

300 m

6000

m30

00

m6000 m

3200 m

7000 m

100 m

600 m2000 m

2500 m

200 m

300 m

15000

m

1500

m

3500

m

3000 m9000 m

23

68

BC

DFG

BIBLIOGRAFIE Manual Informatică pentru clasa a XI-

a,Editura L&S, autor Tudor Sorin. Informatica pentru liceu şi bacalaureat,

materia de clasa a XI-a, autori George Daniel Mateescu, Pavel Florin Moraru.

http://portalnovaciranca.ro