=========================preview======================
(COMP221)midterm-2004.pdf
Back to COMP221 Login to download
======================================================
COMP221:2004SpringSemesterMidterm

Instruction:(a)Thetimethatyouhavefortheexamis90minutes. (b)AttemptALLquestions. (Youmaygetpartialcreditsforyourincompleteanswers!) (c)WriteALLanswersinthebluebook.Donotuseanyotherpapers.
Nowtakeaminutetowritedownyourname,studentIDnumber, labsection,andemailaddress.
Problem1(15pts)Giventhefollowingtrainingset
x
1 x2 output 111 000
Ifwesettheinitialweightsto0,andthelearningratec.1,whatistheTLUtrained accordingtotheerror-correctingprocedurethatwetalkedaboutinclass.Whatisthe BooleanfunctioncorrespondingtothisTLU.
Problem2(15pts)Consideragaintheboundary-followingrobotexample.Recallthat thereareeightsensors,s1tos8,oneforeachdirectionwiths1fornorthwest,s2for north,etc.,andtherearefouractions:north,south,east,andwest.Assumethat initiallytherobotisontopofaboundary(i.e.s6.1).Developaproductionsystemso thattherobotwillmoveontheboundaryleftandrightforeverwithoutfallingo.:the robotwill.rstmoveleft(west)totheendoftheboundary,thenmoveright(east)to theotherendandbackandforthforever.Weassumeherethatwhenevers6.0,the robotfallso.,i.e.actionsouthdoesnotwork.
Problem3(15pts)HeuristicSearch.Consideragainthe8-puzzleasgiveninthefollowing .gure:


. 1998 Morgan Kaufman Publishers
Assumingagainthateachoperatorcostsoneunit,givethe.rst.venodeschosenfor expansionbyA.usingthecityblockdistanceheuristic:foreachstateS,h(S)isthe sumoftheshortestcityblockdistancesofallthenumbersinStotheirrespective goalpositions.Givethenodesinsequenceandlabelthembystates,costs(valuesofg function),andheuristicvalues(valuesofhfunction).
Problem4(20pts)GameSearch.Inthefollowinggametree,therearetwoterminal nodeswithunknownvalues.Letusdenotethembyxandy.

x2 346y
38
1.GivetheconditionsonxandyunderwhichMAXshouldmovetonodeCinorder tomaximizeitschanceinwinningthegame.
2.Supposex.3andy.4.WhichmoveshouldMAXmakefromnodeA.What nodeswouldnotneedtobeexaminedusingthealpha-betaalgorithm.Canyou re-ordertheterminalnodessothatthealpha-betaalgorithmwillbrunethelargest numberofnodes.Noticethatyoucanonlyre-ordernodesthathavethesame parent.
Problem5(20pts)CSP(AssignmentProblem)Usethemin-con.ictmethodtosolvethe problemofcoloringthemapshownherewiththefourcolors:Red,Blue,Green,and Yellow,suchthatnotwoadjacentregionshavethesamecolor.Startwiththefollowing initialcolorassignment:
A.Red.B.Green.C.Yellow.D.Green.E.Red.F.Blue.H.Red.I.Yellow:

Problem6(15pts)STRIPSoperators.Considertheblocksworldwiththefollowing relations:on(xy)ifxisony,ontable(x)ifxisonthetable,clear(x)ifxisclear, handemptyiftherobot'shandisempty,andholding(x)iftherobot'shandisholding x.ConsiderthefollowingSTRIPSoperatorunstack(xy):
unstack(x,y)
preconditionlist:clear(x),on(x,y),handempty
deletelist:clear(x),on(x,y),handempty
addlist:holding(x),clear(y)
1.Giventhefollowinginitialstate:
handemptyon(AB)ontable(B)clear(A).
whatisthenewstateaftertheactionunstack(AB)isperformed. 2.Giventhefollowinginitialstate:
holding(C)on(AB)ontable(B)clear(A).
whatisthenewstateaftertheactionu