=========================preview======================
(COMP221)midterm97S.pdf
Back to COMP221 Login to download
======================================================
HongKongUniversityofScienceandTechnology 1.(25%)HeuristicSearch COMP221:FundamentalsofArti.cialIntelligence Asearchtreeisshownbelowwhereeachboxrepresentsanodecorrespondingtoastate Spring1997 inthesearchspace.Theestimatedcost(i.e.hfunction)for.ndingasolutionfrom anodeisshowninitsbox.Thetwonodeswithh.0aregoalstatesandtheother
MidtermExamination
terminalnodesaredead-ends(i.e.statesthatcanneverreachagoal).Actuallinkcosts aremarkedonthelinksbetweennodes.Thusthepathcost(i.e.gfunction)ofanode
25March1997,7:30{9:00pm isequaltothesumofthelinkcostsfromtheroottothatnode.
A 25
StudentName:
StudentNumber: LectureSection:

DEF G 1916 1227
Instructions
1.Thisisaclosed-book,closed-notesexamination.
2.Checkthatyouhaveall9pages(excludingthiscoverpage). 125 0 23329012
3.Writeyourname,studentnumberandlecturesectiononthispage.
4.Answerallquestionsinthespaceprovided.Roughworkshouldbedoneontheback

(a)[8%]Usingthegreedysearchalgorithm,givethesequenceofnodesexpandedbefore
agoalstateisreached.Whatisthesolutionpathandwhatisitspathcost. 5.Makeyouranswersasconciseaspossible.
pages.
Question1(25%):
Question2(10%):
Question3(10%):
Question4(10%):
Question5(25%):
Question6(20%):

TOTAL(100%): (b)[8%]Repeatpart(a)usingtheA.searchalgorithm. 2.(10%)GamePlaying

Inthefollowinggametree,therearetwoleafnodeswithunknownevaluationfunction
values.Letusdenotetheunknownvaluesbyxandy.Intermsofxandy,givethe
conditionunderwhichMAXshouldmovetotheleftchildfromtherootnodeinorder
tomaximizeitschanceofwinningthegame.
MAX

x 0 1101 23 y
(c)[9%]Istheheuristicfunction(i.e.h)admissible.Justifyyouranswer.Whatcan yousayabouttheA.searchalgorithminthelightofthispropertyoftheheuristic functionused.
3. (10%)First-OrderLogic SupposeRespects(xy)means\xrespectsy". (a)[3%]WhatisthemeaningofthisFOLsentence. 9x8yRespects(xy) 4. (10%)First-OrderLogic SupposeLoves(xy)means\xlovesy"andHappy(x)means\xishappy".thefollowingtwoFOLsentences: 8x[9yLoves(yx)])Happy(x) 8xyLoves(yx))Happy(x) (a)[6%]Formallyprovethatthetwosentencesarelogicallyequivalent. Consider
(b)[3%]WhatisthemeaningofthisFOLsentence. 8y9xRespects(xy)
(c) [4%]Arethetwosentencesaboveequivalentinmeaning.answer. Brie.yexplainyour
(b)[4%]Whatisthemeaningofthetwosentences.

5. (25%)LogicalReasoning ConsideraknowledgebasewiththefollowingfourFOLsentences: (b) [15%]Usingresolutionwithrefutation,provethat9zHappy(z)istrue.showthesentencesinvolvedandthesubstitutionlistforeachstep. Again,
8xEngineer(x))Wealthy(x) 8yWealthy(y)^Healthy(y))Happy(y) Engineer(Peter) Healthy(Peter)
(a) [10%]Usinggeneralizedmodusponens,provethatHappy(Peter)istrue.Foreach stepinyourproof,showthesentencesinvolvedandthesubstitutionlistresulted fromuni.cation.

6.(20%)Miscellaneous (c)[5%]Aninaccessibleenvironment De.nethefollowingconceptsinyourownwords:
(a)[5%]Acompletesearchstrategy
(d)[5%]Anondeterministicenvironment
(b)[5%]Acompletelogicalinferenceprocedure