Artificial Intelligence 简明教程
AI - Popular Search Algorithms
搜索是人工智能中解决问题的一种通用技术。它包括一些单人游戏，如棋牌类游戏、数独、填字游戏等。搜索算法可以帮助你在这些游戏中搜索特定位置。
Single Agent Pathfinding Problems
3X3 八方棋、4X4 十五方棋和 5X5 二十四方棋之类的游戏是单代理寻径难题。它们包含一个带空格的瓷砖矩阵。玩家需要通过将瓷砖垂直或水平地滑入空格中来排列瓷砖，以达到实现某个目标的目的。
单代理寻径问题的其他示例包括旅行商问题、魔方和定理证明。
Search Terminology
-
Problem Space − 它是在其中执行搜索的环境。（状态集合和用于更改这些状态的运算符集合）
-
Problem Instance − 它等于初始状态 + 目标状态。
-
Problem Space Graph − 它表示问题状态。状态显示为节点，而运算符显示为边。
-
Depth of a problem − 从初始状态到目标状态的最短路径的长度或最短运算符序列的长度。
-
Space Complexity − 存储在内存中的最大节点数。
-
Time Complexity − 创建的最大节点数。
-
Admissibility − 算法始终找到最优解的特性。
-
Branching Factor − 问题空间图中子节点的平均数。
-
Depth − 从初始状态到目标状态的最短路径的长度。
Brute-Force Search Strategies
它们非常简单，因为它们不需要任何特定领域的知识。它们在可能的状态较少时工作正常。
要求 −
-
State description
-
一组有效运算符
-
Initial state
-
Goal state description
Breadth-First Search
它从根节点开始，首先探索相邻节点，然后转向下一级邻域。它一次生成一棵树，直到找到解决方案。它可以使用 FIFO 队列数据结构实现。该方法提供了解决方案的最短路径。
如果 branching factor （给定节点的平均子节点数）= b 且深度 = d，则第 d 级节点数 = bd。
在最坏情况下创建的节点总数为 b + b2 + b3 + … + bd。
Disadvantage − 由于每级节点都将用于创建下一级节点，因此会占用很多内存空间。存储节点所需的空间呈指数级增长。
其复杂度取决于节点数目。它可以检查重复节点。
Depth-First Search
它通过 LIFO 栈数据结构在递归中实现。它创建与广度优先方法相同的一组节点，只是顺序不同。
由于每个迭代中从根节点到叶节点都会存储在单一路径上的节点，因此存储节点所需的空间是线性的。当分支系数为 b、深度为 m 时，存储空间为 bm。
Disadvantage − 该算法可能不会终止，而会在一条路径上无限延续。解决此问题的方法是选择截止深度。如果理想的截止深度为 d，而所选的截止深度小于 d，则此算法可能会失败。如果所选的截止深度大于 d，则执行时间会增加。
其复杂度取决于路径数目。它不能检查重复节点。
Uniform Cost Search
按照到达节点的路径成本递增进行排序。它始终展开成本最低的节点。如果每个转换都有相同的成本，则它与广度优先搜索相同。
它按照成本递增的顺序探索路径。
Disadvantage − 可能会存在多条成本 ≤ C* 的长路径。一致代价搜索必须探索所有这些路径。
Informed (Heuristic) Search Strategies
要解决具有大量可能状态的大型问题，需要增加特定于问题的信息，以提高搜索算法的效率。
Heuristic Evaluation Functions
它们计算两个状态之间最佳路径的成本。通过计算每个图块从其目标状态所进行的移动数量，并为所有图块添加这些移动数量，即可计算出滑动拼图游戏的试探函数。
Pure Heuristic Search
它按照试探值来展开节点。它创建两个列表：已展开节点的封闭列表和已创建但未展开节点的开放列表。
在每个迭代中，展开一个具有最小试探值的节点，创建并置于封闭列表中其所有子节点。然后，将试探函数应用到子节点，并根据它们的试探值将它们置于开放列表中。较短的路径将会保存，而较长的路径则会被丢弃。
Local Search Algorithms
它们从可能的解决方案开始，然后移至相邻的解决方案。即使在它们结束之前在任何时候中断，它们也可以返回一个有效解决方案。
Hill-Climbing Search
它是一种迭代算法，从问题的任意解决方案开始，并尝试通过逐个增量地更改解决方案的一个元素来找到一个更好的解决方案。如果该更改产生了更好的解决方案，则将增量更改视为一个新的解决方案。此过程将重复进行，直到不再有进一步的改进。
函数 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
endDisadvantage − 此算法既不完整，也不是最优的。
Local Beam Search
在此算法中，它在任何给定时间都保存 k 个状态。在开始时，这些状态是随机生成的。这些 k 个状态的后继状态是借助于目标函数计算得出的。如果这些后继状态中的任何一个是目标函数的最大值，则算法停止。
否则（最初的 k 个状态和 k 个状态的后继状态 = 2k）个状态被置于一个池中。然后，对池进行按数字排序。最高 k 个状态被选择为新的初始状态。此过程一直持续到达到最大值。
函数 BeamSearch(问题，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
endSimulated Annealing
退火是加热和冷却金属以更改其内部结构，从而改变其物理特性的过程。当金属冷却时，其新的结构会凝结，该金属会保持其新得到的特性。在模拟退火过程中，温度保持可变。
我们最初将温度设置得很高，然后随着算法的进行，我们允许它慢慢“冷却”。在温度高时，算法通常会接受较差的解决方案。
开始
-
初始化 k = 0；L = 整数变量数；
-
从 i → j，搜索性能差异 Δ。
-
如果 Δ ⇐ 0 则接受，否则如果 exp(-Δ/T(k)) > random(0,1)，则接受；
-
对 L(k) 个步骤重复步骤 1 和 2。
-
k = k + 1；
对步骤 1 至步骤 4 执行重复操作，直至达到标准。
结束
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