„Algoritmuselmélet - Vizsga, 2013.05.30.” változatai közötti eltérés
| 95. sor: | 95. sor: | ||
}} | }} | ||
===6. Feladat=== | ===6. Feladat (Van megoldás)=== | ||
Egy ország ''n'' kis szigetből áll. Szeretnénk néhány hajójáratot indítani a szigetek között úgy, hogy bárhonnan bárhova el lehessen jutni (esetleg átszállással). Ehhez ismerjük bármely két szigetre, hogy mennyibe kerül egy évben a hajójárat fenntartása közöttük, illetve azt, hogy mekkora az itt várható éves bevétel. Adjon algoritmust, ami ezen adatok ismeretében <math>O(n^2)</math> időben meghatározza, hogy hol indítsuk el a hajójáratokat, ha a lehető legnagyobb várható éves hasznot (vagy a lehető legkisebb veszteséget) szeretnénk elérni. (Egy szigeten egy hajóállomás van csak). | Egy ország ''n'' kis szigetből áll. Szeretnénk néhány hajójáratot indítani a szigetek között úgy, hogy bárhonnan bárhova el lehessen jutni (esetleg átszállással). Ehhez ismerjük bármely két szigetre, hogy mennyibe kerül egy évben a hajójárat fenntartása közöttük, illetve azt, hogy mekkora az itt várható éves bevétel. Adjon algoritmust, ami ezen adatok ismeretében <math>O(n^2)</math> időben meghatározza, hogy hol indítsuk el a hajójáratokat, ha a lehető legnagyobb várható éves hasznot (vagy a lehető legkisebb veszteséget) szeretnénk elérni. (Egy szigeten egy hajóállomás van csak). | ||
{{Rejtett | {{Rejtett | ||
| 101. sor: | 101. sor: | ||
|szöveg= | |szöveg= | ||
*Első lépésben az élsúly legyen a <math> Profit = -(Bevetel - Kiadas) .</math> | |||
*Vegyük fel az összes profitot termelő, vagy legalábbis veszteséget nem termelő éleket <math> (Profit \geq 0 )</math> <math> \Rightarrow O(n^2) </math> lépés. Ez legyen mondjuk a G gráf. | |||
*Két eshetőség áll fenn: | |||
**Ha a G gráf összefüggő, akkor jók is vagyunk, nincs további teendőnk, meg is vagyunk. | |||
**Ha nem összefüggő, akkor: | |||
***Az egyes komponenseket tekintsük egy pontnak. Minden olyan él, ami ebbe a komponensbe megy, menjen ebbe a pontba. Így kapunk egy F gráfot. | |||
***Erre az F gráfra hívunk meg egy Prim-algoritmust, ami <math> O(n^2) </math> időben keres az F gráfban egy minimális feszítőfát ''(vagyis a komponenseket - ami most jelenleg 1-1 pont a gráfban - a lehető legkisebb költségű élekkel köti össze)''. | |||
*Tehát Prim-algoritmussal, vagy anélkül <math> O(n^2) </math> időben megmondjuk, hogy mely hajójáratok indításával lesz az évi bevétel a legmagasabb. | |||
}} | }} | ||