学号:17101223364
姓名:张海潮
转载自：http://m.manew.com/forum.php?mod=viewthread&tid=102750&mobile=2，有删节
【嵌牛导读】：
搜索是AI解决问题的通用技术。有一些单人游戏，如瓷砖游戏，数独，填字游戏等。搜索算法帮助您在这样的游戏搜索特定的位置。
【嵌牛鼻子】：人工智能 搜索 算法
【嵌牛提问】：典型的人工智能搜索算法有哪些？它们的特点是什么？
【嵌牛正文】：
单Agent寻路问题
譬如3X3， 4X4，5X5的瓷砖游戏都是单一Agent的寻路挑战。这些路径都是由一块块空白的瓷砖组成。玩家必须水平或者是垂直的移动这些瓷砖到空白的空间，来完成游戏目标。
其他的single agent寻路问题还有例如，旅行推销员问题，魔方以及定理证明类问题
搜索术语
Problem Space −这是搜索发生的环境（一组状态以及运算符来改变这些状态）Problem Instance −是初始状态+目标状态。
Problem Space Graph −代表问题状态。状态由结点表示，而运算符由边缘表示Depth of a problem —操作数从初始状态到目标状态长度最短的路径或者是最短的序列
·
·
Space Complexity −存储在内存中的最大节点数。
Time Complexity −创建的节点的最大数目
Admissibility −能解决问题的的最佳解决方案算法
Branching Factor − 在问题空间图表中子节点的平均数
Depth −从初始状态到目标状态的最短路径长度
Brute-强制搜索策略
他们是最简单的，因为他们不需要任何特定领域的知识。在可能状态很少的情乱他们可以最好的发挥性能
· 要求−
· ·状态描述
· ·一套有效的操作数
· ·初始状态
· ·目标状态描述
Breadth-优先搜索
它从根节点开始，起初探索相邻节点然后向下一级的相邻节点探索。它一次生成一棵树直到解决方案被发现。使用FIFO队列数据结构可以实现，这个方法提供了解决方案的最短路径
如果分支因子（对于一个给定的节点的子节点的平均数）=b，深度=d，那么d级别的节点数量= bd.
也就是说，在最坏的情况下，在这一级要创建的节点总数为 b + b2 + b3 + … + bd
缺点-因为每一级的节点将会被保留来创造下一级。它将消耗大量的内存空间。存储节点的空间需求是呈指数级增长的。
它的复杂性取决于节点的数量。它可以检查重复节点。
Depth-优先搜索
它实现了递归后进先出栈的数据结构。和Breadth-First方法相同，它创建了相同的一套节点，只不过有不同的顺序
由于单路径上的节点被存储在每次迭代从根到叶节点，存储节点的空间要求是线性的。分支因子带宽深度为 m，存储空间为 BM。
缺点-这个算法可能不会终止并且会在一个路径上无限2延伸。这个问题的解决方案是选择一个截止深度。如果给定一个截止深度cut-off isd，如果给定的截止深度小于d,那么这个算法有可能会失败。如果选择的截止深度超过d,那么执行的时间将会增加
其复杂性取决于路径数。它不能检查重复节点。
双向搜索
它从初始状态和目标状态向后搜索，直到两者达到共同状态。
从初始状态开始的路径被连接从目标状态出发的逆路径。每个搜索只完成了一半的总路径。
成本一致搜索
排序是以节点路径的成本增加为代价的。它总会引起最小成本节点的扩大。如果每个过度都有相同的成本，那么他和双向优先搜索是一致的
以增加开销为代价的情况下，成本一致搜索得以探索路径
缺点—可能存在很多长的路径开销≤ C*。而Uniform Cost search必须探索所有的路径。
迭代加深深度优先搜索
它执行深度优先搜索到1级，然后从头开始，以第2级执行一个完整的深度优先搜索，并继续以这种方式，直到找到解决方案。
它不会创建一个节点，直到所有较低的节点生成。它只保存一组节点。当它在深度 D发现一个解决方案时，算法结束.在深度 D 创建节点的数目是bd，深度 D-1 创建的节点为 bd-1
Informed（启发式）搜索策略
为了解决大的问题，大量的可能状态，需要添加特定问题的知识，以提高搜索算法的效率。
启发式评估功能
他们计算两个状态之间的最佳路径的成本。一个推箱子的启发函数通过计算每一个瓷砖从目标状态移动到现在的状态需要移动的数量，然后添加这些数量给所有的瓷砖。
纯粹的启发式搜索
它根据启发式值的顺序扩展节点。它创造了两个列表，一个未开放的列表给已经被扩展的节点和一个开放的列表对于已经创建但是还没有被扩展的节点
在每次迭代中，一个具有最小启发式值的节点被扩展，所有子节点都被创建并放置在封闭列表中。然后，启发式函数被施加到子节点，它们被放置在开放列表中，根据它们的启发式值。较短的路径被保存，较长的路径被处理。
A* 搜索
他是著名的最佳优先搜索策略。他避免了开销已经很昂贵的扩展路径，而是首先扩展最有可能的路径。
f(n) = g(n) + h(n), 其中
g(n)为到达节点的成本（到目前为止）
h(n)为从节点到目标的估计成本
f(n)为通过N到目标的估计总成本。它采用优先级队列来增加F（n）。
Greedy Best First Search
它扩展预估是最接近的目标的节点。它在f（n）= H（n）的基础上扩展节点。使用优先级队列实现。
缺点—他有可能陷在死循环，不是最优的方案
局部搜索算法
他们从一个前瞻性的解决方案开始，然后移动到邻近的解决方案。他们可以返回一个有效的解决方案，即使它在结束前的任何时候都可以被中断。
爬山搜寻法
它是一个迭代算法，从一个任意的问题的解决方案，并试图找到一个更好的解决方案，通过改变一个单一的元素增量的解决方案。如果变化产生更好的解决方案，增量变化作为一个新的解决方案。重复这个过程，直到没有进一步的改进。
function Hill-Climbing会返回一个局部最大值的状态
inputs: problem, a problem
local variables: current, a node
neighbor, a node
current <-Make_Node(Initial-State[problem])
loop
do neighbor <- a highest_valued successor of current
if Value[neighbor] ≤ Value[current] then
return State[current]
current <- neighbor
end
缺点 −这种算法既不完整，也不是最优的。
局部剪枝搜索
在该算法中，它持有k个数在任何给定的时间。在开始时，这些状态是随机生成的。这些K状态的继承人的计算与帮助的目标函数。如果这些后继的任何一个是目标函数的最大值，则该算法停止。
否则（初始状态k和k的状态的继任者= 2K）状态被放置在一个池。然后对池进行数值排序。最高k状态被选择为新的初始状态。这个过程一直持续直到达到最大值。
搜索功能（ 问题，K），返回一个解决状态。
start with k randomly generated states
loop
generate all successors of all k states
if any of the states = solution, then return the state
else select the k best successors
end
模拟退火法
退火是加热和冷却金属以改变其内部结构以改变其物理性质的过程。当金属冷却时，它的新结构被固定，金属保留其新获得的特性。在模拟退火过程中，温度保持不变。
· 开始
· Initialize k = 0; L = integer number of variables;
· From i → j, search the performance difference ∆.
· If ∆ <= 0 then accept else if exp(-D/T(k)) > random(0,1) then accept;
· Repeat steps 1 and 2 for L(k) steps.
· k = k + 1;
End
Travelling Salesman Problem
在该算法中，目标是找到一个低成本的路线，从一个城市开始，访问所有城市的路线完全一次，并在同一个起点城市结束行程。
Start
Find out all (n -1)! Possible solutions, where n is the total number of cities.
Determine the minimum cost by finding out the cost of each of these (n -1)! solutions.
Finally, keep the one with the minimum cost.
end
