人工智能練習(xí)題_第1頁(yè)
人工智能練習(xí)題_第2頁(yè)
人工智能練習(xí)題_第3頁(yè)
人工智能練習(xí)題_第4頁(yè)
人工智能練習(xí)題_第5頁(yè)
已閱讀5頁(yè),還剩38頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡(jiǎn)介

PartISEARCH1SearchYou’reataxidriver.Yourtaxicanhold4passengers.Passengerspayaflatfeeforaridetotheairport,sogoalistopickup4passengersandtakethemtotheairportinthesmallestnumberofmiles.Yourworldcanbemodeledasagraphoflocationswithdistancesbetweenthem.Some,butnotall,ofthelocationshavepassengersthatyoucanpickup.a.Describethestatespaceofthissearchproblem.b.Whatwouldbeagoodcostfunctionforthissearchproblem?c.Now,consideracasewherepassengershavetopayaccordingtohowfarawaytheyarefromtheairportwhenthey’repickedup(note:theydon’tpayaccordingtohowlongaridetheytakeinyourtaxi,butaccordingtothelengthoftheshortestpathfromtheirpickup-pointtotheairport).Describethestatespaceofthissearchproblem.d.Whatwouldbeagoodcostfunctionforthisversionoftheproblem?Youstillhaveadesiretosavegas.e.Isuniformcostsearchguaranteedtofindtheoptimalsolutionineitherorbothversionsoftheproblem?Whyorwhynot?a.Yourcurrentlocationandnumberofpassengersinthecar.b.Distancetraveledsofar.c.Currentlocation,thenumberofpassengersinthecar,andthefaresofthepassengersyouhaveinthecar.d.Someconstantc1timesthedistancetraveledsofarminussomeotherconstantc2timesthefaresofthepassengerswe’vepickedupsofar.e.UCSwillworkinthefirstcase,becausetherearenonegativecosts,butit’snotguaranteedtofindtheshortestpathinthesecondversionoftheproblem.2SearchConsiderthefollowinggraph,inwhichAisthestartnodeandFisthegoalnode.Assumethatnodesarevisitedatmostonce.1.Inwhatorderdoesuniform-costsearchvisitthenodes?2.Lettheheuristicfunctionh(n)betheminimumnumberofarcsbetweennodenandthegoalnode.Isthisanadmissibleheuristic?WhyorWhynot?3.InwhatorderdoesA*searchvisitthenodes?Whataretheirestimatedvalueswhentheyarevisited?1.ABECF2.Yes,itisadmissiblebecauseitisaconservativeestimateofthedistance.3.A(2)B(4)E(4)F(5)3SearchBelowisagraphtobesearched(startingatSandendingatG).Link/edgecostsareshownaswellasheuristicestimatesatthestates.Youmaynotneedalltheinformationforeverysearch.1.Drawthecompletesearchtreeforthisgraph.Labeleachnodeinthetreewiththecostofthepathtothatnodeandtheheuristiccostatthatnode.Whenyouneedtorefertoanode,usethenameofthecorrespondingstateandthelengthofthepathtothatnode.2.Foreachofthesearchesbelow,justgivealistofnodenames(statename,lengthofpath)drawnfromthetreeabove.Breaktiesusingalphabeticalorder.1.Performadepth-firstsearchusingavisitedlist.Assumechildrenofastateareorderedinalphabeticalorder.Showthesequenceofnodesthatareexpandedbythesearch.S0,A3,C5,G5notethatB6isnotexpandedbecauseBisonvisitedlist(placedtherewhenS0wasexpanded).2.Performabest-first(greedysearch)withoutavisitedorexpandedlist.Showthesequenceofnodesthatareexpandedbythesearch.S0(h=5),A3(h=2),G5(h=0)3.PerformaUniformCostSearchwithoutavisitedorexpandedlist.Showthesequenceofnodesthatareexpandedbythesearch.S0,B1,C2,A3,A4,C5,G5notethatnodesareorderedfirstbycostthenalphabeticallywhentiedforcost.4.PerformanA*search(nopathmax)withoutanexpandedlist.Showthesequenceofnodesthatareexpandedbythesearch.S0(0+5),B1(1+3),C2(2+2),A3(3+2),G5(5+0)5.Istheheuristicinthisexample1.admissible?Yes2.consistent?NoJustifyyouranswer,briefly.Allthehvaluesarelessthanorequaltoactualpathcosttothegoalandsotheheuristicisadmissible.Theheuristicdropsfrom5atSto3atBwhilethepathcostbetweenSandBisonly1,andsotheheuristicisnotconsistent.4Search(121234987651011121314a).Breadth-firstsearch(3Points)b).Depth-firstsearch(3Points)5IDA*WriteoutthemainideaofIterativeDeepeningA*.6MissionariesandcannibalsThemissionaries(傳教士)andcannibals(食人者)problemisusuallystatedasfollows.Threemissionariesandthreecannibalsareonleftsideofariver,alongwithaboatthatcanholdoneortwopeople.Findawaytogeteveryonetotherightside,withouteverleavingagroupofmissionariesinoneplaceoutnumberedbythecannibalsinthatplace.Wecansearchinthestatespacesofthisproblemtosolveit.Sowehavetodefinethestateandtheoperatorsfirstly.Thestatesandoperatorsaredefinedasbelow:State:Astateconsistsofanorderedsequenceofthreenumbersrepresentingthenumberofmissionaries,cannibals,andboatsontheleftsideoftheriver.Thus,thestartstateis(3,3,1)andthegoalstateis(0,0,0).Operators:Wedefinepijasboatingimissionariesandjcannibalsfromleftsideoftherivertotherightsideandqijasboatingimissionariesandjcannibalsfromrightsideoftherivertotheleftside.Drawthestate-spacegraphofthisproblem.Youdonotneedtodrawanystates;justcompletethegraphthatIhavegiven.Youmaymarktheoperatorpijonlybesideeveryedge.(Becauseoperatorqijisthesameaspij)331331220321311111011000p02p01p11p0272L-WaterTherearetwobottlesnamedAandBtostorewater.ThevolumeofAis4LandBis3L,eitherwithnoscalesonit.Ouraimistoget2LwaterexactlyinbottleAthroughsomeoperations.Ateachstep,wecanperformoneofthethreeoperations:(1)fillinguponebottle(2)emptyonebottle;(3)dumpwaterfromonebottletoanother.Howcanyouget2LexactlyinbottleA?Searchinginstatespaceofthispuzzlewillleadtoasolutionandthebest-firstsearchcanimprovesearchefficiency.Sowehavetodefinethestateandtheestimationfunction.Thestatesandestimationfunctionaredefinedasbelow:State:Astate,(x,y),consistsofanorderedsequenceoftwovariablesrepresentingthevolumeofwaterinbottleAandbottleB.Thus,thestartstateis(0,0)andthegoalstateis(2,0).Wedefinetheestimationfunctionasf’(n)=g’(n)+h’(n).g’(n)=numberofoperationsalreadyperformed.h’(n)=2If0<x<4and0<y<3=4if0<x<4or0<y<3=10ifx=0andy=0orx=4andy=3=8ifx=0andy=3orx=4andy=0Pleasedrawthesearchtree,andforeachnodengivethevalueoff’(n).8BottleworldImagineaworldwhichconsistsoffourbeerbottlesA,B,C,andD.Theycanbearrangedinanyorderfromlefttoright,exceptthatbottleAcanneverbefurthertotherightthanbottleD.Forexample,ABCD,CBAD,andCADBarepossiblestatesofourworld,whereasDCBA,CDAB,orBCDAcanneveroccur.Theworldcanbemanipulatedbytheschemaswap(x,y),whichswapsthebottlesinpositionsxandy.Forexample,swap(1,2)turnsstateBCADintoCBAD.However,swap(1,2),swap(2,3),andswap(2,4)aretheonlythreeavailableoperators.a)Drawthestate-spacegraphofthisworld.Youdonotneedtodrawanybottles;justusefour-lettersequencestodescribestates.b)AssumethatyourworldisinthestateADBC,andthegoalstateisCBAD.Nowwedefineaestimationfunctionf’(n)=g’(n)+h’(n),f’(n)=numberofoperationsalreadyperformed+(numberofbottlesinincorrectposition)/2.Pleasewritedowntheresultingsearchtree,indicatetheorderinwhichnodeswerecreated,andforeachnodengivethevalueoff’(n).9Generalgraph-searchingalgorithmPleasepresentageneralgraph-searchingalgorithmthatpermitsanykindoforderingtheusermightprefer-heuristicoruninformed.Thenanswerthefollowingquestions:1)WhathappensifwesimplyappendnewnodesatthebeginningofOPEN?2)WhathappensifwesimplyappendnewnodestotheendofOPEN?

PARTIIGameSearch1PracticeTheIsolaWorldChampionshipsforJavaProgramsIsolaisaboardgamethatisextremelysimpleyet–inmyhumbleopinion–quiteinteresting.Basically,likeineverygoodgameormovie,therearetwoopponents.Theseopponentsliveona7x7arrayofsquares,andtheymovealternately.Onemoveconsistsofmovingtoaneighboringsquare(vertically,horizontally,ordiagonally)thatisnotoccupiedbytheopponentandremovingoneofthesquares,ofcourseonewithno-onestandingonit.Andfinally,whoeveristhefirsttobeunabletomovelosesthegame.Yourtask,ofcourse,istowriteanalgorithminJavathatplaysIsolaatgrandmasterlevel.Youarerequiredtoimplementaminimaxalgorithmandalpha-betapruning.Thegreatestchallengeforprogrammingthealgorithmshouldbethehugenumberofpossiblemoves(upto320,ifIamnotmistaken),becauseeachmoveisacombinationofjumpingtoaneighboringsquareandremovinganyoftheunoccupiedsquares.Maybeitwouldbeagoodideatoimplementsomemechanismthatreducesthenumberofmovesthatarebeingconsidered.Forexample,inmanycasesitdoesnotmatterwhetheryouremoveasquarethatisfarawayfrombothplayers,oryouremoveoneofitsneighboringsquares.Youshouldbyallmeanstrytorestrictthebranchingofthesearchtree,otherwiseyouralgorithmwillnotbeabletolookfarahead.However,withregardtothisassignmentanditsdeadline,youjusthavetoimplementtheplayer,includingareasonablestaticevaluationfunction,minimax,andalpha-beta.Ifyoudothatcorrectly,youwillgetallthepointsforQuestion1.Pleasealsosupplysometextexplaininghowyourevaluationfunctionworks,aswellasanyextramechanismsthatyouimplemented.Afteryousubmittedyourhomework,youcanstillworkonyouralgorithmandimproveituntilthetournament(therewillbeanotherdeadline).2Alpha-BetaPruningThetreebelowindicatesthecompleteMinimaxtreeforaparticularproblem(firstmovebyMAX,thenMIN,andthenMAXagain).Thenumberateachleafpindicatesthevalueofthestaticevaluationfunctione(p)ifitwerecomputedatthatleaf.a)Tocheckwhichbranchwillbeprunedandmarkacross(X)onthesenodes.b)Whichnextmove(theleftorrightone)shouldMAXmake?MAXMAXMINMINMAX-16-244-3022-30-235-21-30689-399-27-54-912-3173-568125-113MINMAXMINmaxminmaxmin453124367525258231544671maxminmaxmin3451236786782345436782343GameSearchConsiderthegametreeshownbelow.Assumethetopnodeisamaxnode.Thelabelsonthearcsarethemoves.Thenumbersinthebottomlayerarethevaluesofthedifferentoutcomesofthegametothemaxplayer.1.Whatisthevalueofthegametothemaxplayer?22.Whatfirstmoveshouldthemaxplayermake?L3.Assumingthemaxplayermakesthatmove,whatisthebestnextmovefortheminplayer,assumingthatthisistheentiregametree?R4Alpha-BetaPruningInthefollowinggametree,arethereanyalpha-betacutoffs??Considerthenodesfromlefttoright,whichnodesarecutoff?CirclethenodesthatarenotexaminedandlabelthemwithL.None.?Considerthenodesfromrighttoleft,whichnodesarecutoff?CirclethenodesthatarenotexaminedandlabelthemwithR.Theleftmost8node.

PARTIIILogic1.ConvertthefollowingEnglishsentencestofirst-orderlogic:1.Everyonehasonemother.YoumayusethepredicateMother(x,y)andEqual(x,y).?x?yMother(y,x)∧(?zMother(z,x)?(y=z))2.Anauntisaparent'ssister.YoumayusethepredicateAunt(x,y),Sister(x,y)andParent(x,y).?xyz.Parent(x,y)∧Sister(z,x)?Aunt(z,y)2.Convertthissentencetoclauseform:?xy.[P(x,y)∧Q(x)?(?zR(z))∧(?wQ(w))]Remove?:?xy.[?(P(x,y)∧Q(x))∨[(?zR(z))∧(?wQ(w))]]Move?:?xy.[?P(x,y)∨?Q(x)∨[(?zR(z))∧(?wQ(w))]]Skolemize:?xy.[?P(x,y)∨?Q(x)∨[R(sk1(x,y))∧Q(sk2(x,y))]]Drop?:[?P(x,y)∨?Q(x)∨[R(sk1(x,y))∧Q(sk2(x,y))]]CNF:?P(x,y)∨?Q(x)∨R(sk1(x,y))?P(x,y)∨?Q(x)∨Q(sk2(x,y))3.Giventhefollowingclauses:1.Hasjob(p,job(p))2.