Artificial Intelligence 简明教程

AI - Popular Search Algorithms

搜索是人工智能中解决问题的一种通用技术。它包括一些单人游戏，如棋牌类游戏、数独、填字游戏等。搜索算法可以帮助你在这些游戏中搜索特定位置。

Searching is the universal technique of problem solving in AI. There are some single-player games such as tile games, Sudoku, crossword, etc. The search algorithms help you to search for a particular position in such games.

Single Agent Pathfinding Problems

3X3 八方棋、4X4 十五方棋和 5X5 二十四方棋之类的游戏是单代理寻径难题。它们包含一个带空格的瓷砖矩阵。玩家需要通过将瓷砖垂直或水平地滑入空格中来排列瓷砖，以达到实现某个目标的目的。

The games such as 3X3 eight-tile, 4X4 fifteen-tile, and 5X5 twenty four tile puzzles are single-agent-path-finding challenges. They consist of a matrix of tiles with a blank tile. The player is required to arrange the tiles by sliding a tile either vertically or horizontally into a blank space with the aim of accomplishing some objective.

单代理寻径问题的其他示例包括旅行商问题、魔方和定理证明。

The other examples of single agent pathfinding problems are Travelling Salesman Problem, Rubik’s Cube, and Theorem Proving.

Search Terminology

  1. Problem Space − It is the environment in which the search takes place. (A set of states and set of operators to change those states)

  2. Problem Instance − It is Initial state + Goal state.

  3. Problem Space Graph − It represents problem state. States are shown by nodes and operators are shown by edges.

  4. Depth of a problem − Length of a shortest path or shortest sequence of operators from Initial State to goal state.

  5. Space Complexity − The maximum number of nodes that are stored in memory.

  6. Time Complexity − The maximum number of nodes that are created.

  7. Admissibility − A property of an algorithm to always find an optimal solution.

  8. Branching Factor − The average number of child nodes in the problem space graph.

  9. Depth − Length of the shortest path from initial state to goal state.

Brute-Force Search Strategies

它们非常简单，因为它们不需要任何特定领域的知识。它们在可能的状态较少时工作正常。

They are most simple, as they do not need any domain-specific knowledge. They work fine with small number of possible states.

要求 −

Requirements −

  1. State description

  2. A set of valid operators

  3. Initial state

  4. Goal state description

Breadth-First Search

它从根节点开始，首先探索相邻节点，然后转向下一级邻域。它一次生成一棵树，直到找到解决方案。它可以使用 FIFO 队列数据结构实现。该方法提供了解决方案的最短路径。

It starts from the root node, explores the neighboring nodes first and moves towards the next level neighbors. It generates one tree at a time until the solution is found. It can be implemented using FIFO queue data structure. This method provides shortest path to the solution.

如果 branching factor （给定节点的平均子节点数）= b 且深度 = d，则第 d 级节点数 = bd。

If branching factor (average number of child nodes for a given node) = b and depth = d, then number of nodes at level d = bd.

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

The total no of nodes created in worst case is b + b2 + b3 + … + bd.

Disadvantage − 由于每级节点都将用于创建下一级节点，因此会占用很多内存空间。存储节点所需的空间呈指数级增长。

Disadvantage − Since each level of nodes is saved for creating next one, it consumes a lot of memory space. Space requirement to store nodes is exponential.

其复杂度取决于节点数目。它可以检查重复节点。

Its complexity depends on the number of nodes. It can check duplicate nodes.

breadth first search

Depth-First Search

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

It is implemented in recursion with LIFO stack data structure. It creates the same set of nodes as Breadth-First method, only in the different order.

由于每个迭代中从根节点到叶节点都会存储在单一路径上的节点，因此存储节点所需的空间是线性的。当分支系数为 b、深度为 m 时，存储空间为 bm。

As the nodes on the single path are stored in each iteration from root to leaf node, the space requirement to store nodes is linear. With branching factor b and depth as m, the storage space is bm.

Disadvantage − 该算法可能不会终止，而会在一条路径上无限延续。解决此问题的方法是选择截止深度。如果理想的截止深度为 d，而所选的截止深度小于 d，则此算法可能会失败。如果所选的截止深度大于 d，则执行时间会增加。

Disadvantage − This algorithm may not terminate and go on infinitely on one path. The solution to this issue is to choose a cut-off depth. If the ideal cut-off is d, and if chosen cut-off is lesser than d, then this algorithm may fail. If chosen cut-off is more than d, then execution time increases.

其复杂度取决于路径数目。它不能检查重复节点。

Its complexity depends on the number of paths. It cannot check duplicate nodes.

depth first search

Bidirectional Search

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

It searches forward from initial state and backward from goal state till both meet to identify a common state.

从初始状态的路径与从目标状态的反向路径连接。每项搜索只进行到总路径的一半。

The path from initial state is concatenated with the inverse path from the goal state. Each search is done only up to half of the total path.

Uniform Cost Search

按照到达节点的路径成本递增进行排序。它始终展开成本最低的节点。如果每个转换都有相同的成本，则它与广度优先搜索相同。

Sorting is done in increasing cost of the path to a node. It always expands the least cost node. It is identical to Breadth First search if each transition has the same cost.

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

It explores paths in the increasing order of cost.

Disadvantage − 可能会存在多条成本 ≤ C* 的长路径。一致代价搜索必须探索所有这些路径。

Disadvantage − There can be multiple long paths with the cost ≤ C*. Uniform Cost search must explore them all.

Iterative Deepening Depth-First Search

它执行到第 1 级的深度优先搜索，然后重新开始，执行到第 2 级的完整深度优先搜索，并一直持续到找到解决方案。

It performs depth-first search to level 1, starts over, executes a complete depth-first search to level 2, and continues in such way till the solution is found.

在生成所有较低级别的节点之前，它永远不会创建节点。它只保存一个节点栈。该算法在深度处找到解决方案 d 时结束。在深度 d 处创建的节点数为 bd，在深度 d-1 处创建的节点数为 bd-1。

It never creates a node until all lower nodes are generated. It only saves a stack of nodes. The algorithm ends when it finds a solution at depth d. The number of nodes created at depth d is bd and at depth d-1 is bd-1.

interactive deepening df search

Comparison of Various Algorithms Complexities

让我们基于各种标准查看算法的性能 −

Let us see the performance of algorithms based on various criteria −

Criterion

Breadth First

Depth First

Bidirectional

Uniform Cost

Interactive Deepening

Time

bd

bm

bd/2

bd

bd

Space

bd

bm

bd/2

bd

bd

Optimality

Yes

No

Yes

Yes

Yes

Completeness

Yes

No

Yes

Yes

Yes

Informed (Heuristic) Search Strategies

要解决具有大量可能状态的大型问题，需要增加特定于问题的信息，以提高搜索算法的效率。

To solve large problems with large number of possible states, problem-specific knowledge needs to be added to increase the efficiency of search algorithms.

Heuristic Evaluation Functions

它们计算两个状态之间最佳路径的成本。通过计算每个图块从其目标状态所进行的移动数量，并为所有图块添加这些移动数量，即可计算出滑动拼图游戏的试探函数。

They calculate the cost of optimal path between two states. A heuristic function for sliding-tiles games is computed by counting number of moves that each tile makes from its goal state and adding these number of moves for all tiles.

Pure Heuristic Search

它按照试探值来展开节点。它创建两个列表：已展开节点的封闭列表和已创建但未展开节点的开放列表。

It expands nodes in the order of their heuristic values. It creates two lists, a closed list for the already expanded nodes and an open list for the created but unexpanded nodes.

在每个迭代中，展开一个具有最小试探值的节点，创建并置于封闭列表中其所有子节点。然后，将试探函数应用到子节点，并根据它们的试探值将它们置于开放列表中。较短的路径将会保存，而较长的路径则会被丢弃。

In each iteration, a node with a minimum heuristic value is expanded, all its child nodes are created and placed in the closed list. Then, the heuristic function is applied to the child nodes and they are placed in the open list according to their heuristic value. The shorter paths are saved and the longer ones are disposed.

A * Search

这是 A* 搜索中最著名的形式。它避免展开已经很昂贵的路径，但会首先展开最有希望的路径。

It is best-known form of Best First search. It avoids expanding paths that are already expensive, but expands most promising paths first.

f(n) = g(n) + h(n)，其中

f(n) = g(n) + h(n), where

  1. g(n) the cost (so far) to reach the node

  2. h(n) estimated cost to get from the node to the goal

  3. f(n) estimated total cost of path through n to goal. It is implemented using priority queue by increasing f(n).

Greedy Best First Search

它展开被估计为最接近目标的节点。它基于 f(n) = h(n) 来展开节点。它使用优先级队列来实现它。

It expands the node that is estimated to be closest to goal. It expands nodes based on f(n) = h(n). It is implemented using priority queue.

Disadvantage − 它可能会陷入循环。它不是最优的。

Disadvantage − It can get stuck in loops. It is not optimal.

Local Search Algorithms

它们从可能的解决方案开始，然后移至相邻的解决方案。即使在它们结束之前在任何时候中断，它们也可以返回一个有效解决方案。

They start from a prospective solution and then move to a neighboring solution. They can return a valid solution even if it is interrupted at any time before they end.

Hill-Climbing Search

它是一种迭代算法，从问题的任意解决方案开始，并尝试通过逐个增量地更改解决方案的一个元素来找到一个更好的解决方案。如果该更改产生了更好的解决方案，则将增量更改视为一个新的解决方案。此过程将重复进行，直到不再有进一步的改进。

It is an iterative algorithm that starts with an arbitrary solution to a problem and attempts to find a better solution by changing a single element of the solution incrementally. If the change produces a better solution, an incremental change is taken as a new solution. This process is repeated until there are no further improvements.

函数 Hill-Climbing (问题)，返回一个局部最大状态。

function Hill-Climbing (problem), returns a state that is a local maximum.

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

Disadvantage − 此算法既不完整，也不是最优的。

Disadvantage − This algorithm is neither complete, nor optimal.

Local Beam Search

在此算法中，它在任何给定时间都保存 k 个状态。在开始时，这些状态是随机生成的。这些 k 个状态的后继状态是借助于目标函数计算得出的。如果这些后继状态中的任何一个是目标函数的最大值，则算法停止。

In this algorithm, it holds k number of states at any given time. At the start, these states are generated randomly. The successors of these k states are computed with the help of objective function. If any of these successors is the maximum value of the objective function, then the algorithm stops.

否则（最初的 k 个状态和 k 个状态的后继状态 = 2k）个状态被置于一个池中。然后，对池进行按数字排序。最高 k 个状态被选择为新的初始状态。此过程一直持续到达到最大值。

Otherwise the (initial k states and k number of successors of the states = 2k) states are placed in a pool. The pool is then sorted numerically. The highest k states are selected as new initial states. This process continues until a maximum value is reached.

函数 BeamSearch(问题，k)，返回一个解决方案状态。

function BeamSearch( problem, k), returns a solution state.

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

Simulated Annealing

退火是加热和冷却金属以更改其内部结构，从而改变其物理特性的过程。当金属冷却时，其新的结构会凝结，该金属会保持其新得到的特性。在模拟退火过程中，温度保持可变。

Annealing is the process of heating and cooling a metal to change its internal structure for modifying its physical properties. When the metal cools, its new structure is seized, and the metal retains its newly obtained properties. In simulated annealing process, the temperature is kept variable.

我们最初将温度设置得很高，然后随着算法的进行，我们允许它慢慢“冷却”。在温度高时，算法通常会接受较差的解决方案。

We initially set the temperature high and then allow it to ‘cool' slowly as the algorithm proceeds. When the temperature is high, the algorithm is allowed to accept worse solutions with high frequency.

开始

Start

  1. Initialize k = 0; L = integer number of variables;

  2. From i → j, search the performance difference Δ.

  3. If Δ ⇐ 0 then accept else if exp(-Δ/T(k)) > random(0,1) then accept;

  4. Repeat steps 1 and 2 for L(k) steps.

  5. k = k + 1;

对步骤 1 至步骤 4 执行重复操作，直至达到标准。

Repeat steps 1 through 4 till the criteria is met.

结束

End

Travelling Salesman Problem

在此算法中，目标是找到一条低成本的路线，从一个城市开始，途中依次访问所有城市，并在同一起始城市结束。

In this algorithm, the objective is to find a low-cost tour that starts from a city, visits all cities en-route exactly once and ends at the same starting city.

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
travelling salesman