「学习笔记」SPFA 算法的优化

这篇具有很好参考价值的文章主要介绍了「学习笔记」SPFA 算法的优化。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

与其说是 SPFA 算法的优化,倒不如说是 Bellman-Ford 算法的优化。

栈优化

将原本的 bfs 改为 dfs,在寻找负环时可能有着更高效的效率,但是最坏复杂度为指数级别。

void dfs_spfa(int u) {
	if (fg)    return;
	vis[u] = true;
	for(pil it : son[u]) {
		int v = it.first;
		ll w = it.second;
		if (dis[v] > dis[u] + w) {
			dis[v] = dis[u] + w;
			if (vis[v] == true) {//如果这个点被访问过,就说明这是负环 
				fg = true;//打标记 
				return;
			}
			else    dfs_spfa(v);
		}
	}
	vis[u] = false;
}

SLF 优化

queue 换成 deque,判断与队首元素的 dis 的大小,小的就放队首,大的就放队尾。

void spfa(int s) {
	for(int i = 1; i <= n; ++ i) {
		dis[i] = inf;
	}
	dis[s] = 0;
	q.push_back(s);
	f[s] = 1;
	while (!q.empty()) {
		int u = q.front();
		q.pop_front();
		f[u] = 0;
		for (pii it : son[u]) {
			int v = it.first;
			int w = it.second;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				if (! f[v]) {
					if (! q.empty() && dis[v] < dis[q.front()]) {
						q.push_front(v);
					}
					else    q.push_back(v);
					f[v] = 1;
				}
			}
		}
	}
}

D´Esopo-Pape 优化

queue 换成 deque,判断一个点是否入过队列,没入过就放到队尾,如果就放到队首。

void spfa(int s) {
	for(int i = 1; i <= n; ++ i) {
		dis[i] = inf;
	}
	dis[s] = 0;
	q.push_back(s);
	f[s] = 1;
	vis[s] = 1; // 是否入过队
	while (!q.empty()) {
		int u = q.front();
		q.pop_front();
		f[u] = 0;
		for (pii it : son[u]) {
			int v = it.first;
			int w = it.second;
			if (dis[v] > dis[u] + w) {
				dis[v] = dis[u] + w;
				if (! f[v]) {
					if (vis[v]) {
						q.push_front(v);
					}
					else {
						q.push_back(v);
						vis[v] = 1;
					}
					f[v] = 1;
				}
			}
		}
	}
}

LLL 优化

queue 换成 deque,每次将入队结点距离和队内距离平均值比较,如果更大则插入至队尾,否则插入队首。

void spfa() {
	ll sum = 0;
	for (int i = 1; i <= n; ++ i) {
		dis[i] = inf;
	}
	dis[s] = 0;
	q.push_back(s);
	g[s] = 1;
	sum += dis[s];
	while (!q.empty()) {
		int u = q.front();
		q.pop_front();
		vis[u] = false;
		sum -= dis[s];
		for (pli it : son[u]) {
			if (dis[it.second] > dis[u] + it.first) {
				dis[it.second] = dis[u] + it.first;
				if (! vis[it.second]) {
					if (q.empty() || dis[it.second] > sum / ((int)q.size())) {
						q.push_back(it.second);
					}
					else {
						q.push_front(it.second);
						g[it.second] = 1;
					}
					vis[it.second] = true;
				}
			}
		}
	}
}

SLF 带容错优化

queue 换成 deque,判断与队首元素的 dis 的大小,设定一个值 \(W\),如果比队首元素大超过 \(W\) 则放队尾。

\(W\) 一般设为所有边权的和的开方,即 \(\sqrt{sum}\)

mcfx 优化

在第 \(\left[L, R\right]\) 次访问一个结点时,将其放入队首,否则放入队尾。通常取 \(L = 2, R = \sqrt{\left|V\right|}\)

SLF + swap 优化

每当队列改变时,如果队首距离大于队尾,则交换首尾。文章来源地址https://www.toymoban.com/news/detail-430595.html

到了这里,关于「学习笔记」SPFA 算法的优化的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 机器学习笔记之优化算法(二十)牛顿法与正则化

    本节我们介绍 经典牛顿法 在训练 神经网络 过程中的迭代步骤,并介绍 正则化 在牛顿法中的使用逻辑。 经典牛顿法 自身是一个典型的 线搜索方法 ( Line-Search Method ) (text{Line-Search Method}) ( Line-Search Method ) 。它的迭代过程使用 数学符号 表示如下: x k + 1 = x k + α k ⋅ P k x_

    2024年02月11日
    浏览(44)
  • 机器学习笔记之优化算法(十九)牛顿法与正则化

    本节我们介绍 经典牛顿法 在训练 神经网络 过程中的迭代步骤,并介绍 正则化 在牛顿法中的使用逻辑。 经典牛顿法 自身是一个典型的 线搜索方法 ( Line-Search Method ) (text{Line-Search Method}) ( Line-Search Method ) 。它的迭代过程使用 数学符号 表示如下: x k + 1 = x k + α k ⋅ P k x_

    2024年02月11日
    浏览(42)
  • 机器学习笔记之优化算法(十)梯度下降法铺垫:总体介绍

    从本节开始,将介绍 梯度下降法 ( Gradient Descent,GD ) (text{Gradient Descent,GD}) ( Gradient Descent,GD ) 。 线搜索方法作为一种常见优化问题的 策略 ,该方法的特点是: 其迭代过程中,将 数值解 的方向和步长分开执行 。对应 数学符号 表达如下: 其中 P k mathcal P_k P k ​ 是一个向量

    2024年02月13日
    浏览(41)
  • 机器学习笔记之优化算法(十三)关于二次上界引理

    本节将介绍二次上界的 具体作用 以及它的 证明过程 。 利普希兹连续 在 Wolfe text{Wolfe} Wolfe 准则收敛性证明一节中简单介绍了 利普希兹连续 ( Lipschitz Continuity ) (text{Lipschitz Continuity}) ( Lipschitz Continuity ) 。其定义对应 数学符号 表达如下: ∀ x , x ^ ∈ R n , ∃ L : s . t . ∣ ∣

    2024年02月13日
    浏览(77)
  • 机器学习笔记之优化算法(十五)Baillon Haddad Theorem简单认识

    本节将简单认识 Baillon Haddad Theorem text{Baillon Haddad Theorem} Baillon Haddad Theorem ( 白老爹定理 ),并提供相关证明。 如果 函数 f ( ⋅ ) f(cdot) f ( ⋅ ) 在其定义域内 可微 ,并且是 凸函数 ,则存在如下 等价 条件 : 以下几个条件之间相互等价。 关于 f ( ⋅ ) f(cdot) f ( ⋅ ) 的 梯度

    2024年02月12日
    浏览(57)
  • 机器学习笔记之优化算法(十九)经典牛顿法的收敛性分析

    上一节整体介绍了 经典牛顿法 ,并讨论了其更新方向 P k mathcal P_k P k ​ 是否为 下降方向 。本节将对 经典牛顿法 在迭代过程中的收敛性 进行分析。 在这些迭代算法中,我们关注的重点在于 算法在迭代过程中 是否收敛 ,以及它的 收敛速度 。 Wolfe text{Wolfe} Wolfe 准则的收

    2024年02月11日
    浏览(42)
  • 机器学习笔记值优化算法(十四)梯度下降法在凸函数上的收敛性

    本节将介绍 梯度下降法 在 凸函数 上的收敛性。 收敛速度:次线性收敛 关于 次线性收敛 ,分为两种 判别 类型: R mathcal R R -次线性收敛与 Q mathcal Q Q -次线性收敛。而次线性收敛的 特点 是: 随着迭代次数的增加,相邻迭代步骤产生的目标函数结果 f ( x k ) , f ( x k + 1 ) f

    2024年02月13日
    浏览(50)
  • 机器学习笔记之优化算法(十七)梯度下降法在强凸函数的收敛性分析

    上一节介绍并证明了: 梯度下降法 在 强凸函数 上的收敛速度满足 Q mathcal Q Q -线性收敛 。 本节将介绍:在 更强 的条件下:函数 f ( ⋅ ) f(cdot) f ( ⋅ ) 在其定义域内 二阶可微 , 梯度下降法 在 f ( ⋅ ) f(cdot) f ( ⋅ ) 上的收敛速度存在什么样的结论。 关于 梯度下降法 在

    2024年02月12日
    浏览(49)
  • 机器学习笔记之优化算法(七)线搜索方法(步长角度;非精确搜索;Wolfe Condition)

    上一节介绍了 Glodstein text{Glodstein} Glodstein 准则 ( Glodstein Condition ) (text{Glodstein Condition}) ( Glodstein Condition ) 及其弊端。本节将针对该弊端,介绍 Wolfe text{Wolfe} Wolfe 准则 ( Wolfe Condition ) (text{Wolfe Condition}) ( Wolfe Condition ) 。 Armijo text{Armijo} Armijo 准则及其弊端 在当前迭代步骤

    2024年02月14日
    浏览(46)
  • 机器学习笔记之优化算法(十六)梯度下降法在强凸函数上的收敛性证明

    本节将介绍: 梯度下降法 在 强凸函数 上的收敛性,以及 证明过程 。 凸函数与强凸函数 关于 凸函数 的定义使用 数学符号 表示如下: ∀ x 1 , x 2 ∈ R n , ∀ λ ∈ ( 0 , 1 ) ⇒ f [ λ ⋅ x 2 + ( 1 − λ ) ⋅ x 1 ] ≤ λ ⋅ f ( x 2 ) + ( 1 − λ ) ⋅ f ( x 1 ) forall x_1,x_2 in mathbb R^n, forall

    2024年02月11日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包