免费免费建网站,网站备案信息模板,海口网络推广,关于医院网站建设的通知一、bellman_ford
1. 是什么松弛
在《算法四》中#xff0c;对松弛的解释是#xff1a;relax the edge#xff0c;看起来比较抽象#xff0c;不过如果我们从生活中的实例去理解#xff0c;就简单多了#xff1a; 试想一根绳索#xff0c;当你握着绳索的两头使劲用力拉…一、bellman_ford
1. 是什么松弛
在《算法四》中对松弛的解释是relax the edge看起来比较抽象不过如果我们从生活中的实例去理解就简单多了 试想一根绳索当你握着绳索的两头使劲用力拉伸时绳子紧绷长度会变长而当你减小用力时绳子松弛长度会变短。当你没有用任何力时此时绳子的长度最短。 这里当用力减小时绳子收到的拉力减小进而长度变短的过程就是“松弛的过程” 体现在图论中就是对于任意边 a-b所谓的松弛操作就是通过 dist[b]min(dist[b], dist[a]g[a][b]) 来更新最短路的过程。 通过松弛操作绳子变短即起点到终点的距离逐渐趋近于最短路。 所以说图论中常说的松弛操作就是一个“比喻”说法。它将最短路和绳子做类比。很有意思 在不同的算法中松弛的具体操作形式可能不同不过它们的本质都是相同的那就是减小起点到终点的距离使其最终趋近于最短路。
2. 限定最短路的边数
为什么 bellman_ford 算法的松弛操作可以限定最短路 从图中我们就可以发现对所有边的松弛过程有点像“层序遍历”的过程具体来说以起点为出发点的层次遍历我们每次从上一轮拓展出的结点出发拓展下一个相邻的结点。形式上就相当于多走了一条边。对于图示就是 第一轮从起点1拓展23 第二轮从23拓展出45 第三轮从45拓展出36 可以发现3被拓展了两次 通过这我们也能证明出 bellman_ford 算法的正确性只要我们松弛 n-1 次那么就一定能得到起点到终点的最短路。因为此时我们是相当于枚举了所有从起点走到终点的情况。 即先枚举走 1 条边到终点的情况再枚举走 2 条边到终点的情况…最后枚举走 n-1 条边到终点的情况。并且对于走 k 条边的情况还会枚举所有可能的路线最后对其结果取最小值。 但是这也说明了bellman_ford 求最短路的过程是 “暴力枚举”因此它的时间效率不高。主要用于限定边数的最短路。
3. 不可达的点
对于不可达的点我们的松弛会导致从起点到该点的距离减小。例如我们只有一条边 2-3权值为 -1那么松弛之后将导致 dist[3]dist[2]-1。在初始状态下dist[2]dist[3]INF。 你可能很聪明的想到哎按你这么说bellman_ford 算法看起来完全不像层次遍历了啊因为在初始状态下我们只拓展了起点1它可以不从起点进行拓展呀2-3。 没错但问题是不从起点上一轮拓展的点开始拓展的点是无意义的因为我们不能保证其可达性就如我们上面的说的1-2 和 1-3 都不可达那么从 2 开始拓展 3 有什么意义呢
二、spfa
SPFA算法Shortest Path Faster Algorithm也称为 bellman_ford 队列优化算法。 SPFA的称呼来自 1994年西南交通大学段凡丁的论文其实Bellman_ford 提出后不久 20世纪50年代末期 就有队列优化的版本国际上不承认这个算法是是国内提出的。 所以国际上一般称呼 该算法为 Bellman_ford 队列优化算法Queue improved Bellman-Ford 1. spfa优化了什么
在上面 bellman_ford 算法中每一轮松弛需要对所有边进行操作时间复杂度为 O(M)效率很低。 但其实就如我们上面所提到的每次松弛看起来就是层序遍历而对于层序遍历来说每一次只需要从最末端元素开始遍历即可之前已经遍历过的元素就无需再遍历了。 其实这里的松弛操作也是类似的对于 1-2 这条边我们只需要在第一轮遍历即可在第二轮和第三轮中就无需对这条边进行松弛了因为 dist[a] 值已经确定了它不会在变化。 由此可见每一轮都枚举所有边是无意义的。并且我们可以总结出对于 a-b 这条边只要当 dist[a] 发生变化时松弛这条边才有意义。否则如果 dist[a] 不变那么 dist[a]g[a][b] 也不变判断 dist[a]g[a][b] 和 dist[b] 的大小从而进行松弛就完全没有意义了。 因此我们可以用一个队列来保存这些 dist 发生变化的起始点 a然后只对以 a 为起点的边进行松弛操作。这就是队列优化的 bellman_ford 算法。
同样我们可能理解为什么在 spfa 中一个点可以多次入队了就如我们上面说的对于 2-5 这条边我们需要在第二轮和第三轮时进行遍历。由于它需要分别在两轮进行松弛操作那么 2 这个点就需要入队两次。每次入队就相当于一轮松弛。 同样的我们也能解释为什么 spfa 一个点不可达但是从起点到他的距离变小了因为 spfa 本质上就是 bellman_ford 啊所以他继承了 bellman_ford 的这个问题。
2. 时间复杂度
如何设计卡掉spfa的数据 队列优化版Bellman_ford 的时间复杂度 并不稳定效率高低依赖于图的结构。 例如 如果是一个双向图且每一个节点和所有其他节点都相连的话那么该算法的时间复杂度就接近于 Bellman_ford 的 O(N * E) N 为节点数量E为边的数量。 在这种图中每一个节点都会重复加入队列 n-1 次因为 这种图中每个节点都有 n-1 条指向该节点的边每条边指向该节点就需要加入一次队列。 当然这种图是比较极端的情况也是最稠密的图。所以如果图越稠密则 SPFA的效率越接近与 Bellman_ford。反之图越稀疏SPFA的效率就越高。 一般来说SPFA 的时间复杂度为 O(K * N) K 为不定值因为节点需要计入几次队列取决于图的稠密度。 如果图是一条线形图且单向的话每个节点的入度为1那么只需要加入一次队列这样时间复杂度就是 O(N)。 所以 SPFA 在最坏的情况下是 O(N * E)但一般情况下时间复杂度为 O(K * N)。 尽管如此以上分析都是 理论上的时间复杂度分析。 并没有计算 出队列 和 入队列的时间消耗。 因为这个在不同语言上 时间消耗也是不一定的。 以C为例以下两段代码理论上时间复杂度都是 O(n)
for (long long i 0; i n; i) {k;
}for (long long i 0; i n; i) {que.push(i);que.front();que.pop();
}在 MacBook Pro (13-inch, M1, 2020) 机器上分别测试这两段代码的时间消耗情况 n 10^4第一段代码的时间消耗1ms第二段代码的时间消耗 4 ms n 10^5第一段代码的时间消耗1ms第二段代码的时间消耗 13 ms n 10^6第一段代码的时间消耗4ms第二段代码的时间消耗 59 ms n 10^7第一段代码的时间消耗: 24ms第二段代码的时间消耗 463 ms n 10^8第一段代码的时间消耗: 135ms第二段代码的时间消耗 4268 ms 在这里就可以看出 出队列和入队列 其实也是十分耗时的。 SPFA队列优化版Bellman_ford 在理论上 时间复杂度更胜一筹但实际上也要看图的稠密程度如果 图很大且非常稠密的情况下虽然 SPFA的时间复杂度接近Bellman_ford但实际时间消耗 可能是 SPFA耗时更多。
4. 负环问题
在用 spfa 求负环时不需要建立虚拟源点。我们只需要以任意结点为起点执行 spfa 就一定能判断负环是否存在。因此只要存在符号就一定存在负权边就一定能进行松弛操作就一定能入队。
3. 限制边数的最短路
既然 spfa 是 bellman_ford 的改进版那么按理来说spfa 也能实现限制边数的最短路问题。没错问题是如何在 spfa 的执行逻辑中限制松弛次数 还是从层序遍历的思想来看在层序遍历中每一轮遍历需要取出当前队列中所有保存的结点。由于 spfa 是对 bellman_ford 的优化所以 spfa 在形式上和层序遍历更相似了。 这里的实现思路和层序遍历非常相似: 题目链接
#include iostream
#include cstring
#include algorithm
#include queueusing namespace std;const int N 510, M 10010, INF 0x3f3f3f3f;int n, m, k;
int h[N], e[M], ne[M], w[M], idx;
int dist[N], backup[N];
bool st[N];void add(int a, int b, int c)
{w[idx] c;e[idx] b, ne[idx] h[a], h[a] idx ;
}int spfa()
{memset(dist, 0x3f, sizeof dist);dist[1] 0;queueint q;q.push(1);st[1] true;while(k -- ) {memset(st, false, sizeof st);// 1这里要将所有st置位false因为上一轮置位true的点和这一轮需要加入的点“不一样”// 上一轮入队的点我们使用的是backup[]进行松弛的// 而这一轮加入的点我们希望使用 dist[] 进行// 可以发现这一轮对 dist 的更新不会体现在上一轮中因为上一轮使用 backup 而不是 dist// 因此对于上一轮入队st置位true的点这一轮依然需要入队int cnt q.size();// 2和bellman_ford一样使用上一轮的dist进行松弛操作memcpy(backup, dist, sizeof(dist));while(cnt -- ) // 3遍历上一层所有加入的点进行松弛{auto t q.front(); q.pop();st[t] false;for(int i h[t]; i ! -1; i ne[i]) {int j e[i];if(dist[j] backup[t] w[i]) {dist[j] backup[t] w[i];if(!st[j]) {q.push(j);st[j] true;}}}}}return dist[n];
}int main()
{memset(h, -1, sizeof h);cin n m k;while(m -- ) {int a, b, c; cin a b c;add(a, b, c);}int t spfa();if(t INF / 2) puts(impossible);else cout t endl;return 0;
}通过上面的代码其实可以发现形式上和 spfa 差不多不过有几个细节需要注意特别是 st 数组和 backup 数组的处理详细内容可以看代码中的注释部分。
三、堆优化dijkstra
1. 时间复杂度分析
reference 在C中一般通过优先队列priority_queue作为数据结构来优化dijkstra 当使用优先队列时如果同一个点的最短路被更新多次因为先前更新时插入的元素不能被删除也不能被修改只能留在优先队列中故优先队列内的元素个数是 O(m) 的 每次从队列中取出一个元素的时间复杂度为 O(logm)。故总的时间复杂度是 O(mlogm)
四、AStar
1. 权值转换
对于很多情景来说我们不好直接使用 AStar 算法特别是在需要确保“最短路”特性的前提下找到一个合适的估价函数比较困难例如题目链接 在上面这道题目中骑士按照日字形移动如果我们使用 AStar 算法是不容易找出一个合适的估价函数使得估价值小于等于真实距离的。 就比如骑士可以从 [0,0] 移动到 [1,2]。此时的
哈密顿距离为 3欧拉距离为 5 \sqrt{5} 5 切比雪夫距离为 2 他们都大于骑士的实际移动距离 1所以说按照实际的移动权值 1 进行移动时很难找出合适的估价函数。 不过如果我们将这个权值 1 看作 52211分别沿着 x 轴和 y 轴移动 的话。然后以欧拉距离的平方作为估价函数。那么此时估价值就一定小于等于实际值。 因此说通过改变权值我们可以将原本不适用的估价函数修改为合法。
#include iostream
#include cstring
#include algorithm
#include queue
#include cmathusing namespace std;const int N 1000;
const int DISTANCE 5; // 2 * 2 1 * 1typedef pairint, int PII;int dist[N 1][N 1];
int dx[8] {1, 1, -1, -1, 2, 2, -2, -2};
int dy[8] {2, -2, 2, -2, 1, -1, 1, -1};typedef struct Node {PII p; // pointint g, h; // f g(grape_dist) h(heuristic)bool operator(const Node rhs) const {return g h rhs.g rhs.h;}
} Node; // astar_node_typeint eular_distance(PII x, PII y)
{return (x.first - y.first) * (x.first - y.first) (x.second - y.second) * (x.second - y.second);
}int astar_bfs(PII start, PII goal)
{if(start goal) return 0;memset(dist, 0, sizeof dist);dist[start.first][start.second] 1;priority_queueNode q;q.push({start, 5, eular_distance(start, goal)});while(q.size()) {auto t q.top(); q.pop();auto [x, y] t.p;int g t.g;for(int i 0; i 8; i ) {int a x dx[i], b y dy[i];if(a 0 || a N || b 0 || b N) continue; if(!dist[a][b] || dist[a][b] dist[x][y] 1){if(a goal.first b goal.second) return dist[x][y];q.push({{a, b}, g DISTANCE, eular_distance({a,b}, goal)});dist[a][b] dist[x][y] 1; }}}return -1; // cant move the goal
}int main()
{int T; cin T;while(T -- ) {int sx, sy, ex, ey;cin sx sy ex ey;cout astar_bfs({sx, sy}, {ex, ey}) endl;}return 0;
}2. 只能确保终点的最短路
在 AStar 算法中我们只能确保从起点到终点的最短路而不能确保从起点到其余节点的路线也是最短路。 具体来说当终点第一次出队时我们能确保它是最短路但对于其余节点来说我们并不能保证这一点。 这是因为我们的估价函数保证的是任意节点到终点的估价值小于等于实际值。 如果我们相求非终点的最短路需要确保任意节点到该节点的估价值小于等于实际值但我们的估价函数并未保证这一点。 当然很显然的如果运气好的话对于某些节点来说我们的估价函数或许也满足其余节点到该节点的估计值小于等于实际值但这完全是运气它完全不可靠 所以说即使我们求出了非终点的最短路也只是运气好而已。 因此说由于非终点第一次出队可能不是最短路就意味着它可能在后续再次被更新此时就需要再次入队。这不同于 dijkstra 和 bfs 的单次入队。 因为 dijkstra 和 bfs 可以保证某个节点第一次出队时一定是最短路。但 Astar 由于估计值的原因只能保证终点。 从上面的代码中我们可能看出这一处理if(!dist[a][b] || dist[a][b] dist[x][y] 1) 其中 dist[a][b] dist[x][y] 1 对某个节点做了允许多次入队处理。如果我们去掉这段代码那么 bfs 的正确性完全看运气了。 如果此时遍历到的其余节点恰好能满足最短路的特性程序正确反之如果其余节点中间节点不满足最短路那么从其余节点出发走向终点的路线也必然不是最短路了。
