图形演算
简介
在离散数学、算法与人智能领域，很多问题可以表示成「节点与连线所形成的图形」，一个程序要解决某个问题其实是在这个图形里把目标节点给找出来，于是问题求解就简化成了图形的搜索，我们只要把解答给「找出来」就行了。
图形搜索的方法大致可以分为「深度优先搜寻(Depth-First Search, DFS)、广度优先搜寻(Breath-First Search, BFS)、最佳优先搜寻(Best-First Search, BestFS) 三类。
然后针对最佳优先搜寻的部份，还有一种具有理论背景，相对强大好用的A* 算法可用。
图形的表达
图形是由节点(node) 与连线(edge) 所组成的。举例来说，以下是一个包含六个节点与十条连线的简单图形：
深度优先搜寻
所谓的「深度优先搜寻」 (Depth-First Search, DFS)，就是一直往尚未访问过的第一个邻居节点走去的一种方法，这种方法可以采用程式设计中的「递归」完成，以下是深度搜寻的演算法：
function dfs(g, node) {
if (g[node].v !=0) return; // 如果已访问过，就不再访问
printf("%d=>", node); // 否则，打印节点
g[node].v = 1; // 并设定为已访问
var neighbors = g[node].n; // 取出相邻节点
for (var i in neighbors) { // 对于每个相邻节点逐一访问
}
}
针对上述的图形，若采用深度优先搜寻，其结果可能如下所示(图中红色的数字代表访问顺序)
广度优先搜寻
虽然深度优先搜寻可以搜寻整个图形，但是却很可能绕了很久才找到目标，于是从起点到目标可能会花费很久的时间(或说路径长度过长)。
如果我们想找出到达目标最少的步骤，那么就可以采用「广度优先搜寻」 (Breath-First Search, BFS) 的方式。
广度优先搜寻BFS 是从一个节点开始，将每个邻居节点都一层一层的拜访下去，深度最浅的节点会优先被拜访的方式。
举例而言，针对上述的图形示例，若采用「广度优先搜寻BFS 」的方式，那么拜访顺序将会如下所示：
要能用程式进行广度优先搜寻，必须采用「先进先出」(First-in First-Out, FIFO) 的方式管理节点，因此通常在「广度优先搜寻」里会有个伫列(queue) 结构，以下是BFS 的演算法片段：
function bfs(g, q) { // 广度优先搜索
if (q.length == 0) return; // 如果 queue 已空，则返回。
var node = dequeue(q); // 否则、取出 queue 的第一个节点。
if (g[node].v == 0) // 如果该节点尚未拜访过。
g[node].v = 1; // 标记为已拜访
else // 否则 (已拜访过)
return; // 不继续搜寻，直接返回。
printf("%d=>", node); // 印出节点
var neighbors = g[node].n; // 取出邻居。
for (var i in neighbors) { // 对于每个邻居
var n = neighbors[i];
if (!g[n].visited) // 假如该邻居还没有被拜访过
q.push(n); // 就放入 queue 中
}
bfs(g, q);
}
最佳优先搜寻
但是、上述两个方法其实都还不够好，深度搜寻会洪水猛兽一样乱冲乱撞，而广度搜寻则会耗费太多的资源，并且没有效率，无法很快的找到目标点。
假如我们能够知道哪些点距离目标点最近，也就是哪些点比较好的话，那就能采用「最佳优先搜寻(Best-First Search) 的方式来搜寻了。
最佳优先搜寻的实作方法与广度优先搜寻类似，但是并不采用伫列(queue) ，而是采用一种根据优先程度排序的结构，每次都取出最好的那个继续进行搜寻。
但是、节点的好坏通常很难评估，单纯采用某种距离去评估往往会过度简化问题，这点往往是最佳优先搜寻的困难之所在。
还好，有时我们不需要非常精确的评估，只要问题符合$h(x) \leq d(x,y) + h(y) $这样的单调(monotone)特性，就可以使用A算法来进行较快速的搜寻，这种方法比广度优先搜寻通常快很多，因为A不会搜寻所有节点，而是有系统的朝着整体较好的方向前进，这种方法在电脑游戏(Game)上常被用在NPC (非人类角色)的智慧型搜寻行为设计上面，是人工智慧搜寻方法中较强大的一种。
code enjoy! ٩(๑❛ᴗ❛๑)۶
作者：indeex
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。