人工智能课后习题答案部分已翻译考试

1、Chapter11.1 Definein yourownword:(a)intelligence,(b)artificialintelligence,(c)agent.Intelligence智能:Dictionardefinitionsofintelligencetalk abouthecapacitytoacquireandapply knowledor the faculty of thought and reasonor the ability to comprehend and profit from experienTheseareallreasonableanswers,buti

2、fwewantsomethingquantifiablewewoulduse somethingliketheabilityto apply knowledge in orderto performbetterin 智能的字典定义有一种学习或应用知识的能力，一种思考和推理的本领，领会并且得益于经验的能力，这些都是有道理的答案，但如果我们想量化一些东西，我们将用到一些东西像为了在环境中更好的完成任务使能力适应知识Artificialintelligence :Wedefineartificialintelligenceasthestudyandconstructionofagent progra

3、msthatperformwell in a given environment, fora given agentarchitecture.作为一学习和构造智能体程序，为了一个智能体结构，在被给的环境中可以很好的完成任务。Agen 智能体 t:Wedefineanagentasanentity 实体 thattakesactioninresponsetoperceptsfroman environment.在一个环境中对一个对象做出反应的实体1.4Therearewell-knownclassesofproblemthatareintractablydifficultclassesthata

4、re provablyundecidable. DoesthismeanthatAIisimpossible?No.ItmeansthatAIsystemsshouldavoidtryingtosolveintractableproblems.Usually,thismeansthey can onlyapproximateoptimalbehavior.NoticethathumansdontsolveNPcompleteproblemseither.Sometimesaregoodatsolvingspecificinstanceswithalotofstructure,perhapswi

5、ththeaidofbackgroundknowledge.should attempt to dothesame.1.11“surelycomputerscannotbeintelligent-theycandoonlywhattheirprogrammerstellthem.”Islatterstatementtrue,and doesitimplytheformer?Thisdependsonyourdefinitinofintelligenadtel.Inonesensecomputersonlydowhattheprogrammers commandthemtodo,butinano

6、thersense whatthe programmers consciouslytellsthe computertodooftenhasvery littletodowithwhatthecomputeractually does. Anyonewhohaswritten a program withanornerybugknowsthis,asdoesanyonewhohaswrittenasuccessfulmachinelearning program.SoinonesenseSaueltodthecomputrlearntoplaycheckersbetterthanI Sower

7、e leftin the situationwhereyoumay ormay notconsider learning to play checkers tobes signof intelligence(oryou maythinkthatlearningtoplayintherightwayrequiresintelligence,butnotinthisway),andyou maythinktheintelligenceresidesin the programmeror inthe computerChapter2Defineinyourownreflexagent,model-b

8、asedagent,goal-basedagent,utility-basedagent,learningagent.Thefollowingarejust some ofthe manypossible definitionsthatcan bewritten:Agent智能体:anentity（实体）thatperceives （感知）andacts行;or,onethatcanbeviewedas perceivingandacting.Essentially 本 质 上 anyobjectqualifies 限 ;thekeypointisthewaytheobject impleme

9、ntsanagentfunction.(Note:someauthorsrestrictthetermtoprogramsthatcancausesomeoralloftheircodetorunonothermachinesonanetwork,asinmobile agents.MOBILE AGENT)一个具有感知和行文的实体，或者是一个可以观察到感觉的实体，本质上，任何限定对象，只要的观点是一种对象执行智能体函数的方法。（注意，一些作者）可以感知环境，并在环境中行动的某种东西。Agentfunction:afunctionthatspecifiestheagentsactioninre

10、sponsetoeverypossible perceptsequence.智能体相应任何感知序列所采取的行动Agentprogram:thatprogramwhich,combinedwithamachinearchitecture,implementsanagentfunction.Inoursimpledesigns,theprogramtakesanewperceptoneachinvocationandreturnsanaction.实现了智能函数。有各种基本的智能体程序设计，反应出现实表现的一级用于决策过程的信息种类。设计可能在效率、压缩性和灵活性方面有变化。适当的智能体程序设计取

11、决于环境的本性Rationality；理性:apropertyofagentsthatchooseactionsthatmaximizetheirexpectedutility,giventhe perceptstodate.Autonomy :apropertyofagentswhosebehaviorisdeterminedbytheirownexperienceratherthan solelybytheir initialprogramming.Reflex agent:an agentwhoseactiondependsonlyon thecurrentpercept.一个智能体的行

12、为仅仅依赖于当前的知觉。Model-basedagent:anagentwhoseactionisderiveddirectlyfromaninternalmodel of currentworldstate thatisupdated overtime.一个智能体的行为直接得自于内在模型的状态，这个状态是当前世界通用的不断更新。Goal-basedagent:anagentthatselectsactionsthatitbelieveswillachieveexplicitly represented goals.智能体选择它相信能明确达到目标的行动。Utility-basedagent:a

13、nagentthatselectsactionsthatitbelieveswillmaximizetheexpectedutilityofthe outcome state.试图最大化他们自己期望的快乐Learning agent:an agentwhosebehavior improvesovertime based on itsexperience.Boththeperformancemeasureandtheutilityfunctionmeasurehowwellanagentisdoing. Explain difference betweenthe two.Aperformanc

14、e measure（性能度量）isused byanoutside observer toevaluate（评估）howsuccessfulanagent is. It isa function fromhistories to a realnumber. Autilityfunction（效用函数）isused byan agent itselftoevaluatehowdesirable（ 令 人 想 要 ）statesorhistoriesare.Inourframework,theutilityfunction maynotbethesameastheperformancemeasur

15、e;furthermore,anagentmayhavenoexplicitutility functionatall, whereas there isalwaysa performancemeasure.For each offollowingagents, develop aPEAS description of the taskenvironment:Robot soccerplayer;Internetbook-shopping agent;AutonomousMarsrover;Mathematicianstheorem-proving assistant.Some represe

16、ntative, butnotexhaustive, answersare given in Figure S2.1.智能体类型机器人足球运动员性能度量赢得比赛， 打败对手 获得请求/环境裁判，自己队伍，其他队伍，自己身体执行器装置（腿）行走踢球传感器加速器因特网购书智能体感兴趣的书，最小支出因特网向下连接，输入提交数据，用户显示器网页，用户请求自主火星 漫地形探测，汇报，火星，运行装置，轮子/腿，简单手机装置，相机，触摸传感器步者 数学家的定理 证明助手样本采集分析登陆器分析装置，无线电发射装置方向传感器Foreachof theagent types listed in Exercise2

17、.5,characterizetheenvironmentaccording to propertiesgiveninSection2.3,andselectasuitable agentdesign.The followingexercisesallconcern implementation ofenvironmentand agentsfor thevacuum-cleanerworld.Environmentpropertiesare given inFigure S2.2. Suitableagent types:a.Amodel-basedreflexagentwouldsuffi

18、ceformostaspects;fortacticalplay,autilitybasedagentwithlookahead would be useful.基于模型的映射能够满足大多数要求对于战术游戏向前效用智能体将会有用b.Agoal-basedagentwouldbeappropriateforspecificbookrequests.Formoreopenendedtaskse.g.,Findsomethinginterestingtoreadtradeoffs （ 权 衡 折 中 ）areinvolved（ 棘 手 的）andthecompareutilitiesforvario

19、us（不同的） possiblepurchases.基于目标的智能体将适当的明确书的请求，为更多开放的任务，例如查找我有兴趣读的书，智能体必须比较各种可能的购买方式之间的效用c.Amodel-basedreflexagentwouldsufficeforlow-levelnavigationandobstacleavoidance;forrouteplanning,explorationplanning,experimentation,etc.,somecombinationofgoal-basedandutility-based agentswould be needed.测计划，实验等。这

20、需要基于目标和效用的智能体。d. For specificprooftasks, agoal-based agent isneeded. Forexploratory taskse.g., Prove someuseful lemmata concerningoperationson stringsa utility-basedarchitecture mightbe needed.为了明确的检验任务，需要基于目标的智能体，为探测任务，任务环境可观察性确定性片段性静态性离散型智能体数机器人足球运动员部分随机的连续的动态的连续的多因特网购书智能体部分确定的连续的静态的离散的单自主火星漫步者部分随

21、机的连续的动态的连续的单数学家的定理证明助手完全确定的连续的静态的离散的多Chapter33.1Defineinyourownwordsthefollowingterms:state,statespace,searchtree,searchnode,goal, action, successorfunction, and branchingfactor.state:Astateisasituationthatanagentcanfinditselfin.Wedistinguish(theactualconcretesituationsintherealworld)and representat

22、ionalstates(theabstractdescriptionsofthe realworld thatare used bythe agentin deliberatingaboutwhat todo).state space:Astate spaceisa graph whosenodesarethe setofallstates, and whose linksare actionsthattransformone state intoanother.searchtree:Asearchtreeisatree(agraphwithnoundirectedloops)inwhicht

23、herootnodeisthestart state and thesetofchildrenforeachnodeconsistsofthe statesreachable bytakinganyaction.searchnode:Asearchnodeisa node inthe search tree.goal:Agoalisa statethatthe agentistryingto reach.action :Anactionissomethingthattheagentcan choose to do.(action, state)pairs, whereeachstateisth

24、estatereachablebytakingthe action.branching factor:The branchingfactor in asearchtree is the numberofactionsavailabletothe agent.Givetheinitialstate,goaltest,successorfunction,andcostfunctionforeachofthefollowing. aformulation that isprecise enoughto beimplemented.a.Youhavetocoloraplanarmapusingonly

25、fourcolors,insuchawaythatnotwoadjacentregions have the same color.Initialstate:No regionscolored.Goaltest:Allregionscolored, andno twoadjacentregionshave thesame color. Successorfunction:Assign a colorto aregion.b. A3-foot-tall monkey isinaroom wheresomebananasare suspended fromthe8-footceiling. wou

26、ldliketogetthebananas.Theroomcontainstwostackable,movable,climbable3-foot-high crates. Initialstate:Asdescribed in 初始状态：Goaltest:Monkeyhasbananas.目标测试：猴子拿到香蕉:Hoponcrate;Hopoffcrate;Pushcrate fromonespottoanother;Walk fromonespottoanother; grab bananas(ifstandingon crate). 挪动箱子，把箱子叠起，走到箱子上拿香蕉Costfunc

27、tion:Numberofactions. 行动数量c.Youhaveaprogramthatoutputsthemessage“illegalinputrecord”whenrecords.Youknowthatprocessingofeachrecordisindependentoftheotherrecords.You discoverwhatrecordisillegal.Initialstate:consideringallinput records.Goaltest:consideringa single record, and itgivesillegal input messa

28、ge. Successorfunction: runagain onthefirsthalfoftherecords;run againon the second halfoftherecords.Costfunction:Numberofruns.Note:Thisisa contingencyproblem;you need toseewhetherarun givesanerror message ornotto decide whatto do next.fileofinputwanttod.Youhavethreejugs, measuring12gallons,8gallons,a

29、nd3gallons,andawater faucet. Youcanfill thejugsuporemptythemoutfromonetoanotherorontotheground.Youneedtomeasureout exactly one gallon.Initialstate:jugshave values 0,0, 0.Successorfunction:given values x, y, z, generate12, y, z, x, 8, z, x, y, 3(byfilling);0, y, z, x, 0, z, x,y,0(byemptying);orwithxt

30、otheminimumofx+yandthecapacityofthejug,anddecrementsthejugwithybytheamountgained bythefirstjug.Costfunction:Numberofactions.Considerastatespacewherethestartstateisnumber1andthesuccessorfunctionforstaten returntwo states, numbers2n and 2n+1.a. Drawthe portion of thestate spacefor states1to15.See Figu

31、re S3.1.b.Supposethegoalstateis11.Listtheorderinwhichnodeswillbevisitedforbreadth-firstsearch, depth- limitedsearchwithlimit3, anditerative deepening search.Breadth-first:12 3 4 56 78 9 10 11Depth-limited:12 4 8 95 10 11Iterative deepening:1;1 23;1 2 45 3 6 7;1 24 8 9 510 11c.Wouldbidirectionalsearc

32、hbeappropriateforthisproblem?Ifso,describeindetailhowitwould work.Bidirectionalsearchisveryuseful,becausetheonlysuccessorofninthereversedirectionis(n/2).This helpsfocusthe search.d. Whatisthe branchingfactorin each direction ofthe bidirectionalsearch?2 intheforward direction;1 inthereversedirection.

33、e.Doestheanswerto(c)suggestareformulationoftheproblemthatwouldallowyoutosolvethe problemofgettingfromstate1 toa given goalstatewith almostno search?Yes;startatthe goal, and applythesinglereverse successoraction untilyou reach1.Chapter44.2 The heuristic path algorithm is a best-first search in which

34、the objective function is f(n)=(2- w)g(n)+wh(n).Forassumethathisadmissible.)Whatkindofsearchdoesthisperformwhenw=0?Whenw=1?Whenw=2?w=0 givesf(n)=2g(n). Thisbehavesexactly likeuniform-costsearchthefactorof twomakesno differenceinthorderifthenodes.w=1givesearch.w=2givesf(n)=2h(n),i.e.,greedybest- firs

35、tsearch.Wealso have f(n)= (2w)g(n)+w2 wh(n)which withaheuristicw2wh(n).Forw1,thisisalwayslessthanh(n)andhenceadmissible,providedh(n)isitself admissible.4.11 Givethe name of thealgorithmthatresultsfromeach of thefollowingspecialcases:Localbeam searchwithk=1.Localbeamsearch with k=1 ishill-climbingsea

36、rch.Localbeamsearchwith one initialstateand no limitonthe number of statesretained. Localbeamsearchwithk=:strictlyspeaking,thisdoesntmakesense.(Exercisemaybemodifiedin futureprintings.)Theideaisthatifeverysuccessorisretained(becausekisunbounded),thenthesearch resemblesbreadth-firstsearchinthatitadds

37、onecompletelayerofnodesbeforeaddingthenextlayer. Startingfromonestate,thealgorithmlayerisgenerated allatonce.Simulated annealingwith T=0 atalltimes(andomittingthe terminationtest).Simulatedannealing with T=0atalltimes:ignoring thefactthattheterminationstepwouldbetriggered immediately,the search woul

38、d be identicaltofirst-choicehillclimbing becauseevery downwardsuccessor would berejected withprobability1. (Exercise maybe modifiedinfutureprintings.)Genetic algorithmwithpopulationsize N=1. GeneticalgorithmwithpopulationsizeN=1:ifthepopulationsizeis1,thenthetwoselectedparentswill bethesameindividua

39、l;crossoveryieldsanexactcopyoftheindividual;thenthereisasmallchanceof mutation.Thus,the algorithmexecutesa randomwalkin the spaceofindividuals.Chapter5Define inyourown wordstheterms constraintsatisfactionproblem, constraint,backtracking arcconsistency,backjumpingand min-conflicts.valueforeach ofaset

40、ofvariables,in such awaythatthe valuesallobeya setofconstraints.chooseaconstraint:Aconstraintisarestrictiononthepossiblevaluesoftwoormorevariables.Forexample,a saythatA= a isnotallowedinconjunction with B= b.Backtrackingsearch:Backtrackingsearchisaformdepth-firstsearchinwhichthereisasinglerepresenta

41、tionthe state thatgetsupdatedforeach successor, and then mustbe restored when a dead end is reached.arcconsistent:Adirected arc fromvariable Ato variable Bin aCSP isarc consistentif, forevery valuein the currentdomain ofA,thereissome consistentvalueofB.Brckjumping :Backjumping isaway ofmaking backtr

42、acking searchmore efficient, byjumping backmore one levelwhena deadend is reached.Min-conflicts:Min-conflictsisaheuristicforusewithlocalsearchonCSPthat,whengivenavariabletomodify,choose thevalue thatconflictswiththefewestnumberofother variables.Howmanysolutionsare thereforthemap-coloring problem inF

43、igure 5.1? Thereare18solutionsforThenmovingclockwise,WAcanhaveeitheroftheothertwocolors,andeverythingelseis determined;thatmakes6 possibilitiesforthe mainland, times3 forTasmania yields18.colors. strictly5.6SolvethecryptarithmeticprobleminFigure5.2byhand,usingbacktracking,forwardchecking, and theMRV

44、and least-constraining-vague heuristics.a. ChoosetheX3 variable.Itsdomain is0, 1. b.Choosethevalue1forX3.(Wecantchoose0;itwouldntsurviveforwardchecking,becauseitwould force F to be 0,andtheleadingdigitof the sum mustbe non-zero.)ChooseF, because ithasonlyone remaining value.Choosethe value 1forF.Now

45、X2andX1 aretiedforminimumremaining valuesat2;letschooseX2.Eithervaluesurvives forward checking, forX2.NowX1 hasthe minimumremaining values.Again, arbitrarilychoose0 forthe value ofX1. i.ThevariableOmustbeanevennumber(becauseitisthesumofT+Tlessthan5(becauseO+O=R+ 10 0).Thatmakes itmostconstrained. j.

46、Arbitrarilychoose 4asthe value ofO. k. Rnowhasonly1 remaining value.l. Choose the value8 forR.m.Tnowhasonly1 remaining value.Choosethe value 7forT.Umustbe an even numberlessthan 9;choose U.The only value forUthat survives forward checkingis6.The only variable left isW.The only value left forWis3.Thi

47、s isa solution.Thisisarathereasy(under-constrained)puzzle,soitisnotsurprisingthatwearriveatasolutionwithno backtracking(given thatweareallowedto use forwardchecking).Chapter66.1Thisproblemexercisesthebasicconceptsofgameplaying,usingtic-tac-toe(noughtsandcrosses) asanexample.WedefineXnasthenumberofro

48、ws,columns,ordiagonalswithexactlynXsandnonOs.Similarly,Oisthenumberofrows,columns,ordiagonalswithjustnOs.Theutilityfunctionnassigns+1toanypositionwithX3=1and-1toanypositionwithO3=1.Allotherterminalpositions haveutility0. Fornonterminalpositions, weusea linearevaluation function definedasEval(s)=3X2

49、(s)+X1(s) (3O2(s)+O1(s).a. Approximatelyhowmanypossible gamesof tic-tac-toe arethere?b.Showthewholegametreestartingfromanemptyboarddowntodepth2(i.e.,oneXandoneOonthetakingsymmetryinto account.c. Markon your treetheevaluationsofallthepositionsatdepth 2. d.Usingtheminimaxalgorithm,markonyourtreethebac

50、ked-upvaluesforthepositionsatdepths1and 0,and use those valuesthe choosethe beststarting move.e.Circlethenodesatdepth2thatwouldnotbeevaluatedifalpha-betapruningwereapplied,assumingnodesare generatedintheoptimalorder foralpha-beta pruning.FigureS6.1 shows thegame tree,with theevaluationfunctionvalues

51、below the terminalnodesand the backed- upvaluestotherightofthenon-terminalnodes.ThevaluesimplythatthebeststartingmoveforX istotakethecenter. Theterminalnodeswith abold outline aretheonesthatdonotneed tobe evaluated, assumingthe optimalordering.6.15Describehowtheminimaxandalpha-betaalgorithmschangefo

52、rtwo-players,nonzero-sum games in whicheachplayerhashisorherown utility function. You may assume thateach player knows the othesutility function.Ifthere arenoconstraintson the twoterminalutilities,is itpossible for any be prunedby alpha-beta?Theminimaxalgorithm6;thatis,theevaluationfunctionisavector

53、ofvalues,oneforeachplayer,andthebackupstep selectswhichevervectorhasthehighestvaluefortheplayerwhoseturnitistomove.Theexampleatthe endofSection6.2(p.167)showsthatalpha-betapruningisnotpossibleingeneralnon-zero-sumgames, anunexamined leafnode mightbe optimal forboth players.p.165becauseChapter77.3 Co

54、nsiderthe problemofdecidingwhether a propositionallogic sentence is true in agiven model.a.WritearecursivealgorithmPLTRUE?(s,m)thatreturnstrueifandonlyifthesentencesis trueinthemodelm(wheremassignsatruthvalueforeverysymbolins).Thealgorithmshouldrun intimelinearinthesizeofthesentence.(Alternatively,u

55、seaversionofthisfunctionfromtheonlinerepository.)ThereisapltrueinthePython code,and a versionofaskintheLisp code that serves the same purpose. TheJava code did nothavethis functionasof May2003, butitshould beadded soon.)b.Givethreeexamplesofsentencesthatcanbedetermined tobe trueor falseinapartialmod

56、el that doesnot specify atrue valueforsome of thesymbols.ThesentencesTrue,PP,andPPcanallbedeterminedtobetrueorfalseinapartialmodelthatdoesnot specifythetruthvalueforP.c.Showthatthetruthvalue(ifany)ofasentenceinapartialmodelcannotbedeterminedefficiently in general.It ispossible tocreate two sentences

57、, each withkvariablesthatare notinstantiated inthe partialmodel, such thatone of themis trueforall2k possible valuesof the variables, while the othersentenceisfalse forone of the2 k values.Thisshowsthatingeneralonemustconsiderall2k possibilities.Enumeratingthemtakesexponentialtime.d.ModifyyourPLTRUE

58、?Algorithmsothatitcansometimesjudgetruthfrompartialmodels, whileretainingitsrecursivestructureandlinear runtime.Givethreeexamplesofsentences whose truthin a partialmodelisnotdetected byyour algorithm.Thepython implementationofpl true returnstrueifanydisjunctofadisjunction istrue,andfalseifany conjun

59、ctofaconjunctionisfalse.Itwilldothisevenifotherdisjuncts/conjunctscontainsuninstantiatedvariables.Thus,in the partialmodelwherePistrue,PQreturnstrue,andPQreturnsfalse. But the truth valuesofQQ, QTrue,andQQare notdetected.e. Investigatewhetherthemodified algorithmmakesTTENTALLS? More efficient.Ourver

60、sion oftt entails alreadyusesthismodifiedpl true. Itwould beslower ifitdid not.7.5Consideravocabularywithonlyfourpropositions,A,B,C,andD.Howmanymodelsarethere for thefollowingsentences?a. (A B)(BC)b. A Bc. A B CThesecanbecomputedbycountingtherowsinatruthtablethatcomeouttrue.Remembertocountpropositio