AI TD2 - Shortest Path Algorithms

《AI TD2 - Shortest Path Algorithms》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、TD2:ShortestpathalgorithmsExercice1a.UsetheDijkstra’salgorithmtofindtheshortestpathfromnodeStonodeG.A20km50kmS10kmGBC10km50km10kmExercise2FivecitiesnamedA,B,C,DandEarelinkedbyroadsaccordingtothefollowingtable.Forexample,thedistancebetweencitiesBandDis5km.Inthetable,minus(-)me

2、ansthatthereisnoroadbetweenthecities,itisforexamplenotpossibletoreachdirectlyEfromAandvice-versa.CityECityDCityCCityBCityA--19km12kmCityB-5km2kmCityC10km2kmCityD5kma.Drawtheweightedgraphofthesystem.b.WhatistheconditiontostoptheDijkstra’salgorithm?c.Isthereawaytostopthealgorit

3、hmearlier?Whatisthecondition?d.ApplytheDijsktra’salgorithmtofindtheshortestpathfromthecityAtothecityE(illustratewithatable).e.Whatistheshortestpath?EMARO-AI(v.01/24/13)TD2-ShortestPathAlgorithms-1/4PhilippeLucidarmeExercise3Let’sconsiderthefollowinggraphs:111111110303132832-2

4、Graph1Graph2Graph1and2areequivalents;weightsongraph2havebeenshiftedfrom-10.a.ApplytheDijsktra’salgorithmongraph1inordertofindtheshortestpathfromnode0tonode3.Thealgorithmisstoppedwhentheopenlistisempty(illustratewithatable).b.ApplytheDijsktra’salgorithmongraph1inordertofindthe

5、shortestpathfromnode0tonode3.Thealgorithmisstoppedwhenthereisnoshortestdistancetothegoalintheopenlistthanthebestknown(illustratewithatable).c.ApplytheDijsktra’salgorithmongraph2inordertofindtheshortestpathfromnode0tonode3.Thealgorithmisstoppedwhentheopenlistisempty(illustrate

6、withatable).d.ApplytheDijsktra’salgorithmongraph2inordertofindtheshortestpathfromnode0tonode3.Thealgorithmisstoppedwhenthereisnoshortestdistancetothegoalintheopenlistthanthebestknown(illustratewithatable).e.Conclude.Exercise4Let’sconsiderthefollowinggraph:A2km2.7kmS0.4kmGBC0.

7、7km0.8km1kmEMARO-AI(v.01/24/13)TD2-ShortestPathAlgorithms-2/4PhilippeLucidarmea.ApplytheA*algorithm,withthefollowingestimatedvalue:minimumnumberofarcsbetweenthecurrentstateandthegoal(thisvalueisassumedtobeknown):·HS=2·HA=1·HB=2·HC=1b.Let’snowconsiderthefollowinggraph:A1.3km1.

8、2kmSGBC0.9km0.8km0.7kmApplytheA*algorithm,withthefollowingestimatedv