Vaje 31.3.2022 Bellman Ford, A*
Completion requirements
Opened: Thursday, 31 March 2022, 12:00 AM
Due: Thursday, 7 April 2022, 12: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.