搜索问题（search problems）

不知情搜索

不知情搜索是问题和状态无关的。除了中间状态可能携带解决问题的信息，问题本身也会携带信息，针对这些信息，不知情搜索选择了忽视。

Depth-First Search(DFS)
Breadth-First Search(BFS)

知情搜索

在不知情搜索的基础上，知情搜索针对所要解决的某一个特定问题改进算法，并在一定程度上利用中间状态附带的信息。

Greedy Best-First Search(GBFS)

贪婪最佳优先搜索与DFS类似，所不同的是，DFS在遇到分岔路口时将随机选择一条路，而GBFS引入了启发式函数（heuristic function），启发式函数会根据当前状态所附带的信息对可能选择的分支进行评估，从而指导分支选择。

在迷宫问题中，我们可以使用GBFS。在直觉上，忽视墙体障碍的情况下，离目的地更近的点更有可能属于最优路径，因此可以使用曼哈顿距离（Manhattan distance）作为启发式函数h(n)，曼哈顿距离即两点间横纵坐标对应差的绝对值之和。

在迷宫问题中使用GBFS

当达到某一个分岔路口时，如果一个分叉走向A(x_1, y_1)，另一个分叉走向B(x_2, y_2)，而目的地为D(x, y)，那么分别有d_1=|x-x_1|+|y-y_1|，d_2=|x-x_2|+|y-y_2|，倘若d_1 < d_2，那么认为A(x_1, y_1)更接近终点，更有可能属于最优路径，于是走向A，反之走向B。

如图，已初始化了每一个可到达点的曼哈顿距离

遇到分岔路口时，根据启发式函数做出选择，这里启发式函数推荐走曼哈顿距离小的分支。

尽管知情搜索更多地利用了问题的信息，并希望我们能走向更优的路径，但也不排除在某种情况下知情搜索的效果反而不如不知情搜索。

*A Search**

A*搜索是GBFS的改进版，在启发式函数h(n)的基础上，引入了g(n)对从出发点到当前位置的cost进行记录。因此，结合启发式函数对不同分支的评估和g(n)给出的不同分支的cost共同指导分支的选择。如果说f(n)是告诉我们哪些选择具有更好的前途，那么g(n)则是告诉我们做出这些选择所要付出的代价。

例如，面前同时有A，B，C三个分支，h(n)告诉我们选A分支能更接近目的地，g(n)告诉我们选B分支距离出发点的cost最小，但结合f(n)和g(n)，则是C分支的综合表现最好，因此我们选择C分支。

**在迷宫问题中使用A*搜索**

如图，已初始化了每一个可到达点的曼哈顿距离，g(n)表示已走过的步数，用g(n)+h(n)作为分支选择的综合考量。

对抗搜索(Adversarial Search)

在对抗搜索中，搜索算法将会面对一个与自己有着相反目的的对手，算法不仅要考虑当前状态，还要考虑对手的行动对状态的影响。对抗搜索常常被用在带有对抗性的游戏中，例如井字棋。

Minimax

在对抗类游戏中，一方的有利常常意味着另一方的有害，因此同一个状态对于对抗双方的利害性是相反的。每一个状态都反映了对抗中当前的优势方和劣势方，如果将局势量化为数值，将Max玩家的优势用正数表示，那么Max玩家总是希望得到更高的分数，反之，Min玩家则总是希望得到更小的分数。

例如，Max玩家当前有3个选择，A，B，C，三种状态对应的局势数值分别是0，-1，1，那么Max玩家会做出选择C。

问题是，A，B，C三个选择的局势数值从何而来？

现在假设当Max做出选择A后进入状态S，而接下来该Min玩家做出选择。在状态S下，Min玩家一共有两个选择D，E。选择D之后轮到Max玩家，Max有唯一选择F，Max获胜，这意味着F选择的局势数值是1，那么D选择的局势数值也是1。选择E之后轮到Max玩家，Max玩家有唯一选择G，选择G意味着平局，说明G选择的局势数值是0，那么F选择的局势数值也是0。当F，G都意味着游戏的结束时，那么F，G所对应的状态的局势数值则是完全可信任的，相应的，D，E所对应的局势数值也是完全可信任的，Min一定会选择E。这就意味着如果Max玩家选择了A，Min玩家就一定会选择E，游戏结束时的局势数值一定是0，那么A选择的局势数值为0，同理B，C。

Depth-Limited Minimax

然而，从当前状态一直搜索到最终状态在时间和空间上都是不现实的，因此，搜索的深度往往是受到限制的。由于我们无法搜索到最终状态，我们的局势数值并不能简单地由输赢来给出，而是通过设计一个评估函数对当前状态的局势进行评估和打分。当然，评估函数给出的局势数值并非完全准确，这取决于评估函数设计的合理与否。或者说，评估函数的好坏决定了局势数值的准确性的下限，而当前状态所携带的有限的信息则决定了评估函数所能给出的局势数值的准确性的上限。