人工智能练习题

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.Hasjob(p,k)∨Equal(job(p),k)3.Hasjob(George,Fireman)4.Equal(Fireman,Teacher)5.Equal(x,y)∨Equal(y,z)∨Equal(x,z)6.Equal(x,y)∨Equal(y,x)Provebyresolutionrefutationthat:Hasjob(George,Teacher)Hint:thinkaboutthestrategyfortheproofbeforeyoustartdoingresolutions.Howwouldyouprovetheresultbyhand?StepParentParentUnifier7NegGoalHasjob(George,Teacher)-----------------827Equal(job(George),Teacher)p=Georgek=Teacher923Equal(job(George),Fireman)p=Georgek=Fireman1096Equal(Fireman,job(George))x=job(George)y=Fireman11510¬Equal(job(George),z)∨Equal(Fireman,z)x=Firemany=job(George)12811Equal(Fireman,Teacher)z=Teacher13412Contradiction4.Writethefollowingsentencesinfirst-orderlogic,usingS(x)forslow,S(x,y)tomeanthatxisslowerthany,H(x)forhorse,B(x)forbrown,andW(x,r)forhorsexwinningracer.1.Allbrownhorsesareslow.2.Allslowhorsesarebrown.3.Allslowthingsarebrownhorses.4.Someslowhorsesarebrown.5.Theslowesthorseisbrown.6.Thereisawinnerineveryrace.1.∀x.B(x)^H(x)⇒S(x)2.∀x.S(x)^H(x)⇒B(x)3.∀x.S(x)⇒B(x)^H(x)4.∃x.S(x)^H(x)^B(x)5.∃x.H(x)^B(x)^∀y.(x≠y^H(x)⇒Slower(x,y))6.∀r.R(r)⇒∃x.W(x,r)5ClausalFormGiventhefollowingsentenceinfirst-orderlogic,convertittoclausalform:∀r.o(r)⇒∃x.w(x)¬o(r)∨w(f(r))6ClausalNormalFormConvertthefollowingsentencetoCNF(A∧B)∨¬(C⇒D)7UnificationForeachpairofliteralsbelow,specifyamostgeneralunifier,orindicatethattheyarenotunifiable.a.r(f(x),y)andr(z,g(w))b.r(f(x),x)andr(y,g(y))c.r(a,C,a)andr(f(x),x,y)a.{z/f(x),y/g(w)}b.notunifiablec.{a/f(x),x/C,y/f(x)}8ClausalformConverteachsentencebelowtoclausalform.a.∀y.∃x.r(x,y)∨s(x,y)b.∀y.(∃x.r(x,y))⇒p(y)c.∀y.∃x.(r(x,y)⇒p(x))a.r(f(y),y)∨s(f(y),y)b.¬r(x,y)∨p(y)c.¬r(f(y),y)∨p(f(y))9FOLSemanticsConsideraworldwithobjectsA,B,andC.We’lllookatalogicallangugewithconstantsymbolsX,Y,andZ,functionsymbolsfandg,andpredicatesymbolsp,q,andr.Considerthefollowinginterpretation:•I(X)=A,I(Y)=A,I(Z)=B•I(f)={<A,B>,<B,C>,<C,C>}•I(p)={A,B}•I(q)={C}•I(r)={<B,A>,<C,B>,<C,C>}Foreachofthefollowingsentences,saywhetheritistrueorfalseinthegiveninterpretationI:a.q(f(Z))b.r(X,Y)c.∃w.f(w)=Yd.∀w.r(f(w),w)e.∀u,v.r(u,v)⇒(∀w.r(u,w)⇒v=w)f.∀u,v.r(u,v)⇒(∀w.r(w,v)⇒u=w)a.Tb.Fc.Fd.Te.Ff.T10Interpretationa.•I(p)={A}•I(q)={C}•I(r)={<A,B>}b.•I(p)={B,C}•I(r)={<A,B>,<B,B>,<C,C>}c.•I(p)={A}•I(r)={<A,A>,<B,A>,<C,A>}11.PropositionalcalculusandresolutionrefutationIsthefollowingargumentvalidornot?Useresolutionorresolutionrefutationtofindout.Proceedinfoursteps:a)Extractthepropositionsfromtheargumentandnamethemwithsingleletters.(4Points)b)Describethehypothesesandtheconclusioninpropositionalcalculus.(3Points)c)Converttheseexpressionsintoconjunctivenormalform(CNF)suitableforresolutionrefutation(3Points)d)Listthestepsoftheresolutionrefutationandstatetheresult,thatis,whethertheargumentisvalidornot.(5Points)AnnegoestothelibraryonSaturdayoronSunday.JohnalsogoestothelibraryonSaturdayorSunday.Therefore,bothAnneandJohnwillbeatthelibraryonSaturday,orbothofthemwillbeatthelibraryonSunday.FrankandSarahtaketheAIcourseatXAUT.SarahandGeorgetaketheDiscreteMathcourseatXAUT.WhoevertakestheAIcourseatXAUTendsupinalunaticasylum(疯人院).WhoevertakestheDiscreteMathcourseatXAUTlosesalltheirhair.Therefore,Sarahwillloseallherhairandendupinalunaticasylum.Jenniferiseitherwatchingasoccergameorabasketballgame,orboth.Whenevershewatchesasoccergame,shewearsaBeckhamt-shirt.Whenevershewatchesabasketballgame,shewearsaYaoMingscarf.Therefore,JenniferiswearingaBeckhamt-shirtandaYaoMingscarf.Ifwecouldtravelbackwardsintime,wecouldvisitourselvesinthepast.Ifwecouldvisitourselvesinthepast,someonewouldhavedoneso.Ifsomeonehadvisitedhim/herselfinthepast,thevisitedpersonwouldpublicizethatevent.Nosucheventhaseverbeenpublicized.Therefore,wecannottravelbackwardsintime.WheneverCarldrinksabottleofwhiskey,hegetsterribleheadaches.WheneverCarldrinksabottleofrum,hebelievesheseespinkelephants.WheneverCarldrinksabottleofwater,hefeelsbored.Hedrinksoneormorebottles,eachofthemcontainingwhiskey,rum,orwater.Carldoesnotbelieveheseespinkelephants,andheisnotbored.Therefore,hemusthavedrunkabottleofwhiskey..12WhataretheresolutionresultandMGUofthetwosentencesbelow?P(x)ÚQ(x,y)P(A)ÚR(B,x)ResolutionResult:MGU:

PARTIIIMachineEvolution1.Onourcomputerwecansimulateevolutionaryprocessesintwomainaspects,pleasewriteoutthetwomainaspects.2.Onourcomputerwecansimulateevolutionaryprocessesintwomainaspects,thatis,generationofdescendantsandselectivesurvivalinthesedescendants.Wecanusethemainideaofevolutionarytoproduceacurriculaschedule.Presentyourdesigntoimplementsuchacurriculaschedule.3.Wehaveintroducedawall-followingrobotinthegrid-space.Wecanusetheideaofmachineevolutiontogetaperfectwall-followingrobotrule.TherearetwotreesrepresenttworulesthattherobotfollowedInthegraphbelow.Pleasegivemethedescendantofthetwotreeuse“crossover”andtheprobablyresultifmutationoccurred.

PARTIVComputerVisionRobotVision(15Points)a)MedianfilteringUsea3´3filterandmoveitacrosstheimage,foreachposition,computethemedianofthebrightnessvaluesoftheninepixelsandusethemedianasthenewvalueforthecenterpixel.AveragingfilteringUsea3´3filterandmoveitacrosstheimage,foreachposition,computetheaverageofthebrightnessvaluesoftheninepixelsandusethemedianasthenewvalueforthecenterpixel.3015027256911815227711817221352017289251018100000000000000000a)Medianfiltering0000000000000000b)Averagingfilteringb)EdgedetectionComputethefirstderivateandsecondderivateinX-directionofthesampleinput.Thefilterisgivenbelow.Filter:-11Sampleinput:254165342Firstderivate:Secondderivate:c).labelingBelowyouseethe2Dprojectionofanartificial3Dscene.Labeleachlineaccordingtoitstype(+,—,↑).FilteringAssumethatyouhavethefollowing7×7pixelgrayscaleimageA:205183200187432554102101961883157332132310213255603721102191993955255189240213172416140192210018947255380201203211374442a)ApplythefollowingSobelfiltertoA:-101-202-101Writedowntheresulting5×5imageBofbrightnessvalues.Ifyouprefer,youcanwriteasmallprogramtodoallcomputationsforQuestion3.b)Nowapplya3×3medianfiltertotheoriginal7×7imageA.AlsoapplythisfiltertothepixelsontheborderoftheimagesothattheresultingimageCisnot5×5,but7×7.Obviously,wheneveryoumovethecenterofyourfilterontotheborder,itwillcoverlessthanninepixels.Thenjusttakethemedianofthissmallersetofpixelsastheresultingbrightnessvalue.WritedownthebrightnessvaluesofC.c)NowapplythesameSobelfilteronceagain,butthistimetothemedian-filteredimageC.Writedownthebrightnessvaluesfortheresulting5×5imageD.d)DescribethedifferencebetweenimagesBandD,thatis,theeffectofapplyingamedianfilterbeforetheSobeloperation.Whyisitagoodideatoperformsmoothing(eitherwithaGaussianormedianfilter)beforeedgedetection?

PARTVInferenceBayes’NetsIamaprofessortryingtopredicttheperformanceofmyclassonanexam.Aftermuchthought,itisapparentthatthestudentswhodowellarethosethatstudiedanddonothaveaheadachewhentheytaketheexam.Myvastmedicalknowledgeleadsmetobelievethatheadachescanonlybecausedbybeingtiredorbyhavingtheflu.Studying,theflu,andbeingtiredarepairwiseindependent.a)WewillmodeleverythingwithBooleanvariables.Findicatesthepresenceoftheflu,Tindicatesbeingtired,H-havingaheadache,S-studying,andE-passingtheexam.Whichofthefollowingthreenetworksbestmodelstherelationshipsdescribed?b)Whyweretheothertwonetworksunsatisfactorymodels?Explainthedeficienciesofeachintermsoftheconditionalindependenceanddependencerelationshipstheymodel.Whichoneoftheremainingmodelsrepresentsanequivalentjointprobabilitytableasthebestmodel,giventhatthedescriptionoftherel