人工智能经典问题搜集
1、传教士和野人问题，Amarel（1978）详细的分析过。解题思路
2、八数码游戏是15数码游戏的一个小型同类型游戏。Ratner和Warmuth（1986）证明了15数码问题推广得到的一般的n×n版本属于NP完全问题。
3、八皇后问题，Nauck在1850年晚些时候发表了全部92个解。Netto（1901）将该问题推广到n皇后问题，Abramson和Yung（1989）找到了一个复杂度为O（n）的算法。
1、2、3摘自《人工智能—一种现代方法（第二版）》P71，参考文献与历史的注释
人工智能 一种现代方法 第3章 通过搜索进行问题求解
文章目录问题求解Agent问题形式化通过搜索求解（树搜索、图搜索）无信息搜索策略（盲目搜索）宽度优先搜索（广度优先搜索）（BFS）一致代价搜索（Uniform-costSearch）深度优先搜索(DFS)深度受限搜索(DepthLimitedSearch:DLS)迭代加深的深度优先搜索(IterativeDeepeningSearch:IDS)双向搜索(Bidirectionalsearch)有信息的搜索策略（启发式搜索）贪婪最佳优先搜索A*搜索：缩小总评估代价存储受限的启发式搜索启发式函数总结资源分享问题求解Agent有一些问题无法通过单独的行动得出解，需要行动序列达到目标，则需要使用搜索法。
搜索：寻找能够达到目标的行动序列无信息搜索：算法除了问题定义本身没有任何其他信息。有信息搜索：利用给定的知识引导能够更有效地找到解。问题形式化：在给定目标下确定需要考虑哪些行动和状态的过程。抽象：除去细节的过程被称为抽象。如果执行解中的每个行动比原始问题中的容易，那么这种抽象是有用的。
问题形式化一个问题形式化由下面5个组成部分组成
初转状态在罗马尼亚问题中，初始状态为In(Arad)描述可能的行动给定一个状态s，ACTIONS(s)返回在状态s下可以执行的动作集合。称这些状态读s是可用的。在罗马尼亚问题中，考虑状态In(Arad)，可应用的行动为：（{Go(Sibiu),Go(Timisoara),Go(Zerind)}）转移模型（对每个行动的描述）用函数RESULT(s,a)描述：在状态s下执行行动a后到达的状态。目标测试确定给定的状态是否是目标状态。在罗马尼亚问题中，目标状态集是一个单元素集合{In(Bucharest)}路径耗散此函数位每条路径赋一个耗散值，即边加权。行动a从状态s走到s’的单步耗散用c(s,a,s’)表示可以看出，由初始状态、行动和转移模型就定义了问题的状态空间，即从初始状态可以到达的所有状态的集合。
问题实例玩具问题：滑块问题，八皇后问题，Knuth现实世界问题：TSP，VLSI布线，机器人导航，自动装配
吸尘器问题（玩具问题）状态：由Agent位置和灰尘位置确定，世界状态有n*2的n次方，有n个位置，而且是有或没有灰尘初始行动：任何状态都能被设计成初始状态行动：行动有3个：左、右、吸转移模型：最左边不能再左，最右边不能再右目标测试：检测所有位置是否干净路径消耗：路径耗散值为1，因此整个路径的耗散值是路径中的步数
通过搜索求解（树搜索、图搜索）罗马尼亚状态空间图如下：（从Arad到Bucuresti）
边缘（开结点表）：在任一给定时间点，所有待扩展的叶节点的集合；探索集（closed表）：记录每个已扩展过的结点。一般的树搜索和图搜索算法的非形式化描述：
树搜索树搜索中有冗余路径
（frontier：已生成未拓展；closed：已拓展）
图搜索避免探索冗余路径的方法是牢记曾经走过的路。图搜素在树搜索算法上增加了一个参数：探索集（closed表）：记录每个已扩展过的结点。新生成的结点若于已经生成的某个结点相匹配的话，即是在探索集或是边缘集中，那么它将被丢弃而不是加入到边缘集中。
下图是罗马尼亚问题的图搜索过程：
图搜索只需三步即可到达目标：
图搜索的一个特点：边缘将状态空间图分成了已探索区域和未被探索区域，因此从初始状态出发至任一未被探索状态的路径都不得不通过边缘中的结点。
搜索算法基础一个解是一个行动，搜索算法考虑各种可能的行动序列n.STATE:对应状态空间中的状态n.PARENT:搜索树种产生该结点的结点n.ACTION:父结点生成该结点时所采取的行动n.PATH-COST:代价，一般用g(n)表示，指从初始状态到该结点的路径消耗
队列
FIFO队列：先进先出LIFO队列：栈，后进先出优先级队列：根据函数计算最高优先级，具有最高优先级的队列出队问题求解算法的性能评价性能的标准
完备性：是否保证找到解最优性：找到的解是否最优时间复杂度：找到解需要多少时间空间复杂度：在执行搜索过程中需要多少内存复杂度的表达
b：分支引子任何节点的最多后继数d：深度目标节点的最浅深度根节点到目标节点的步数m：状态空间中任何路径的最大长度评价搜索有效性—搜索代价，通常由时间复杂度和空间复杂度决定
无信息搜索策略（盲目搜索）无信息搜索（盲目搜索）：除了问题定义中提供的状态信息外没有任何附加信息的搜索。当搜索空间较大并且不知道解所在深度时，迭代加深的深度优先搜索是首选的无信息搜索方法。
宽度优先搜索（广度优先搜索）（BFS）a)概念：先扩展根结点，接着扩展根结点的所有后继，每次总是扩展深度最浅的结点，然后再扩展它们的后继。b)评价：
完备的（分支因子b有限时）；最优的（如果路径代价是基于结点深度的非递减函数，比如stepcost保持是1，则是最优的）；时间复杂度如果目标检测是在选择扩展的结点时:O(b^d)如果选择要扩展的结点在结点生成时才检测，那么目标结点到之前深度d时已经被扩展，此时为O(b^(d+1))空间复杂度O(b^d)，有O(b^(d-1))个结点在搜索集中，O(b^d)个结点在边缘集中。默认：Timeandspacecomplexityis1+b+…+b^d=O(b^d)
使用FIFO队列实现一个简单二叉搜索树的搜索过程：
一致代价搜索（Uniform-costSearch）每一步的行动代价都相等时，BFS是最优的。因为它总是选择先扩展深度最浅但是未扩展的结点。a)概念：扩展的是路径消耗g(n)最小的结点n（g(n)指从初始状态到该结点的路径消耗）。这可以通过将边缘结点按路径代价g值进行排序的队列来实现b)评价：
完备的（如果每一步代价都大于等于某个小的正值常数）；最优的；时间复杂度和空间复杂度在最坏情况均比宽度优先搜索大（因为可能搜索一些对结果无用的树，一致代价搜索可能会检查目标深度所有结点看谁的代价小，在这种情况下一致搜索在深度d无意义地做了更多的工作）。c)特点（和BFS的区别）
将边缘结点按路径代价g值进行排序的队列来实现目标检测应用于结点被选择拓展时，而不是在结点生成的时候如果边缘中的节点有更好的路径到达该节点，则会引入一个测试例子：考虑下图（初始状态S，目标状态G）
树搜索
图搜索
深度优先搜索(DFS)a)概念：总是扩展搜索树的当前边缘结点集（叶节点）中最深的结点。b)评价：
完备性：避免冗余路径和重复状态的图搜索，在有限空间中是完备的，但树搜索的DFS则不完备，有可能陷入死循环中。在无限状态空间中，则均可能陷入死循环中最优性：无论基于图搜索还是树搜索的DF算法都不是最优的时间复杂度O(b^m)受限于状态空间的规模（可能是无限的）；m:叶子结点的最大深度b:分支因子d:目标结点的最浅深度空间复杂度O(bm)（只需要存储一条从根结点到叶结点的路径，以及该路径上每个结点的所有未扩展的兄弟结点）；c)变形——回溯搜索：空间复杂度O(m)（每次只产生一个后继而不是生成所有后继，每个被部分扩展的结点要记住下一个要生成的结点）；d)使用LIFO队列实现（栈）
深度受限搜索(DepthLimitedSearch:DLS)a)概念：在深度优先搜索基础上设置界限l来避免无限状态空间深度优先搜索失败的问题（深度为l被当作没有后继对待）。b)评价：
完备的(l大于d)|不完备的(l小于d，则最浅的目标结点搜索不到)；不是最优的；时间复杂度O(b^l)；空间复杂度O(bl)；深度优先搜索可以看作是特殊的深度受限搜索，其深度l=∞深度受限搜索可以通过修改一般的树搜索或图搜索算法来实现。迭代加深的深度优先搜索(IterativeDeepeningSearch:IDS)定义：不断地增大深度限制，不断执行深度受限搜索。当深度界限达到d，即最浅的目标结点所在深度时，就能找到目标。性能：
完备性：分支引子b有限时完备最优性：路径代价是节点深度的非递减函数时最优空间复杂度：O(bd)d:thedepthoftheshallowestgoalnode问题：当深度为3时，有多少个结点被生成？
双向搜索(Bidirectionalsearch)定义：同时运行两个搜索，一个从初始状态向前搜索，另一个从目标状态向后搜索，目标检测是检查两个方向的边缘结点集是否相交，如果交集不为空就找到了解。理由是b(d/2)+b(d/2)要比b^d小很多。性能：
完备性：分支引子有限时完备最优性：不一定是最优的时空复杂度：O(b^(d/2))难点：如何向后搜索，部分问题可以向后搜索，但有些问题向后搜索会使得分子引子很大。
有信息的搜索策略（启发式搜索）有信息搜索：使用问题本身的定义之外的特定知识进行搜索评估函数f(n):代价估计最佳优先搜索的图搜索的实现与一直代价搜索类似，不过最佳优先是根据f值而不是g值进行优先级队列排队的启发式函数（heuristicfunction）：h(n)=结点n到目标结点的最小代价路径的代价估计值。若n是目标结点，则h(n)=0
f(n)：经过结点n的最小代价解的估计代价（有可能略小于真实代价）g(n)：到达此结点已经花费的真实代价h(n)：从该结点到目标结点所花代价Evaluationfunctionf(n)
f(n)=g(n)，UniformCost一直代价搜索f(n)=h(n)，GreedyBest-First贪婪最佳优先搜索f(n)=g(n)+h(n)，A*搜索贪婪最佳优先搜索定义：在每一步扩展时，都试图扩展离目标最近的结点。只用启发信息，f(n)=h(n)评价
完备性：不一定能找到解，容易钻进离目标节点近的死胡同。最优性：不一定是最优的，因为其贪婪地每次都寻找离目标结点最近的结点时空复杂度：罗马尼亚例子中，直线距离启发式hSLD均很小，O(h)，只搜索一条路径；但最坏情况下，O(b^m)，m是搜索空间的最大深度A*搜索：缩小总评估代价定义：f(n)=g(n)+h(n)，每次都选择扩展f(n)最小的结点，在扩展时检测是否到达目标f(n):经过结点n的最小代价解的估计值算法与一致代价搜索类似，除了A*使用g+h而不是g若启发式函数h(n)满足特定条件:A*搜索既是完备的也是最优的。
保证最优性的条件：
可采纳性：h(n)是一个可采纳启发式(admissible)，从不会高估到达目标的代价。例如直线距离启发式。一致性（单调性）：若对于每一个结点n和通过任一行动a生成的n的每个后继结点n’，从结点n到达目标的代价估计满足：h(n)