VIK Wiki

„Algoritmuselmélet - Vizsga, 2013.05.30.” változatai közötti eltérés

← Régebbi szerkesztésÚjabb szerkesztés →
Vizuális
Arklur (vitalap | szerkesztései)
381 szerkesztés
Arklur (vitalap | szerkesztései)
381 szerkesztés
75. sor: 75. sor:
}}
}}


===6. Feladat (Van megoldás)===
===6. Feladat===
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
81. sor: 81. sor:
|szöveg=
|szöveg=


*Az élek súlya legyen a "Veszteség" = Fenntartás - Bevétel (Így a súly minél kisebb, annál nagyobb a Profitunk). Ezt <math>O(n^2)</math> időben el tudjuk végezni.
TODO
*Az így kapott G gráfra futtassunk egy Prim-algoritmust, ami <math>O(n^2)</math> időben keres nekünk egy minimális feszítőfát, ez legyen F. Ez azért jó, mert így bármelyik szigetről bármelyik szigetre eltudunk jutni a lehető legnagyobb profittal bíró útvonalakon.
*Mivel a cél a profitmaximalizálás, így minden olyan élt, aminek nem pozitív a súlya (tehát profitot termel, vagy legalábbis nincs rajta veszteségünk), felvesszük a F gráfhoz, ez legyen az M gráf. Ez is <math>O(n^2)</math> időt vesz igénybe.
*Az M gráfról elmondhatjuk, hogy bármelyik szigetről bármelyik szigetre el tudunk jutni, és a hajóhálózat a legnagyobb profittal rendelkezik.
*Tulajdonképpen <math>3*O(n^2)</math> időt igényel az algoritmus, ami összességben még mindig <math>O(n^2)</math>, tehát az algoritmus jó.
}}
}}


A lap eredeti címe: „https://vik.wiki/Algoritmuselmélet_-_Vizsga,_2013.05.30.”