黑马程序员技术交流社区

标题: 夜深人静写算法：搜索入门（2） [打印本页]

---

作者: hy2014051202    时间: 2017-7-16 18:47
标题: 夜深人静写算法：搜索入门（2）
4、基于DFS的A*（迭代加深，IDA*）

1) 算法原理

迭代加深分两步走：
1、枚举深度。
2、根据限定的深度进行DFS，并且利用估价函数进行剪枝。

2) 算法实现

迭代加深写成伪代码如下：

def IDA_Star(STATE startState):
maxDepth = 0
while true:
if( DFS(startState, 0, maxDepth) ):
return
maxDepth = maxDepth + 1
sousuo_8


图 8

3) 基础应用

如图8所示，一个“井”字形的玩具，上面有三种数字1、2、3，给出8种操作方式，A表示将第一个竖着的列循环上移一格，并且A和F是一个逆操作，B、C、D…的操作方式依此类推，初始状态给定，目标状态是中间8个数字相同。问最少的操作方式，并且要求给出操作的序列，步数一样的时候选择字典序最小的输出。图中的操作序列为AC。

大致分析一下，一共24个格子，每个格子三种情况，所以最坏情况状态总数为3^24，但实际上，我们可以分三种情况讨论，先确定中间的8个数字的值，假设为1的话，2和3就可以看成是一样的，于是状态数变成了2^24。

对三种情况分别进行迭代加深搜索，令当前需要搜索的中间8个数字为k，首先枚举本次搜索的最大深度maxDepth（即需要的步数），从初始状态进行状态扩展，每次扩展8个结点，当搜索到深度为depth的时候，那么剩下可以移动的步数为maxDepth – depth，我们发现每次移动，中间的8个格子最多多一个k，所以如果当前状态下中间8个格子有sum个k，那么需要的剩余步数的理想最小值s = 8 – sum，那么估价函数：

h = depth + (8 – sum)

当h > maxDepth时，表明在当前这种状态下，不可能在maxDepth歩以内达成目标，直接回溯。

当某个深度maxDepth至少有一个可行解时，整个算法也就结束了，可以设定一个标记，直接回溯到最上层，或者在DFS的返回值给定，对于某个搜索树，只要该子树下有解就返回1，否则返回0。

迭代加深适合深度不是很深，但是每次扩展的结点数很多的搜索问题。

二、广度优先搜索

1、BFS

1) 算法原理

广度优先搜索即Breadth First Search，也是图遍历算法的一种。用一句话概括就是：“我会分身我怕谁？！”。

BFS的具体算法描述为选择一个起始点v放入一个先进先出的队列中，执行如下操作：
a. 如果队列不为空，弹出一个队列首元素，记为当前结点，执行b；否则算法结束；
b. 将与 当前结点 相邻并且尚未被访问的结点的信息进行更新，并且全部放入队列中，继续执行a；

维护广搜的数据结构是队列和HASH，队列就是官方所说的open-close表，HASH主要是用来标记状态的，比如某个状态并不是一个整数，可能是一个字符串，就需要用字符串映射到一个整数，可以自己写个散列HASH表，不建议用STL的map，效率奇低。

广搜最基础的应用是用来求图的最短路。

如图9所示，对以下图进行广度优先搜索，假设起点为1，将它放入队列后。那么第一次从队列中弹出的一定是1，将和1相邻未被访问的结点继续按顺序放入队列中，分别是2、3、4、5、7，并且记录下它们距离起点的距离dis[x] = dis[1] + 1 (x 属于集合 {2, 3, 4, 5, 7})；然后弹出的元素是2，和2相邻未被访问的结点是10，将它也放入队列中，记录dis[10] = dis[2] + 1；然后弹出5，放入6（4由于已经被访问过，所以不需要再放入队列中）；弹出7，放入8、9。队列为空后结束搜索，搜索完毕后，dis数组就记录了起点1到各个点的最短距离；


图9

2) 算法实现

广搜一般用队列维护状态，写成伪代码如下：

def BFS(v):
resetArray(visited,false)
visited[v] = true
queue.push(v)
while not queue.empty():
v = queue.getfront_and_pop()
for u in adjcent_list[v]:
if visited[u] is false:
dosomething(u)
queue.push(u)

3) 基础应用

a. 最短路：bellman-ford最短路的优化算法SPFA，主体是利用BFS实现的。绝大部分四向、八向迷宫的最短路问题。
b. 拓扑排序：首先找入度为0的点入队，弹出元素执行“减度”操作，继续将减完度后入度为0的点入队，循环操作，直到队列为空，经典BFS操作；
c. FloodFill：经典洪水灌溉算法；

4) 高级应用

a. 差分约束：数形结合的经典算法，利用SPFA来求解不等式组。
b. 稳定婚姻：二分图的稳定匹配问题，试问没有稳定的婚姻，如何有心思学习算法，所以一定要学好BFS啊；
c. AC自动机：字典树 + KMP + BFS，在设定失败指针的时候需要用到BFS。详细算法参见：http://www.cppblog.com/menjitianya/archive/2014/07/10/207604.html
d. 矩阵二分：矩阵乘法的状态转移图的构建可以采用BFS；
e. 基于k进制的状态压缩搜索：这里的k一般为2的幂，状态压缩就是将原本多维的状态压缩到一个k进制的整数中，便于存储在一个一维数组中，往往可以大大地节省空间，又由于k为2的幂，所以状态转移可以采用位运算进行加速，HDU1813和HDU3278以及HDU3900都是很好的例子；
f. 其它：还有好多，一时间想不起来了，占坑；

2、基于BFS的A*

1) 算法原理

在搜索的时候，结点信息要用堆（优先队列）维护大小，即能更快到达目标的结点优先弹出。

2) 基础应用

a.八数码问题
如图10所示，一个3*3的棋盘，放置8个棋子，编号1-8，给定任意一个初始状态，每次可以交换相邻两个棋子的位置，问最少经过多少次交换使棋盘有序。


图10

遇到搜索问题一般都是先分析状态，这题的状态数可以这么考虑：将数字1放在九个格子中的任意一个，那么数字2有八种摆放方式，3有七种，依此类推；所以状态总数为9的排列数，即9!（9的阶乘） = 362880。每个状态可以映射到0到362880-1的一个整数，对于广搜来说这个状态量不算大，但是也不小，如果遇到无解的情况，就会把所有状态搜遍，所以这里必须先将无解的情况进行特判，采用的是曼哈顿距离和逆序数进行剪枝，具体参见 SGU 139的解法：
http://www.cppblog.com/menjitianya/archive/2014/06/23/207386.html

网上对A*的描述写的都很复杂，我尝试用我的理解简单描述一下，首先还是从公式入手：
f(state) = g(state) + h(state)

g(state)：表示从初始状态 到 state 的实际行走步数，这个是通过BFS进行实时记录的，是一个已知量；
h(state)：表示从 state 到 目标状态 的期望步数，这个是一个估计值，不能准确得到，只能通过一些方法估计出一个值，并不准确；
f(state)：表示从 初始状态 到 目标状态 的期望步数，这个没什么好说的，就是前两个数相加得到，也肯定是个估计值；

对于广搜的状态，我们是用队列来维护的，所以state都是存在于队列中的，我们希望队列中状态的f(state)值是单调不降的（这样才能尽量早得搜到一个解），g(state)可以在状态扩展的时候由当前状态的父状态pstate的g(pstate)+1得到；那么问题就在于h(state)，用什么来作为state的期望步数，这个对于每个问题都是不一样的，在八数码问题中，我们可以这样想：

这个棋盘上每个有数字的格子都住了一位老爷爷 （-_-|||），每位老爷爷都想回家，老爷爷的家就对应了目标状态每个数字所在的位置，对于 i 号老爷爷，他要回家的话至少要走的路程为当前状态state它在的格子pos[i] 和 目标状态他的家target[i] 的曼哈顿距离。每位老爷爷都要回家，所以最少的回家距离就是所有的这些曼哈顿距离之和，这就是我们在state状态要到达目标状态的期望步数h(state)，不理解请回到两行前再读一遍或者看下面的公式。

h(state) = sum( abs(pos[i].x – (i-1)/3) + abs(pos[i].y – (i-1)%3) ) (其中 1 <= i <= 8, 0 <= pos[i].x, pos[i].y < 3 )
最后附上原题链接：http://acm.hdu.edu.cn/showproblem.php?pid=1043

b.K短路问题
求初始结点到目标结点的第K短路，当K=1时，即最短路问题，K=2时，则为次短路问题，当K >= 3时需要A*求解。还是一个h(state)函数，这里可以采用state到目标结点的最短距离为期望距离；附上原题链接：http://poj.org/problem?id=2449

3、双向广搜

1) 算法原理

初始状态 和 目标状态 都知道，求初始状态到目标状态的最短距离；利用两个队列，初始化时初始状态在1号队列里，目标状态在2号队列里，并且记录这两个状态的层次都为0，然后分别执行如下操作：

a.若1号队列已空，则结束搜索，否则从1号队列逐个弹出层次为K(K >= 0)的状态；
i. 如果该状态在2号队列扩展状态时已经扩展到过，那么最短距离为两个队列扩展状态的层次加和，结束搜索；
ii. 否则和BFS一样扩展状态，放入1号队列，直到队列首元素的层次为K+1时执行b；

b.若2号队列已空，则结束搜索，否则从2号队列逐个弹出层次为K(K >= 0)的状态；
i. 如果该状态在1号队列扩展状态时已经扩展到过，那么最短距离为两个队列扩展状态的层次加和，结束搜索；
ii. 否则和BFS一样扩展状态，放入2号队列，直到队列首元素的层次为K+1时执行a；

如图11，S表示初始状态，T表示目标状态，红色路径连接的点为S扩展出来的，蓝色路径连接的点为T扩展出来的，当S扩展到第三层的时候发现有一个结点已经在T扩展出来的集合中，于是搜索结束，最短距离等于3 + 2 = 5；


图11

双广的思想很简单，自己写上一两个基本上就能总结出固定套路了，和BFS一样属于盲搜。

---

作者: hy2014051202    时间: 2017-7-16 18:48
发生了什么事情，，，，，我上传的图片不见了

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2