时间戳

首页 > 解决方案 > 有两个目标的最短路径

algorithm - 有两个目标的最短路径

问题描述

我有兴趣编写一个算法来找到具有两个目标（例如时间和安全）的最短路径。例如，在下图中，黑色数字是旅行时间，红色数字是用户遇到事件的概率。目标是找到具有最佳总体成本的最佳路径。

总成本 = 时间 +（此路线发生事故的概率）*（事故的时间成本）

这是什么类型的问题？这是一个 NP 难题吗？ 例子

标签： algorithmgraphgraph-algorithmdijkstranp-hard

解决方案

首先，如果您的边权重可以通过兼容单元通过卷积、缩放或其他导致形成新的有序半环的方式组合，那么 Dijkstra 的算法将在该半环上按预期工作。

其次，如果您的边权重根本不同，您可以满足于帕累托最优路径。也就是说，一条你不能在不恶化另一个标准的情况下改善一个标准的路径。通常，这是您能做的最好的事情。可能感兴趣的两篇论文是：

Climacao 和 Martins的双准则最短路径算法

Tung 和 Chew的双准则帕累托最优路径算法

在您的情况下，如果您对“事件”的事件做出一些强有力的假设 - 即它们是互斥的 - 那么您可以将边缘权重替换为time + expected time due to an incident.

这是因为如果X_e事件发生在 edge 上e，P(X_e1 or X_e2) = P(X_e1) + P(X_e2) - P(X_e1 and X_e2) = P(X_e1) + P(X_e2)则由它们相互排斥。那么任何路径的预期成本e1 ... eN就是cost(e1) + ... + cost(eN) + incident cost * P(X_e1 or ... or. X_eN) = cost(e1) + ... + cost(eN) + incident cost * (P(X_e1) + ... + P(X_eN)) = (cost(e1) + incident cost * P(X_e1)) + ... + (cost(eN) + incident cost * P(X_eN)) = E(cost of e1) + ... + E(cost of eN)每条边的预期成本之和，彼此独立。

推荐阅读