《第二次作业》PPT课件

第二次作业,2.4让我们考察一下各种真空洗尘器的理性：a.说明图2.3所述的简单吸尘器简单智能体函数在第2.2.2节列出的假设下确实是理性的。b.修改过的性能度量为每次移动减1分，描述一个对应的理性智能体函数。对应的智能体程序需要内部状态吗？c.讨论在干净的方格可能变脏和环境的地理不明的情况下可能的智能体设计。在这些环境下智能体从经验中学习有意义吗？如果有，改学习什么？,要说明智能体是理性的，就需要证明该智能体总是能选择使其性能度量最大化的行动。按照2.2.2所述的智能体函数，如果所处位置“干净”则移动到另一侧，以期望获取一个得分，如果所处位置是“脏”的，则清洁，以获得一个得分。感知序列行动A,CleanRightB,CleanLeftA,dirtySuckB,dirtySuckA,CleanB,CleanNO-OP,单纯从定义上说，为了获得最大性能，是不需要记录内部状态的，因为移动一下需要减一分。但是如果需要确保所有的地方清洁干净，需要一个内部状态记录是否已经清洁过所以地方。c.可以在清理完所有地方后，定时去启动智能体清理地面。对于地理信息比较复杂的情况，通过学习地理信息，可以优化智能体的路径；智能体可通过学习掌握某地方变脏的分布情况。,2.7为图2.2和图2.2.2节描述的吸尘器世界实现一个可以进行性能度量的环境模拟器。你的实现应该是模块化的，以使传感器、执行器和环境特征易于修改。,说明：参照书上图2.7伪代码(P35)，关键是智能体函数的设计、性能度量函数的设计。,第三章作业,3.7给出下列问题的初始状态、目标测试、后继函数和耗散函数。选择精度得足以实现的形式化。a.只用四种颜色对平面地图染色，要求每两个相邻的地区不能染成相同的颜色。b.一间屋子里只有一只3英尺高的猴子，屋子的房顶上挂着一串香蕉，离地面8英尺。屋子里有两个可叠放起来的、可移动的、可攀登的3英尺高的箱子。猴子很想得到香蕉。c.有一个程序，当输入一个特定文件的输入记录时会输出“不合法的输入记录”。已知每个记录的处理独立于其它记录。要求找出哪个记录不合法。d.有三个水壶，容量分别为12加仑、8加仑和3加仑，还有一个水龙头。可以把壶装满或者倒空，从一个壶倒进另一个壶或者倒在地上。要求量出刚好1加仑水。,初始状态：未经染色的平面地图；目标测试：所有地区被染色，且相邻地区颜色不同；后继函数：对某未染色地区染色，且所选颜色与邻近地区不同色；耗散函数：当前状态选择下一个未染色地区染色的耗散为1个单位。b.初始状态：猴子在房间，箱子等在原地未经移动；目标测试：猴子能够够到香蕉；后继函数：移动、攀登或叠放箱子；耗散函数：当前状态下移动、攀登或叠放箱子耗散均为1个单位。,c.初始状态：某未经检测的文件，一个计算机程序；目标测试：检测到某记录不合法；后继函数：输入一个记录，并检测是否合法；耗散函数：每输入一个记录的耗散为1个单位。d.初始状态：三个水壶均为空；目标测试：某水壶恰好含有1加仑水；后继函数：装满某水壶或将某水壶倒空，将一个水壶的水倒入另外一个水壶；耗散函数：选取下一个可行状态耗散都为1个单位。,3.9传教士和野人问题通常描述如下：三个传教士和三个野人在河的一边，还有一条能载一个人或者两个人的船。找到一个办法让所有的人能渡到河的另一岸，要求在任何地方野人数都不能多于传教士的人数。a.精确地形式化该问题，只描述确保该问题有解所必须地特性。画出该问题的完全状态空间。b.用一个合适的搜索算法实现和最优地求解该问题。检查重复状态是个好主意吗？c.这个问题的状态空间如此简单，你认为为什么求解它却很困难？,a.初始状态：六人均在河的一边(左岸)；目标测试：是否六人都在河的另外一边(右岸)；后继函数：一人或两人坐船从河的一边到另外一边；耗散函数：当前状态下船从一侧划到另外一侧耗散值为1个单位。该问题的所有合法状态以及状态空间转换图：(3,3,1/0),(3,2,1/0),(3,1,1/0),(3,0,1/0),(2,2,1/0)(1,1,1/0),(0,3,1/0),(0,2,1/0),(0,1,1/0),(0,0,1/0)其中第一个元素表示在河的左岸的传教士，第二个元素表示在河的左岸的野人数目，第三个元素为1表示船在左岸，为0表示船在右岸。,(3,3,1)(2,2,0)(3,2,0)(3,1,0)(3,2,1)(3,0,0)(3,1,1)(1,1,0)(2,2,1)(0,2,0)(0,3,1)(0,1,0)(0,2,1)(1,1,1)(0,0,0),图3.9状态转换图,采用先深搜索、先广搜索以及图搜索都可以，注意检查重复状态，重复状态的检测避免程序陷入死循环。虽然状态空间比较简单，但是要检测重复状态是一个困难；另外，在当前状态选取下一个合法状态，要能够不漏举所有合法状态也存在困难，当在某个状态无下一个合法状态时，需要回溯，这些都使得人为求解它变得困难。,第四章作业,4.1跟踪A*算法用直线距离启发式求解从Lugoj到Bucharest问题的过程。按顺序列出算法扩展的节点和每个结点的f,g,h值。,Lugoj,Timisoara,Mehadia,440=111+329,311=70+241,Drobeta,387=145+242,Craiova,425=265+160,Pitesti,544=411+193,503=403+100,595=229+366,Bucharest,504=504+0,Lugoj,Timisoara,Mehadia,Arad,Drobeta,Craiova,RimnicuVilcea,Pitesti,Bucharest,4.6设计一个启发函数，使它在八数码游戏中有时会估计过高，并说明它在什么样的特殊问题下会导致非最优解。证明：如果h被高估的部分从来不超过c，A*算法返回的解的耗散比最优解的耗散多出的部分也不超过c。答：启发式函数可以设计为h=h1+h2等，当对最优解路径上的节点启发函数估计过高，有可能导致非最优解，具体可以编制程序来说明。,证明：考虑在边界上的最优解路径上的节点n，由于对每个结点的耗散估计不超过c，则有：f(n)=g(n)+h(n)C*+c现假定要扩展的次优结点G2在边界上，则扩展的次优解结点必有：f(G2)C*+c否则扩展n，而不扩展次优解，故其返回的解不会超过c。,4.7证明如果一个启发式是一致的，它肯定是可采纳的。构造一个非一致的可采纳启发式。概念回顾：启发式是一致的，表示对每个结点n和通过任何行动a生成的每个后继结点n从结点n到达目标的估计耗散不大于从n到n的单步耗散与从n到达目标n的估计耗散之和：h(n)c(n,a,n)+h(n)某启发式算法是可采纳指如果从S到目标结点T有路径存在，算法总是在返回某最优解后结束，称为该启发式算法是可采纳的。,证明:采用数学归纳法，由于启发式是一致的，则有:h(n)c(n,a,n）+h(n)设G为目标结点，则h(G)=0，对任一通过动作a扩展G的结点，由于h(n)c(n,a,G)+0，故可采纳。假定在距离目标结点距离为k的结点都满足A*的定义，则对于距离目标结点距离为