人工智能入门 课件 7.总结.ppt

AI:Summary*r(state,action)即时奖励值Q(state,action)valuesV*(state)values10000100G0000000009081100G08172908181729081100G90100081901001.3怎样发现最优函数?使用累计折扣收益，折扣率=0.981=0+0.9*90Q-学习算法AI:Summary*Q值例:Hanoi塔AI:Summary*补充题：以下GridWorld中，除了到达目标状态（G）的动作获得的即时奖励为10以外，其余动作对应的即时奖励皆为0。如采用折扣系数为0.8的累积折扣收益，请计算图中的Q函数值，直接标注在图中。G1086.41086.486.41086.4搜索(最优化)01AI:Summary*什么是搜索?以可以接受的计算代价，在问题所有解答中找出最优解或可行解。理想的搜索算法：尽可能快地找到最优解。求解的效果与效率之间存在矛盾-完备性,最优性,复杂性-盲目vs.启发,局部vs.全局,可行vs.最优.AI:Summary*数学和计算机科学中的核心主题确定性搜索-图搜索随机和基于群体的搜索-进化计算-群智能启发式搜索方法AI:Summary*用于问题求解图搜索算法的一般结构是不断扩展顶点，直到发现目标顶点（状态空间）或者确定初始顶点的可解性（与或图）。).不同图搜索算法的主要区别在于顶点的扩展顺序不同。盲目搜索不考虑问题特性,包括广度优先搜索、深度优先搜索、有界深度优先搜索和迭代加深深度优先搜索。启发式搜索算法根据问题所提供的启发式信息，用估价函数估计顶点的搜索效率，选择估计效率最高的顶点进行扩展。2.1图搜索AI:Summary*状态空间vs.与/或图状态空间与/或图AI:Summary*2.5为什么采用与或图表示法时，解决问题的答案对应于一个子图，而不是一条路径？答：因为与节点AI:Summary*A*算法是影响最大的，应用于状态空间的启发式搜索算法。它通过对估价函数施加一定约束，可以保证搜索到最优解。可容许的启发式函数:如果对于每一个顶点n都有h(n)≤h*(n)，则该启发式函数h(n)是可容许的。其中h*(n)表示从顶点n到目标顶点的最小代价。支配性:如果对于所有顶点都有h2(n)≥h1(n)，并且两者都是可容许的，则h2优于h1,使用h2搜索速度更快A*算法AI:Summary*2.3请用状态空间法求解农夫过河问题，该问题是：一农夫带着一只狼、一只羊和一筐菜来到河边，欲乘船到河对岸。但船太小，农夫每次只能带一样东西过河。而在没有农夫看管的情况下，狼会吃羊，羊会吃菜。农夫应该怎样做，才能在没有任何损失的情况下把所有东西带到河对岸？2.13试用A*算法解决习题2.3中给出的农夫过河问题。解：问题状态表示为（a,b,c,d），其中a,b,c,d分别表示农夫、狼，羊和菜的位置，1表示在左岸，0表示在右岸。则起始状态为(1,1,1,1)，终止状态为(0,0,0,0)。改变状态的操作共八种，分别为：农夫带着{狼、羊、菜}从{左岸到右岸、右岸到左岸}。搜索路径为：(1,1,1,1)?(0,1,0,1)?(1,1,0,1)?(0,0,0,1)?(1,0,1,1)?(0,0,1,0)?(1,0,1,0)?(0,0,0,0)AI:Summary*h(x)=河左岸物体个数

或无穷大（≠人：狼、羊对应位不能相等；羊、菜对应位不能相等）(1,1,1,1)h=3f=3(0,0,1,1)h=∞f=∞(0,1,0,1)h=2f=3(0,1,1,0)h=∞f=∞(1,1,0,1)h=2f=4(0,0,0,1)h=1f=4(0,1,0,0)h=1f=4(1,0,0,1)h=∞f=∞(1,0,1,1)h=2f=6(1,1,0,0)h=∞f=∞(1,1,1,0)h=2f=6102345AI:Summary*(1,0,1,1)h=2f=6(0,0,1,0)h=1f=6(0,0,0,1)h=1f=6(1,0,1,0)h=1f=7(1,1,1,0)h=2f=8(0,0,0,0)h=0f=7h(x)=河左岸物体个数