寻路算法以最大化利润

Question

寻路算法以最大化利润

algorithmgraphgraph-algorithmpath-finding

3

假设我们有一个有向图，每个边包含一个元组 (d，p)，其中 d 是必须行进的距离，p 是您穿过该边时将获得的利润，在穿过一条边后，其利润设置为 0 。我的问题是，给定起始节点和最大距离 D （使得所有经过的边上的 Σd＜D ），解决最大利润的问题，其中利润定义为 Σp 经过所有边缘。

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

我已尝试修改迪杰斯特拉算法，但没有成功，因为迪杰斯特拉不知道何时停止其泛洪填充，据我所知，在检查所有可能性之前，无法保证使用迪杰斯特拉算法得到最佳解决方案。我也研究了TSP的变化，而这个问题似乎更多地与路径查找相关。任何参考资料、伪代码或已经理解的算法都将不胜感激。当然，我不想要暴力算法。

- Bryce219

3

通过从哈密顿路径问题归约来证明NP-hard性质。与非对称奖励旅行商问题相关。 - David Eisenstat

@DavidEisenstat，谢谢您提到它是NP难问题，并且从我能找到的关于非对称奖励收集TSP的文献来看，它似乎非常相似，除了节点只被访问一次。 - Bryce219

@DavidEisenstat 进一步阅读后，我发现奖励收集TSP的优化目标与我的相距甚远。奖励收集TSP的目标是访问节点的子集，使得旅程的长度加上所有不在旅程中的节点的惩罚之和尽可能小。没有明确的最大距离限制，只是试图保持它低。 - Bryce219

1

这并不是一种精确的对应关系，但是（在将每条边分割以允许中间奖品后），您可以通过尝试几个不同的D值来近似地使用此算法来解决APCTSP问题，并通过引入拉格朗日乘数来解决APCTSP问题。注意到这种关系的想法不是为了应用现成的APCTSP算法，而是攻击APCTSP所使用的思想可能对解决此问题有用。 - David Eisenstat

1

我正在构思一个想法。 - David Eisenstat

显示剩余3条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Eisenstat · Accepted Answer

考虑到问题的规模，我们可以采用整数规划来解决。对于每一条有向边e，我们定义一个非负整数变量x(e)表示使用该边的次数，以及一个0-1变量y(e)表示从该边获利的次数。对于每个顶点v，我们定义一个0-1变量w(v)表示是否访问了该顶点，以及一个0-1变量z(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的子路径消除约束）。如果我们能够做到这一点，那么我们就可以在子图中找到一条欧拉路径，其边缘的重复次数由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)