algorithm - 利润最大化的寻路算法

Question

假设我们有一个有向图，其中每条边都包含一个元组 (d,p)，其中 d 是必须经过的距离，p 是你穿过这条边得到的利润，穿过一条边后，它的利润设置为0。我的问题是，给定起始节点和最大距离 D(例如 Σd < D 跨越所有遍历的边)，求解最大利润，其中利润定义为 < strong>Σp 遍历所有边。

您可以重新访问节点并重新遍历边。

我试图修改 dijkstra 但没有成功，因为 dijkstra 不知道何时停止它的泛洪填充，据我所知，在检查所有可能性之前，没有办法保证 dijkstra 的最佳解决方案。我还研究了 TSP 的变体，这个问题似乎与寻路更相关。任何引用、伪代码或已经理解的算法将不胜感激。当然，我不是在寻找蛮力算法。

Answer 1

鉴于问题的规模，我们可能会成功地使用整数程序对其进行攻击。对于每条有向边e，设x(e)是一个非负整数变量，表示我们使用该边的次数，y(e) 是一个 0-1 的变量，代表我们从边缘获利的次数。对于每个顶点 v，让 w(v) 是一个 0-1 变量，指示是否访问了 v，并且 z(v ) 是一个 0-1 变量，指示 v 是否为结束顶点。整数程序的简单部分是

maximize sum_e p(e) y(e)
subject to
y(e) <= x(e)            # can't profit from an edge if we don't use it
for all e, y(e) <= w(head(e))    # can't profit unless we visit
for all e, y(e) <= w(tail(e))    # can't profit unless we visit
sum_e d(e) x(e) <= D    # bounded distance
sum_v z(v) = 1          # exactly one ending vertex
# path constraints
for all vertices v, sum_{e with head v} x(e) - sum_{e with tail v} x(e) =
    z(v) - 1 if v is the starting vertex,
    z(v)     otherwise.

困难的部分是防止无处可去的循环(类似于 TSP 的 subtour 消除约束)。如果我们做到了这一点，那么我们就可以在子图中找到欧拉轨迹，其边缘具有由 y(e) 指示的多重性。

我们采用与 TSP 相同的策略——编写指数数量的约束，事后强制执行。

for all sets of vertices S containing the starting vertex,
    for all vertices v not in S,
        sum_{directed edges e entering S} y(e) >= w(v)