利润最大化的寻路算法

Question

假设我们有一个有向图，其中每条边包含一个元组 (d,p)，其中 d 是必须的距离traveled 并且 p 是您通过该边缘获得的利润，并且在遍历边缘之后，它的利润设置为 0。我的问题是，给定起始节点和最大距离 D（使得 Σd < D 跨越所有遍历的边），求解最大利润，其中利润定义为遍历所有边的 Σ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 相同的策略 -- 编写指数数量的约束，强制执行它们 post hoc.

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)

利润最大化的寻路算法

Pathfinding algorithm to maximize profit

algorithm

graph

graph-algorithm

path-finding