algorithm - 修改 Dijkstra 以在给定额外属性的情况下找到最优化的最短路径

Question

这是我在 here 提出的问题的后续问题.问题被映射到一个边上有非负权重的图(无论是否可以定向，都没有偏好)。然而，除了实际上是距离的权重外，我们还有另一个属性，即边缘的数据覆盖范围，这可能是选择路由的重要因素，因为我需要手机上的互联网有多严重(例如，对于实时游戏，我需要良好的带宽)。所以总的来说，我们想以某种方式在路径长度和网络带宽之间找到一个权衡点，以解决在两个城市之间找到最优化和最短路径的问题。然而，一个重要的特征是算法应该是动态的。一旦我们到达一个节点，根据我们当前的需求状态，我们可能会更改预先确定的路径。

好的。为简单起见，假设每条边都与两个属性相关联:A) 距离或旅行时间或其他任何东西，作为常规权重，以及 B) 网络带宽作为次要属性以显示网络有多好。

对于约束和目标函数，假设我们想要最小化总距离(或旅行时间)，但根据我们当前的状态，我们还希望最小化总断开时间 或最大化路径带宽的总和。或者，假设我们不能容忍超过阈值 T 的总连续断开时间。所以这可能是对问题的约束。此类目标函数中最简单的可以是 f()=total time of travel + a*time of disconnection。 a 系数决定了连通性在任何时候对我们的重要性。

为了解决边缘可能有部分断开的问题，经过一番思考，我想到了一个解决方案，让我们在它们之间插入节点。这样问题就更容易解决了。所以基本上每条路由要么断开连接，要么连接到特定值的带宽。

我想到的第一个版本的解决方案是在计算路径时累加连续断开连接的总次数，因此不能超过阈值T。每当我们到达一条有连接的路线时(对于更简单的问题，不考虑带宽)，我们只是重置累积。进一步考虑带宽，因为我们也有连接带宽的值(value)，我们可以从总的累计断开时间中减去连接带宽的值(value)(这行得通吗？!)

一件重要的事情是考虑下面的示例图。不超过总断开阈值不应导致经过很远的路线，从而增加总行程时间!为此，我想到了这种通用方法:解决断开连接阈值的问题，比如 T1, T2, ...Tk，计算最佳路径(或者可能是一组最佳路径？!)，并计算每个相应的总行程时间。然后应用我们上面的目标函数，看看什么是最佳解决方案。我们可以进一步确定两个样本之间的解决方案，以使用类似二进制搜索的方法找到更优的解决方案。

拜托，有人可以帮我解决这个问题吗？显然我的解决方案是不正确的，如果是的话，甚至在多项式时间内也是不可能的。也许是近似算法？!非常感谢任何帮助找到解决方案的人。随意添加更多细节或假设，或修改问题。这个问题比我想象的要难。

Answer 1

首先，为整个网络找到这个问题的完美答案在计算上是不可行的。参见 http://phys.org/news/2015-05-maths-congestionsprings-traffic.html获取概述您将遇到的一些实际复杂性和数值不稳定性的文章。以及添加道路会使整个网络变得更糟的演示。

但是，对于您正在查看的 IP 网络问题，我们可以在实践中很好地解决它。谷歌搜索给了我 https://www.cs.princeton.edu/~jrex/papers/opthand04.pdf作为从哪里开始学习文献的建议。