„Algoritmuselmélet - ZH, 2013.04.03.” változatai közötti eltérés
| 67. sor: | 67. sor: | ||
}} | }} | ||
===4. Feladat=== | ===4. Feladat (Van megoldás)=== | ||
Adjacencia-mátrixával adott <math>n</math> csúcsú, irányított gráfként ismerjük egy város úthálózatát. El szeretnék jutni <math>A</math> pontból <math>B</math> pontba, de sajnos minden csomóponthoz várnunk kell a nagy hóesés miatt, a várakozás hossza minden csomópontra ismert és független attól, hogy merre akarunk továbbmenni. Adjon algoritmust, ami <math>O(n^2)</math> lépésben eldönti, hogy merre menjünk, hogy a lehető legkevesebbet kelljen várni összességében. ''(A csomópontok közötti utak hosszának megtétele a várakozáshoz képest elhanyagolható időbe telik, tekintsük 0-nak. <math>A</math>-ban és <math>B</math>-ben nem kell várakozni.)'' | |||
{{Rejtett | {{Rejtett | ||
|mutatott=<big>'''Megoldás'''</big> | |mutatott=<big>'''Megoldás'''</big> | ||
|szöveg= | |szöveg= | ||
*A "probléma", hogy a csúcsoknak van súlya (ill. az éleknek is van, de az 0), amivel nem igen tudunk mit kezdeni. De nem hiába volt BSZ1 (vagy BSZ2?), ahol megtanultuk, hogy könnyedén csinálhatunk a csúcssúlyból élsúlyt. | |||
*Az adott pontot (X) lecseréljük 2 pontra (X1, X2). Ami eddig X-be ment, az menjen X1-be, és ami X-ből ment, az menjen X2-ből. ''(Vagyis X1-ből csak X2-be megy él, és X2-be csak az X1 megy.)'' | |||
*A 2 pontot összekötjük, a köztük menő élsúly pedig az X pont súlya lesz. | |||
*Csináljuk hát ezt ezzel a gráffal: | |||
**Az eredeti <math> n </math> csúcsú G gráfból csinálunk így egy F gráfot, melyben <math> 2n </math> csúcs lesz ''(és az élszám is n-nel nő, de ez most minket annyira nem izgat)''. | |||
**Ebben az F gráfban kell megtalálni a legrövidebb utat egy "X2"-ből egy "Y1"-be. | |||
**A Dijkstra-algoritmus <math> O(n^2) </math> lépésben keres legrövidebb utat, ebben az esetben <math> O((2n)^2)=4O(n^2)=O(n^2)</math>. | |||
*Így a feladat ezzel meg is oldva. | |||
::::::::::[[File:csucs_suly.png|300px|G gráf]][[File:el_suly.png|400px|F gráf]] | |||
}} | }} | ||