资源描述：
《人工智能章用搜索法对问题求解》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、人工智能━一种现代方法第二部份 问题求解PROBLEM-SOLVING第三章用搜索法对问题求解3.1问题求解智能体3.2问题实例3.3对解的搜索3.4无信息的搜索策略3.5避免重复状态3.6使用不完全信息搜索3.5小结3.6参考文献与历史注释习题问题求解智能体目标形式化问题形式化搜索形式化执行搜索行动序列（问题的解）一个问题可形式化的定义为四个组成部分初始状态:智能体的起始状态对智能体可采纳的可能行动的描述：后续函数Successor-FN(x)给定一个状态x，返回一个由有序对<行动，后续>组成的集合，其中每个行动都是状态
2、x下的合法行动目标测试：确定给定的状态是不是目标状态路径耗散：为每条路径分配一个数值化的耗散值问题的解：从初始状态到目标状态的路径最优解：路径耗散最小的解初始状态和它的后续函数隐含地定义了问题的状态空间一个问题可形式化的定义为四个组成部分初始状态:智能体的起始状态对智能体可采纳的可能行动的描述：后续函数Successor-FN(x)给定一个状态x，返回一个由有序对<行动，后续>组成的集合，其中每个行动都是状态x下得合法行动目标测试：确定给定的状态是不是目标状态路径耗散：为每条路径分配一个数值化的耗散值问题的解：从初始状态到目标
3、状态的路径最优解：路径耗散最小的解问题形式化将问题描述为一个序列，分别用状态、初始状态、状态序列和目标状态来使问题形式化，智能体在目标函数的测试过程中找到一个行动序列，序列应有最小的路径耗散。状态描述抽象化、行动抽象化问题实例玩具问题八皇后问题旅行商问题真空吸尘器世界状态：8个可能的状态后续函数：用来产生通过左移、右移、吸尘能够到达的合法状态目标测试：用来检测是否所有的方格都干净路径耗散：假设每一步的耗散值为1皇后问题增量形式化：初始状态：空棋盘后续函数：目标测试：寻径问题状态：位置和当前时间初始状态后续函数：乘坐的航班、飞行
4、时间、候机时间状态目标测试：是否在预定时间到达目的地路径耗散：等待时间、飞行时间、座位的质量、费用…旅行商问题：状态：当前位置和已经访问过的城市集合目标测试：是否在目的地且已访问过所有城市搜索树由初始状态和后续函数产生搜索树扩展：把后续函数应用于当前状态，生成新的状态集。即生成该节点的所有后续节点，并给出它们之间的耗散值。节点--包含5个元素的数据结构：状态：状态空间中和该节点相对应的状态父节点：搜索树中产生该节点的父节点行动；由父节点产生该节点所用的行动路径耗散：从初始状态到达该节点的路径耗散，路径由父指针表示路径长度：从
5、初始状态到达该节点所经路径上的步数搜索树节点深度：根节点深度=0其他节点深度=父节点深度+1边缘：已经出现但还未被扩展的节点集合。边缘的每个元素都是叶节点，即没有后续的节点搜素策略就是从边缘集合中选择下一个被扩展的节点的函数搜索策略根据实际问题按照一定的策略和规则，利用现有的知识一步一步摸索前进，构造出一条使问题获得解决的过程，即搜索。搜索包含两个问题：合理的推理路线；最优的时间和空间复杂度。搜索的种类：无信息搜索（盲目搜索）启发式搜索（有信息搜索）回溯QQQQ（）Q（）(（1,1）)QQ（）(（1,1）)(（1,1）,(2,
6、3))Q（）(（1,1）)(（1,1）,(2,3))QQ（）(（1,1）)(（1,1）,(2,3))(（1,1）,(2,4))QQQ（）(（1,1）)(（1,1）,(2,3))(（1,1）,(2,4))(（1,1）,(2,4),(3,2))QQ（）(（1,1）)(（1,1）,(2,3))(（1,1）,(2,4))(（1,1）,(2,4),(3,2))Q（）(（1,1）)(（1,1）,(2,3))(（1,1）,(2,4))(（1,1）,(2,4),(3,2))（）(（1,1）)(（1,1）,(2,3))(（1,1）,(2,4))
7、(（1,1）,(2,4),(3,2))Q（）(（1,1）)(（1,1）,(2,3))(（1,1）,(2,4))(（1,1）,(2,4),(3,2))(（1,2）)QQ（）(（1,1）)(（1,1）,(2,3))(（1,1）,(2,4))(（1,1）,(2,4),(3,2))(（1,2）)(（1,2）,(2,4))QQQ（）(（1,1）)(（1,1）,(2,3))(（1,1）,(2,4))(（1,1）,(2,4),(3,2))(（1,2）)(（1,2）,(2,4))(（1,2）,(2,4),(3,1))QQQQ（）(（1,1）)
8、(（1,1）,(2,3))(（1,1）,(2,4))(（1,1）,(2,4),(3,2))(（1,2）)(（1,2）,(2,4))(（1,2）,(2,4),(3,1))(（1,2）,(2,4),(3,1),(4,3))递归：一个递归的例子intListLength(LIST*
