Vaje 31.3.2022 Bellman Ford, A*
Odprto: četrtek, 31 marec 2022, 00:00 AM
Rok za oddajo: četrtek, 7 april 2022, 00:00 AM
1) Ponovitev Bellman Fordovega algoritma. Kaj sprejme kot vhod, kaj izračuna, predpostavke, ideja algoritma.
2) Kaj je A*? Kako izgleda "tipična" implementacija?
2.1 Recimo, da imamo graf v obliki mreže z ovirami. Navedi primer hevristike. Kje bi še lahko uporabili tako hevristiko?
2.2 Recimo, da imamo graf, kjer so vozlišča mest (vasi, kraji, križišča..) in povezave ceste med njimi. Vsaka povezava e ima utež w(e), ki predstavlja razdaljo oz. pot potovanja po tej povezavi. Poleg tega ima vsaka povezava e še "ocenjen čas zastojev" w'(e, t), kjer t predstavlja trenutni čas. Ocenjen čas zastojev je tako odvisen od časa. Želimo čim hitreje dobiti odgovore na poizvedbe oblike: Kako najhitreje priti iz mesta A do mesta B.
Ideja: S predprocesiranjem skonsktuirajte ustrezno hevristiko za A* algoritem.
V poročilo vključite zgornje naloge ter tudi, kar je zahtevano iz Tekmovanja 31.3.2022.
2) Kaj je A*? Kako izgleda "tipična" implementacija?
2.1 Recimo, da imamo graf v obliki mreže z ovirami. Navedi primer hevristike. Kje bi še lahko uporabili tako hevristiko?
2.2 Recimo, da imamo graf, kjer so vozlišča mest (vasi, kraji, križišča..) in povezave ceste med njimi. Vsaka povezava e ima utež w(e), ki predstavlja razdaljo oz. pot potovanja po tej povezavi. Poleg tega ima vsaka povezava e še "ocenjen čas zastojev" w'(e, t), kjer t predstavlja trenutni čas. Ocenjen čas zastojev je tako odvisen od časa. Želimo čim hitreje dobiti odgovore na poizvedbe oblike: Kako najhitreje priti iz mesta A do mesta B.
Ideja: S predprocesiranjem skonsktuirajte ustrezno hevristiko za A* algoritem.
V poročilo vključite zgornje naloge ter tudi, kar je zahtevano iz Tekmovanja 31.3.2022.