人工智能练习题.doc

《人工智能练习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、PartISEARCH1SearchYou’reataxidriver.Yourtaxicanhold4passengers.Passengerspayaflatfeeforaridetotheairport,sogoalistopickup4passengersandtakethemtotheairportinthesmallestnumberofmiles.Yourworldcanbemodeledasagraphoflocationswithdistancesbetweenthem.Some,butnotall,of

2、thelocationshavepassengersthatyoucanpickup.a.Describethestatespaceofthissearchproblem.b.Whatwouldbeagoodcostfunctionforthissearchproblem?c.Now,consideracasewherepassengershavetopayaccordingtohowfarawaytheyarefromtheairportwhenthey’repickedup(note:theydon’tpayaccor

3、dingtohowlongaridetheytakeinyourtaxi,butaccordingtothelengthoftheshortestpathfromtheirpickup-pointtotheairport).Describethestatespaceofthissearchproblem.d.Whatwouldbeagoodcostfunctionforthisversionoftheproblem?Youstillhaveadesiretosavegas.e.Isuniformcostsearchguar

4、anteedtofindtheoptimalsolutionineitherorbothversionsoftheproblem?Whyorwhynot?a.Yourcurrentlocationandnumberofpassengersinthecar.b.Distancetraveledsofar.c.Currentlocation,thenumberofpassengersinthecar,andthefaresofthepassengersyouhaveinthecar.d.Someconstantc1timest

5、hedistancetraveledsofarminussomeotherconstantc2timesthefaresofthepassengerswe’vepickedupsofar.e.UCSwillworkinthefirstcase,becausetherearenonegativecosts,butit’snotguaranteedtofindtheshortestpathinthesecondversionoftheproblem.2SearchConsiderthefollowinggraph,inwhic

6、hAisthestartnodeandFisthegoalnode.Assumethatnodesarevisitedatmostonce.1.Inwhatorderdoesuniform-costsearchvisitthenodes?2.Lettheheuristicfunctionh(n)betheminimumnumberofarcsbetweennodenandthegoalnode.Isthisanadmissibleheuristic?WhyorWhynot?3.InwhatorderdoesA*search

7、visitthenodes?Whataretheirestimatedvalueswhentheyarevisited?1.ABECF2.Yes,itisadmissiblebecauseitisaconservativeestimateofthedistance.3.A(2)B(4)E(4)F(5)3SearchBelowisagraphtobesearched(startingatSandendingatG).Link/edgecostsareshownaswellasheuristicestimatesatthest

8、ates.Youmaynotneedalltheinformationforeverysearch.1.Drawthecompletesearchtreeforthisgraph.Labeleachnodeinthetreewiththecostofthepathtothatnodeandtheheur