1 搜索相关概念

搜索算法是一个基本的计算机科学概念，作为开发人员应该理解。
它们通过使用分步方法在数据集合中查找特定数据来工作。

搜索也是人工智能解决问题的通用技术。有一些单人游戏，如瓷砖游戏、数独、填字游戏等。搜索算法可帮助您在此类游戏中搜索特定位置。

1.1 搜索术语

问题空间 - 它是进行搜索的环境。（一组状态和一组运算符来更改这些状态）

问题实例 − 它是初始状态 + 目标状态。

问题空间图 - 它表示问题状态。状态由节点显示，运算符由边显示。

问题的深度 − 从初始状态到目标状态的最短路径或最短运算符序列的长度。

空间复杂度 − 内存中存储的最大节点数。

时间复杂度 − 创建的最大节点数。

可接受性 − 算法始终找到最佳解决方案的属性。

分支因子 − 问题空间图中子节点的平均数。

深度 − 从初始状态到目标状态的最短路径长度。

1.2 搜索策略

1.2.1 暴力搜索

它们最简单，因为它们不需要任何特定于领域的知识。

它们在少量可能的状态下工作正常。

• 要求

        状态描述
        一组有效的运算符
        初始状态
        目标状态描述
  

1.2.1 广度优先搜索

它从根节点开始，首先探索相邻节点，然后向下一级邻居移动。

它一次生成一棵树，直到找到解决方案。它可以使用FIFO队列数据结构来实现。

此方法提供解决方案的最短路径。

如果分支因子（给定节点的平均子节点数）= b 且深度 = d，则级别 d 的节点数 = bd.

在最坏情况下创建的节点总数为 b + b2+ b3+ … + bd.

缺点 - 由于每个级别的节点都被保存用于创建下一个节点，因此会消耗大量内存空间。

存储节点的空间需求呈指数级增长。

其复杂性取决于节点的数量。它可以检查重复的节点。

1.2.2 深度优先搜索

它是使用LIFO堆栈数据结构在递归中实现的。
它创建与广度优先方法相同的节点集，只是顺序不同。

由于单个路径上的节点存储在从根节点到叶节点的每次迭代中，因此存储节点的空间要求是线性的。

分支因子 b 和深度为 m 时，存储空间为 bm。

缺点 - 此算法可能不会终止并在一条路径上无限运行。此问题的解决方案是选择截止深度。

如果理想的截止值为 d，并且选择的截止值小于 d，则此算法可能会失败。

如果选择的截止值大于 d，则执行时间增加。

其复杂性取决于路径的数量。它无法检查重复节点。

1.2.3 双向搜索

它从初始状态向前搜索，从目标状态向后搜索，直到两者相遇以识别共同状态。

从初始状态开始的路径与从目标状态开始的反向路径连接。每次搜索最多只能执行总路径的一半。

1.2.4 统一成本搜索

排序是在增加节点路径的成本的情况下完成的。

它始终扩展成本最低的节点。

如果每个转换具有相同的成本，则它与广度优先搜索相同。

它按成本递增顺序探索路径。

缺点 − 可能有多个长路径。统一成本搜索必须探索全部成员。

1.2.5 迭代深化深度优先搜索

它执行深度优先搜索到级别

1，重新开始，执行完整的深度优先搜索到级别 
2，并以这种方式继续，直到找到解决方案。

在生成所有较低节点之前，它永远不会创建节点。它只保存一堆节点。

当算法在深度 d 找到解决方案时结束。

在深度 d 处创建的节点数为 bd深度 d-1 处为 bD-1.

1.2.6 交互式深化DF搜索

各种算法复杂性的比较
让我们看看基于各种标准的算法的性能 -

标准		广度优先	深度优先	双向		制服成本	互动深化
时间		bd		bm		bD/2	bd		bd
空间		bd		bm		bD/2	bd		bd
最优		是的		不		是的		是的		是的
完整性	      是的		不		是的		是的		是的

知情（启发式）搜索策略为了解决具有大量可能状态的大问题，需要添加特定于问题的知识以提高搜索算法的效率。

启发式求值函数他们计算两个状态之间最佳路径的成本。

滑动图块游戏的启发式函数是通过计算每个图块从其目标状态进行的移动次数并将所有图块的移动次数相加来计算的。

1.2.7 纯启发式搜索

它按启发式值的顺序扩展节点。

它创建两个列表，一个用于已扩展节点的封闭列表，一个用于已创建但未展开的节点的开放列表。

在每次迭代中，将展开具有最小启发式值的节点，创建其所有子节点并将其放置在关闭列表中。

然后，将启发式函数应用于子节点，并根据其启发式值将它们放置在打开列表中。

保存较短的路径，处理较长的路径。

1.2.8 A * 搜索

这是最著名的最佳优先搜索形式。

它避免了扩展已经很昂贵的路径，而是首先扩展了最有前途的路径。

f（n） = g（n） + h（n），

其中

g（n） 到达节点的成本（到目前为止）
h（n） 从节点到目标的估计成本
f（n） 通过 n 到目标的路径的估计总成本。它通过增加 f（n） 使用优先级队列来实现。

它是贪婪的最佳第一搜索，它扩展估计最接近目标的节点。

它基于 f（n） = h（n） 扩展节点。它是使用优先级队列实现的。

缺点 - 它可能会卡在循环中。此时不是最佳的。

1.2.9 本地搜索算法

他们从预期解决方案开始，然后移动到相邻解决方案。

他们可以返回有效的解决方案，即使它在结束前的任何时间被中断。

1.2.10 爬山搜索 Hill-climbing search

它是一种迭代算法，从问题的任意解决方案开始，并尝试通过增量更改解决方案的单个元素来找到更好的解决方案。

如果更改产生了更好的解决方案，则增量更改将被视为新的解决方案。

重复此过程，直到没有进一步的改进。

它的缺点是可能找到局部最大，而不是全局最大。

函数爬坡（问题），返回一个局部最大值的状态。

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

缺点 - 此算法既不完整，也不是最佳的。

1.2.11 局部束搜索 Local beam search

在此算法中，它在任何给定时间都包含 k 个状态。

一开始，这些状态是随机生成的。

这些 k 状态的后继者是在目标函数的帮助下计算的。

如果这些后继函数中的任何一个是目标函数的最大值，则算法停止。

否则，（初始 k 个状态和状态的 k 个后继者数 = 2k）状态将放置在池中。

然后按数字对池进行排序。

选择最高的 k 个状态作为新的初始状态。此过程一直持续到达到最大值。

函数 BeamSearch（ problem， 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

1.2.12 模拟退火 Simulated annealing search

退火是加热和冷却金属以改变其内部结构以改变其物理性能的过程。

当金属冷却时，其新结构被锁定，金属保留其新获得的特性。

在模拟退火过程中，温度保持恒定。

我们最初将温度设置为高，然后随着算法的进行让它慢慢“冷却”。

当温度较高时，允许算法接受高频的差解。

模拟退火兼具爬山算法和随机行走(random walk)优点，同时满足效率和完备性要求。

想象在一个高低不平的平面有个乒乓球掉落到最深裂缝中，

如果只运行乒乓球运动，那么它将停留在局部极小点。

如果晃动平面，乒乓球可以弹出极小点。

诀窍是晃动幅度要足够大，让乒乓球弹出，但是又不能太大，从全局最小弹出。

退火算法就是开始用力晃，并慢慢减少晃的强度。

允许一些坏的移动，逐渐减少它们的频率，以概率突破局部最优，走向全局最优。

它的内循环类似爬山搜索，只是它没有选择最佳移动，而是随机移动。

如果该移动使情况改善，则移动被接受。

如果该移动使情况变坏，则算法以小于1的概率接受，

持续变坏将导致概率的指数级下降。

模拟退火在20世纪80年代用于求解VLSI的大规模集成电路的布局问题。

现在它被广泛应用在工厂调度和其他大型最优任务中。

这是一种逼近全局最优的算法，发布于1953年。

开始计算的步骤

1 初始化 k = 0;L = var 的整数数;
2 从 i → j 中，搜索性能差异 Δ。
3 如果 Δ <= 0，则接受否则，如果 exp(-Δ/T(k)) > rand(0，1) 则接受;
4 对 L(k)步骤重复步骤 1 和 2。
   k = k + 1;
重复步骤 1 到 4，直到满足条件。

1.2.13 遗传算法 Genetic algorithm

遗传算法在1960年代提出，在1970年代通过约翰霍兰的 《神经元和人工系统适应性》流行起来。

这是一种模仿自然的启发式算法。

该算法中，后继节点是由两个父辈状态的结合而不是单一修改生成的，处理过程是有性繁殖，不是无性繁殖。

该算法采用自然进化派生的技法生成优化问题的解，遗传，变异，选择，杂交。

它开始时具有一组k个随机生成的状态，称其为种群。

每个状态，或个体表示为有限字母的一个字符串，通常是0和1字符。

每个状态都由它的目标函数或适应度函数（遗传算法术语）给出评估值。

好的状态，适应度函数返回较高值。

• 相关基本概念：

    种群（Population）：指初始给定的多个解的集合。
    个体（Individual）：指种群中的单个元素，通常由一个用于描述其基本遗传结构的数据结构来表示。
    染色体（Chromosome）：指对个体进行编码后所得到的编码串。染色体中的每一位称为基因，染色体上由若干个基因构成的一个有效信息段称为基因组。例如：11011为一个染色体，每一位上的0或1表示基因。
    适应度（Fitness）函数：一种用来对种群中各个个体的环境适应性进行度量的函 数。其函数值是遗传算法实现优胜劣汰的主要依据。
    遗传操作（Genetic Operator）：指作用于种群而产生新的种群的操作。标准的遗传操作包括以下三种基本形式：
  
    	选择 Selection
    	交叉 Crossover
    	变异 Mutation
  

3 小结

任何解决搜索问题的算法，即检索存储在某个数据结构中的信息，或在问题域的搜索空间中计算的信息，无论是离散值还是连续值。

搜索算法旨在从存储元素的任何数据结构中检查或检索元素。他们在搜索空间中搜索目标（键）。

参考：

https://classes.engr.oregonstate.edu/eecs/spring2018/cs331/slides/LocalSearch.2pp.pdf