在包含成本限制和最大奖励的完整图表中查找路径

Question

我正在寻找一种算法来解决这个问题.我必须实现它(所以我需要一个非np解决方案XD)

我有一个完整的图表,每个拱门都有成本,每个顶点都有奖励.我只有一个起点,但终点并不重要,因为问题是要找到一条路径尽可能多地查看顶点,以便尽可能获得最大奖励,但要受到最大成本限制.(因此,最终位置并不重要).

我认为找到最佳解决方案是一个难以解决的问题,但也是一个近似的解决方案:D

谢谢

我正在尝试研究如何用分支和绑定解决问题...

更新:完整问题dscription

我有一个区域,其中有几个区域通过其id和x,y,z位置来识别.每个顶点标识这些区域中的一个.最大的ares数是200.从起点S开始,我知道成本,以秒为单位并插入拱(因此只是整数值),从每个其他顶点到达每个顶点(一个完整的图).当我访问一个顶点时,我得到一个奖励(浮动valiues).

我的目标是在图表中找到最大化奖励的路径,但我受到路径上的成本约束.事实上,我只有有限的时间来完成路径(例如600秒).

该图表是作为成本和奖励的矩阵邻接矩阵(但如果有用,我可以更改表示).

我可以访问顶点更多的时间,但只有一个奖励!

Answer 1

\n\n

寻找最优解

\n\n

这是解决问题的递归方法。

\n\n

让我们从一些定义开始：

\n\n

\n
• 设 A = (A _i ) _{1 \xe2\x89\xa4 i \xe2\x89\xa4 N}为面积。
\n
• 设 w _i,j = w _{j,i从 A i}到 A _j的时间成本_{，反之亦然。}
\n
• 设 r _i为访问 A 区的奖励_{为访问 A i}
\n

\n\n

这是将输出确切请求的解决方案的递归过程：（伪代码）

\n\n

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

\n\n

出于明显的清晰原因，我认为 A _i是全局可达的，并且 w _{i,j也是如此}都是全局可达的。

\n\n

说明

\n\n

你从S开始。你做的第一件事？收集奖励并将节点标记为已访问。然后你必须检查S的 N-1 个邻居（我们称它们为 N _S,i即 1 \xe2\x89\xa4 i \xe2\x89\xa4 N-1）。

\n\n

_{这与解决 N S,i}问题完全相同_{，时间限制为 ：}

\n\n

\n

time_limit - W(S \xe2\x86\x94 N _S,i )

\n

\n\n

由于您标记了访问过的节点，因此当到达某个区域时，您首先检查它是否被标记。如果是这样，你没有奖励......否则你收集并将其标记为已访问......

\n\n

等等！

\n\n

结束条件是time_limit(C)变为负值。这告诉我们已经达到了极限，无法继续进一步的移动：递归结束。如果在达到时间限制 C 之前收集到所有奖励，则最终路径可能包含无用的旅程。您必须“修剪”输出列表。

\n\n

复杂性？

\n\n

哦，这个解决方案在复杂性方面太糟糕了！\n每个调用都会导致 N-1 个调用......直到达到时间限制。通过每次在最短边上来回产生可能的最长调用序列。让 w_分钟为该边的权重。

\n\n

显然，整体复杂度受 N ^{C/w _min} .C/w _min的限制。
\n这就是呼呼呼。

\n\n\n\n

另一种方法

\n\n

维护所有已访问节点的哈希表。\n另一方面，维护尚未收集的节点的最大优先级队列（例如使用MaxHeap ）。（堆顶是奖励最高的节点）。队列中每个节点 A _i的优先级值设置为对 (ri _, E[w _i,j] )

\n\n

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

\n\n

注意：哈希表最适合跟踪收集的节点。这样，我们就可以在 O(1) 中检查使用 Dijkstra 计算的路径中的节点。

\n\n

同样，当沿路径收集节点时，维护导致堆中每个节点位置的哈希表可能有助于优化堆的“修剪”。

\n\n

一点分析

\n\n

这种方法在复杂性方面比第一种方法稍好，但可能不会得到最佳结果。事实上，它甚至在某些图形配置上表现得很差。例如，如果所有节点都有奖励 r，除了一个节点 T 具有 r+1 且每个节点 N 的 W(N \xe2\x86\x94 T) = C，但其他边都是可达的，则此只会让你收集 T 并错过所有其他节点。在这种特殊情况下，最好的解决方案是忽略 T 并收集其他所有人，从而获得 (N-1).r 的奖励，而不是仅获得 r+1。

\n