深度理解基本图搜索算法

 

这篇随笔是在综合看了多本书，包括算法导论，人工智能等之后，写自己的一些感悟。

  适合的读者：如果你已经能够思路清晰的回答以下问题，那么请直接忽略本文~

l  A*，BFS,DFS算法的实现思路？

l  A*，BFS,DFS算法本质上最主要的不同点？

以上可以看做是随便的摘要，将从以下几个部分展开：

1. 图的基本表示
2. 图搜索问题本身的抽象
3. 图搜索三种基本算法，BFS,DFS,A*的实现。
4. 三种算法进一步抽象理解，以及简单扩展。

 

一．      图的基本表示方法

  既然文章主要讨论的是图的搜索算法，那么我们首先来看图在计算机中的表示方法，主要以下两种：

1. 邻接表
2. 邻接矩阵

这个部分比较基础，我简单说一下。

 

 

二．      图搜索

状态机理论上来说，把每个图看成是一个状态，那么图搜索便是这样一个问题，从起始状态，经过一系列的转移（或者说操作），达到最终状态。

在这么一个过程中，可以从很多面引出很多问题。主要会有从以下几个方面产生问题：

1. 关于操作。例如操作的最小次数（最大次数，或者某个适合的次数），操作的最小代价等等。
2. 关于状态。例如是否每个初始状态都有最终状态可达，有几个初始状态可达最终状态，能达几个最终状态等等。

 

这个过程，加上以上两条之一做为约束之后便能形成一个问题了，便是经常我们见到的形式，从A点到B点最快需要几个点，A点是否能到B点等等。

 

 

三．      图搜索的基本算法

我们都知道，算法是针对某个问题，或者某类问题存在的。在上一部分我们提出问题后，接下来进行解答，也就是算法部分的介绍。

在介绍具体算法之前，让我们先自己来想想如何解决此类问题，是否有一个相对抽象的模型（以下我们会看到，这也是这三个算法的基本模型），这将有助于我们对算法的理解，使得算法来的不那么“突然”。

为了方便模型的描述，我们将问题实例化为一个现实的例子，要从点A找到点B，你不能问路，只能自己“搜索”，你所知道的就是你现在的初始的位置A和目标B的样子，那么让我们开始：

图搜索解决思路\模型：

1. 记住前一步。当你走到新的一步的时候，要记得你是从哪走过来的，要不然等你走到了B点，却又不知道怎么走回去，便是白走了。
2. 判断当前一步。判断当前步是否为最终状态，如果是，就别再走了，沿路返回吧。
3. 走好下一步。当你有很多下一步的选择的时候，你需要去选择哪个作为你的下一步（这便是几个算法最大的不同），由于走错可以重来，倒也只是时间代价的问题。

不断重复以上三步，直到找到终点，或者你再也找不到可选的下一步了~~搜索便完毕了，这便是你能做的所有事情，是不是感觉很熟悉？其实人生也是一场搜索，记住过去，把握现在，规划未来~~~

 

扯远了，回到算法本身上来，既然我们已经抽象出算法模型，那么我们进一步将模型转到计算机领域相关内容上来。

1. 将当前一步的指针指向前一步，从而记录前一步的走法。
2. 将当前一步与最终点B进行对比，若相同，则通过每一步所留下的前一步的指针找回到初始位置便是一条路。
3. 把所有接下来可选的下一步列出来，作为下一步的参考方向。根据不同的算法，有不同的做法。

 

 

那么问题已经很清晰了，所有的算法基本上都只对第三步起作用，前两步是完全相同的，那么最基本的三种算法都做了哪些工作呢。

 

      广度优先算法（DFS）：

      我们直接根据上文考虑第三步，广度优先算法故名思意便是我从某点可能去的某个方向之后，返回前一个方向继续试没走过的方向，直到前一步能去的所有方向都试完之后才从另一个方向试，并且去过的我就不再傻傻的再去了。

      深度优先算法（DFS）：

      考虑第三步，深度优先算法故名思意便是我从某点可能去的方向挑一个去，并且下一步不返回原点，继续在走过的基础上再走下去，并且去过的我就不再傻傻的再去了。

      A*算法，又名启发式算法。

     考虑第三步，首先去过的地方我是不会再去了，然后可选的下一步地方我都列出来，通过某种科学的评估方式，判定哪个下一步比较靠谱，就走哪一步。

 

上面三种方法描述不够严谨，但是却很简明的体现出了这三种方法的特点，深度和广度优先算法都被称作盲目搜索，因为在选择下一步的时候只是通过自己的某种“习惯”作搜索而已，A*搜索通过了某种科学的评估方式，所以显得就比较“智能”了。

 

在网上有大量的关于深度优先，广度优先，A*算法的实现，案例，各种语言的代码，相信大家都能找到，所以本着“复用”的思想，就不在此做过多实现上的介绍。（算法导论书上的介绍非常详细和严谨，推荐）

 

四．      算法的扩展和提炼

其实文章到这里差不多结束了，但是还是有几点后续关注点和大家分享一下。

1. 关于第三步所走过的所有状态。

我们都知道，整个搜索过程中，可能我们只需要最终初始位置走向最终位置的那条路就好了。但是每个算法所走过的节点（正确的或者错误的），是可以记录下来，作为一种特殊的数据组织起来，通过这个特殊的数据，我们可以评判一个算法所经历的时间，错误节点数量，从而来评判一个算法的优劣。就像DEBUG，我们需要记录整个过程中的所有信息~~~

于是，广度优先算法在搜索过程中将形成广度优先树，深度优先算法在搜索过程更是能够形成括号结构的特殊性质，而A*所形成的搜索产物呢？是一个被完美剪支过后的树~~（A*搜索产物完全是个人看法的，不对欢迎讨论和指正）

    2.关于下一步的的选择，OPEN表。

实际上DFS用的是一个先进先出的队列结构来实现，BFS基本可以看成是先进后出的栈找下一步，而A*需要每次重新排序来确定下一步。

再通俗一点，如果读者对这三个算法有点熟悉的话，都知道在这个过程中需要两个关键的数据结构，分别来储存已经去过的点（名closed表），和可选的点（OPEN表），CLOSED表实现没什么特殊之处。

而OPEN表中,DFS是用队列，BFS用栈，而A*每次对OPEN进行重新排序。

      3.关于A*的评估函数

明眼人一下就看出来了，A*算法最关键的部分在于，那个评估函数究竟是什么？怎么样来确定一个好的评估函数便是用A*解决问题最关键的钥匙~~~，但是并不会有一个通用的函数，就像你在不同的地方需要不同的地图~~

当然还是会有很多经典的评估函数，例如用A*解决八数码问题所用到的评估函数等等……

 更多信息请查看 java进阶网 http://www.javady.com

评论

1 楼 502220545 2012-07-05  

记住过去，把握现在，规划未来  总结的经典