一种合理有效的报酬驱动图遍历算法

Question

我想知道这个问题是否有一个更优雅的解决方案。蛮力法(深度优先搜索)在计算上过于密集.

您将得到一个由连接路径的节点组成的网络。每条路径都有一个距离和零个或多个元素，每五分钟只能收集一次。收集这些元素会增加你的分数。

我们的目标是规划下五分钟的路径遍历，同时铭记过去五分钟内已经遍历过的路径，以便最大限度地增加分数。

蛮力算法是尝试从当前位置的每一条可能的路线，避免我们已经去过的地方，当我们旅行了我们的最大计划距离或时间时停止，并保持一个虚拟的奖励计数收集。然后我们要做的就是选择得分最高的路线。

不幸的是，图中节点和路径的数量很高，以至于计划出5分钟的行程都需要大量的计算。

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

编辑

谢谢你@SaiBot，这是我的最后解决方案，以防有人会问同样的问题：

我给每条路径都分配了一个唯一的ID，从节点A到节点B。从B到A的路径有自己的ID。在DFS搜索功能之外，我保留了一个由ID键构成的散列，该值包括在走这条路径之前所走的距离，以及迄今为止所收到的奖励的大小。为了尽量减少额外的工作，我确保在每个节点上，输出路径被排序为最短到最长。然后，当DFS算法被要求评估它之前评估过的路径时，它首先检查的是缓存的结果。如果缓存的结果到达：

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

然后推断，再次递归这条路径没有好处，因此它立即返回，分数为0，立即取消它的考虑资格。否则，它会在缓存中记录新传入的奖励、距离和得分，并正常进行。

另外，我还做了另一件事。我认为我想在这条路上有一定的新鲜感，这意味着我不想让它找到一条能得到最大回报的小径，我想让它去探索地图。因此，我向传出节点添加了一个筛选器，表示如果在过去的X分钟中访问过该节点，则从考虑中删除它。这有副作用，允许算法自己路由到一个角落，所以我增加了一个后退，在那里，如果没有可用的选项，它将排序的最后一次访问，最古老的路径，首先，并尝试按照这个顺序。

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

Answer 1

您的问题与多准则网络中的帕累托最优路径计算密切相关，如本论文中所描述的。

如果您只有一个条件(如距离)与每个边缘相关联，那么迪克斯特拉可以让您快速找到所有可能的路径(优化距离)。这是可能的，因为如果到达节点的另一条路径已经有较低的距离，则可以“丢弃”到达该节点的路径。

当你有两个或更多的标准(例如，距离和奖励)与每个边缘相关联时，问题就出现了。现在，如果两个路径(从您的开始节点开始)指向同一个节点，而path_1的距离低于path_2，但是path_2的回报高于path_1，那么您也不能丢弃它。但是，如果路径的两个条件都比另一条路径差，则可以放弃它。

在上述论文中描述了完成搜索的一种可能的算法。

编辑

我上面的回答不会考虑在路线上出现的因素。如果您想要包括这一点，您必须知道在路线规划过程中元素何时和在何处出现。然而，这将使事情变得更加复杂，因为你可以通过“等待”元素来获得更高的回报。