在一个完全图中找到一条路径，限制路径的成本并最大化奖励。

Question

我正在寻找一种算法来解决这个问题。我必须实现它（所以我需要一个不是np的解决方案XD）

我有一个完全图，每条边上都有成本，每个顶点上都有奖励。我只有一个起点，但终点并不重要，因为问题是找到一条路径，能够尽可能多地访问顶点，以便获得最大的奖励，但受到最大成本限制。（因此，结束位置并不重要）。

我认为找到最佳解决方案是一个NP难题，但近似解决方案也是可行的:D

谢谢

我正在尝试学习如何使用分支和界来解决这个问题...

更新：完整问题描述

我有一个区域，其中有几个由其ID和XYZ位置标识的区域。每个顶点都标识着其中一个区域。最大区域数为200。 从起点S开始，我知道从任意一个顶点到达每个顶点的成本（以秒为单位），并在弧上插入（因此只有整数值）。 当我访问一个顶点时，我会得到一个奖励（浮动值）。

我的目标是在图中找到一条路径，最大化奖励，但我受到路径上的成本约束。事实上，我只有有限的时间完成路径（例如600秒）。

该图由成本和回报的邻接矩阵构成（但如果有用的话，我可以更改表示方法）。

我可以多次访问顶点，但仅获得一个奖励！

- Peppe

---

你有多少个顶点，成本限制有多大？有一种简单的伪多项式O(n^2 * C)算法，其中C是成本限制，n是顶点数。 - Niklas B.

这不是一个清晰的问题陈述。你要么在寻找具有最大可能奖励的路径，要么是尽可能多的顶点，两者不能同时兼备。 - svinja

弧成本是否是度量？您能否重新访问顶点？如果可以重新访问顶点，您会多次获得奖励吗？ - David Eisenstat

我已经更新了帖子。 - Peppe

Answer 1

由于您对分支定界感兴趣，让我们制定一个线性规划。使用 Floyd-Warshall 算法将成本最小化向下调整，以便对于所有顶点 u, v, w，cost(uw) ≤ cost(uv) + cost(vw)。

假设 s 是起始顶点。我们有 0-1 变量 x(v)，表示顶点 v 是否是路径的一部分，以及 0-1 变量 y(uv)，表示弧 uv 是否是路径的一部分。我们旨在最大化：

sum over all vertices v of reward(v) x(v).

不幸的是，这些限制条件相当复杂。我们首先将 x 和 y 变量相关联。

for all vertices v ≠ s,  x(v) - sum over all vertices u of y(uv) = 0

然后我们限制了成本。

sum over all arcs uv of cost(uv) y(uv) ≤ budget

我们有(预)流约束条件，以确保所选的弧看起来像一条路径，可能伴随着循环（我们稍后会处理循环）。

for all vertices v,  sum over all vertices u of y(uv)
                       - sum over all vertices w of y(vw)
                         ≥ -1 if v = s
                            0 if v ≠ s

为了处理这些循环，我们添加割覆盖约束。

for all subsets of vertices T such that s is not in T,
  for all vertices t in T,
    x(t) - sum over all vertices u not in T and v in T of y(uv) ≥ 0

由于前置流约束，一个循环结构必然与路径结构断开连接。

存在指数级别的割覆盖约束，因此在解决LP问题时，我们必须按需生成它们。这意味着找到s和每个其他顶点之间的最小割，然后验证割的容量不大于x(t)。如果发现违规，则添加约束并使用对偶单纯形法找到新的最优解（如有必要，请重复）。

我不打算详细描述分支机制-这应该由您的LP求解器自动处理。

- David Eisenstat

---

非常聪明的回答。你让我学到了一些东西...你能加入一些复杂度分析吗？由于我不熟悉你使用的概念，所以我自己做不到。这将使这个已经很棒的答案更加出色 :) - Rerito

@Rerito 可能是最坏情况下的指数级，但研究运筹学的人们用实验验证性能而不是理论，这是有原因的：最坏情况下的边界与现实几乎没有关系。 - David Eisenstat

Answer 2

寻找最优解

这里提供了一种递归方法来解决您的问题。

让我们从一些定义开始：

• 令 A = (A_i)_{1 ≤ i ≤ N} 为区域。
• 令 w_i,j = w_j,i 为从 A_i 到 A_j 和从 A_j 到 A_i 的时间成本。
• 令 r_i 为访问区域 A_i 的奖励。

以下是将输出所需精确解决方案的递归过程：（伪代码）

List<Area> GetBestPath(int time_limit, Area S, int *rwd) {
    int best_reward(0), possible_reward(0), best_fit(0);
    List<Area> possible_path[N] = {[]};
    if (time_limit < 0) {
        return [];
    }
    if (!S.visited) {
        *rwd += S.reward;
        S.visit();
    }
    for (int i = 0; i < N; ++i) {
        if (S.index != i) {
            possible_path[i] = GetBestPath(time_limit - W[S.index][i], A[i], &possible_reward);
            if (possible_reward > best_reward) {
                best_reward = possible_reward;
                best_fit = i;
            }
        }
    }
    *rwd+= best_reward;
    possible_path[best_fit].push_front(S);
    return possible_path[best_fit];
}

为了明确起见，我假设A_i和w_i,j是全局可访问的。

解释

你从S开始。第一件事是什么？收集奖励并标记节点为已访问。然后你必须检查在S的N-1个邻居（我们称它们为N_S,i，其中1 ≤ i ≤ N-1）之间选择哪个方向最好。

这与使用时间限制解决N_S,i问题完全相同：

time_limit - W(S ↔ N_S,i)

由于你标记了已访问的节点，所以当到达一个区域时，你首先检查它是否被标记。如果是，你就没有奖励...否则，你会收集并标记它为已访问...

依此类推！

结束条件是当时间限制（C）变为负数时。这告诉我们，我们已经达到了极限，不能继续进行更多的移动：递归结束。如果在达到时间限制C之前已经收集了所有奖励，则最终路径可能包含无用的旅程。你需要“修剪”输出列表。

复杂度？

哦，这个解决方案在复杂度方面太糟糕了！每次调用都会导致N-1次调用...直到达到时间限制。通过在最短的边上来回移动，可以得到最长的可能调用序列。让w_min成为这条边的权重。

显然，总体复杂度受N^C/w_min.C/w_min的限制。
这是非常巨大的。

---

另一种方法

维护一个所有已访问节点的哈希表。 另一方面，维护一个未收集节点的最大优先队列（例如使用MaxHeap）。（堆的顶部是奖励最高的节点）。队列中每个节点A_i的优先级值设置为对偶（r_i，E[w_i,j]）

1. 弹出堆：Target <- heap.pop()。
2. 使用Dijkstra算法计算到该节点的最短路径。
3. 检查路径：如果路径成本太高，则该节点不可达，将其添加到不可达节点列表中。
   1. 否则，收集其中找到的所有未收集节点并...
   2. 从堆中删除每个收集的节点。
   3. 将目标设为新的起点。
4. 在任何情况下，继续执行步骤1，直到堆为空。

注意：哈希表是跟踪收集节点的最佳选择。这样，我们可以在使用Dijkstra计算路径时以O(1)的时间检查节点。

同样，维护一个哈希表，指向堆中每个节点的位置，可能有助于优化沿路径收集节点时对堆进行“修剪”的操作。

一些分析

从复杂度的角度来看，这种方法略优于第一种方法，但可能不会导致最优结果。实际上，在某些图形配置上，它甚至可能表现得相当差。例如，如果所有节点都具有奖励r，除了一个节点T具有r+1和W(N ↔ T) = C（其中N是每个节点，C是常数），但其他边缘都是可达的，则这只会使您收集T并错过每个其他节点。在这种特殊情况下，最好的解决方案是忽略T并收集其他所有人，从而获得（N-1）.r的奖励，而不仅仅是r+1。

- Rerito

---

是的...这个解决方案不适用。因此，我正在寻找一个近似的解决方案...比如分支定界或者我也不知道！！ - Peppe

@gepeppe 我有另一个想法，可能不是最佳解决方案，但如果我没弄错的话，可以得到有趣的结果。我需要一些时间来整理它 :) - Rerito

@gepeppe 给你 ;) - Rerito