初窥Dijkstra算法、Bellman-Ford、SPFA算法、Floyd算法、迭代加深搜索、A*、IDA*

366

Dijlkstra算法



Dijkstra算法是一种常见的计算正权图上的单源最短路的算法,能同时用在有向图和无向图上。


>Dijkstra算法的解释<

其以BFS为基础进行优化。

BFS算法



宽度优先遍历算法,先从起点向周围拓展,再从拓展后的每个点向外拓展,如果某个节点已经访问过,则不再访问该节点。


由于每个节点只访问一次,并且按层逐层向外访问,因此第一次访问到终点时走过的路径就是最短路径。


可以用于无权图的最短路搜索。


通常使用循环队列进行搜索。



queue Q;
bool visited[maxn];
memset(visited,flase,sizeof(visited));

Q.push(v);
visited[v]=true;
while(!Q.empty()){
int it=Q.top();
Q.pop();

//拓展到终点
if(it==s){
...
break;
}

...//从it向外拓展到itn
if(!visited[itn])
Q.push(itn);
}


## DFS算法

> 深度优先遍历,从起点开始,沿着一条分支一直走到终点。

> 与BFS不同,DFS的在搜索最短路的大多数情况下,是不如BFS的,它更多是用在状态的转移上。

> 根据已有的状态向下一个状态进行转移。

> 在较为复杂的迷宫中(牵扯到时间、方向等各种复杂状态)时,用DFS来传递参数会更有优势

> 由于DFS强调的是状态的转移。因此,更多用递归来实现。

> ``` cpp
void DFS(...){
//不符合要求的拓展
if(...)
return;
//达到叶节点
if(...)
return;
...//向下拓展到itn(n=1、2、……)
DFS(it1);
...
DFS(itn);
}


当图为有权图时,如果我们想要走最短的路径,就要优先走权值更小的路,这样才能走出最小的解(可证明)

因此,在BFS中,我们在队列中不应该选取先进队的节点,而应该走权值最小的节点。

将BFS的队列(queue)改成优先队列(priority_queue)即可。

然后每次拓展节点后,更新每个节点的权值(取最小)

最后终点的权值就是最小路的距离。



Bellman-Ford算法



Dijkstra算法只适用于正权图上最短路,而Bellman-Ford还可计算副权存在时的最短路。

首先要明确:

  • 如果最短路存在,一定存在一个不含环的最短路。

  • 最短路最多只经过(不含起点)n-1个节点,可以通过n-1轮松弛操作得到。

将起点权值设置为0,其他点权值设置为无穷大。

循环节点个数-1次

  循环边的个数次(i)

    对第i条边进行松弛操作

    检测是否存在负权回路

      存在

       返回false

      不存在

       继续



SPFA算法



Bellman-Ford算法虽然解决了负权路的问题,但是其效率过于底下,并不常使用。

而SPFA算法,是其高效率的替代方法。

其与无权图的BFS较为相近。

不同的是,visited数组记录的不是是否已经访问过,而是是否在队列Q中

每次松弛操作更新估计值(d[i]),如果i点不在队列中,则要把i点入队

如果有边入队的次数超过N次,则说明存在负环。



Floyd算法



如果需要求出每两点之间的最短路,则可以使用Floyd算法,这是一个非常简洁的算法

不断进行松弛操作,即可得到最短路径

for(int k=0;k<n;k++)
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
```



迭代加深搜索、A\*、IDA\*是三种相似并且很有用的算法。

他们是一种解题的思路,并没有具体的实现代码,在脑海中有这种思路,有可能会帮助我们获取解题的思路

# 迭代加深搜索

迭代加深搜索是一种不断拓展搜索范围的搜索方式。

可以将其形象成一棵树,这棵树有无数层(深度无限深),每一层有无限个节点(无限广)

因此,无论是DFS还是BFS,都不能拓展一支,拓展一层。

而其答案可能就在第二层第二支上……

为了求解这种问题,有了迭代加深搜索。

顾名思义,迭代加深就是逐渐增加搜索的范围。

最初我们只搜索maxd的范围,当maxd内没有我们需要的答案时,我们将maxd+1,而后继续搜索。

``` cpp
for(maxd=1;;maxd++)
if(dfs(...))
break;
```

埃及分数问题,是经典的迭代加深问题

在古埃及,人们使用单位分数的和(形如 1/a 的,a 是正整数)表示一切有理数。

如:`2/3 = 1/2 + 1/6`,但不允许 `2/3 = 1/3 + 1/3`,因为加数中有相同的。

首先,加数少的比加数多的好,其次,加数个数相同的,最小的分数越大越好。

首先BFS无法求解这个问题,我们不知道有几个加数;其次DFS也不能求解这个问题,我们不知道加数没有最小值(分母可以无限大)。

因此,我们需要使用迭代加深算法。先让每个加数都大于1/10,进行DFS,如果没有答案,再搜索每个加数都大于1/20……



很显然,每次maxd的增加,都导致了重复搜索,不过相比搜索总数指数级的增加,重复搜索的这部分可以忽略……





# A*算法

A*算法,又称启发式搜索。

用公式表示为

> f(n)=g(n)+h(n)

其中

> f(n)是初始点经由节点n到目标点的估价函数

> g(n)是在状态空间中从初始节点到n节点的实际代价

> h(n)是从n到目标结点的最佳路径的估计代价

具体是什么意思呢,就是我们要优先选择一条我们估计最好的分支进行拓展,对于我们估计不是很好的分支进行剪枝。

由于最好只是我们的估计,因此,如果估计的不合理,可能会丢失最优解或者并没有有效提升效率。

与Dijkstra对比,我们可以发现,Dijkstra其实是简化的一种A*算法:

它与A*相比少了剪枝的部分,与BFS相比,多了估价的部分



# IDA*算法

将迭代加深的有上限的搜索和A*算法的剪枝与估价结合,就得到了IDA*算法

IDA*算法有以下优缺点:

* 优化了A*对空间的小号
* 在每一次迭代的过程中避免了判重
* 比普通的DFS相比更加明确目标,并能够有效剪枝
* 迭代加深会导致重复搜索内容
发布评论
  • 点击查看/关闭被识别为广告的评论