algorithm - 奖励驱动图遍历的合理有效算法

Question

我想知道是否有更优雅的解决方案来解决这个问题。蛮力方法(深度优先搜索)的计算量太大。

给定一个由路径互连的节点网络。每条路径都有一个距离和沿路径的零个或多个元素，每五分钟只能收集一次。收集这些元素会增加你的分数。

目标是规划接下来五分钟的路径遍历，牢记在过去五分钟内已经遍历的路径，以最大限度地增加分数。

蛮力算法是从当前位置开始尝试每条可能的路线，避开我们已经去过的地方，当我们走过我们的最大计划距离或时间时停止，并保留收集到的奖励的虚拟记录。然后我们所要做的就是选择得分最高的路线。

不幸的是，图中的节点和路径数量太多，以至于即使只规划五分钟的行程也需要大量计算。

有没有比暴力法更有效地解决这个问题的已知算法？即使它只能找到近似解，而不是最优解。

编辑

谢谢@SaiBot，这是我的最终解决方案，以防万一有人发现自己在问同样的问题:

我为从节点 A 到节点 B 的每条路径分配了一个唯一 ID。从 B 到 A 的路径有自己的 ID。在 DFS 搜索功能之外，但它可以访问，我保留了一个由 ID 键控的哈希值，该值由走这条路径之前走过的距离和到目前为止收到的奖励大小组成。为了尽量减少额外的工作，我确保在每个节点上，传出路径都按最短到最长的顺序排序。然后，当 DFS 算法被要求评估它之前评估过的路径时，它首先检查的是缓存的结果。如果缓存结果到达:

( reward <= previous_reward && distance >= previous_distance )
|| reward / distance <= previous_score

然后推断再次递归这条路径不会有任何好处，所以立即以0分返回，立即取消考虑。否则，将新传入的奖励、距离和分数记录在缓存中，并正常进行。

另外，我还做了一件事。我的理由是我希望路径中有一定的新颖性，这意味着我不希望它只找到一条获得最大奖励的小路径，我希望它探索 map 。所以我给传出的节点加了一个过滤器，说如果这个节点在过去X分钟内访问过，就把它从考虑中去掉。这具有允许算法将自身路由到角落的副作用，因此我添加了一个回退，如果没有可用的选项，它会按最后访问的、最旧的优先顺序对传出路径进行排序，然后尝试这样做命令。

结果还不错，但我会做更多的实验，看看是否能得到更好的结果。

Answer 1

您的问题与多标准网络中的帕累托最优路径计算密切相关，例如，如 this paper 中所述.

如果您只有一个标准(如距离)与每条边相关联，那么 Dijkstra让您快速找到所有可能的路径(优化距离)。这是可能的，因为如果到达该节点的另一条路径已经具有更短的距离，您可以“丢弃”到达该节点的路径。

当您有两个或多个与每条边关联的标准(例如，距离和奖励)时，就会出现问题。现在，如果两条路径(从您的起始节点开始)通向同一个节点，并且 path_1 的距离比 path_2 短，但 path_2 的奖励比 path_1 高，您不能丢弃任何一个。但是，如果一条路径的两个标准都比另一条路径差，您可以丢弃它。

the above paper 中描述了一种可能的算法来进行完整搜索.

编辑

我上面的回答不会考虑在 route 重新出现的元素。如果你想包括这个，你必须知道在路线规划期间元素何时何地重新出现。然而，这会使事情变得更加复杂，因为您可以通过“等待”元素重生来获得更高的奖励。