寻求奖励驱动图遍历的高效算法：替代暴力DFS的优化方案

我现在碰到一个路径规划的难题，想请教有没有比暴力DFS更优雅的解法——暴力DFS的计算量实在太夸张了。具体场景如下：

• 给定一个由节点和路径构成的网络，每条路径带有距离信息，路径上存在0个或多个每5分钟仅可收集一次的元素，收集这些元素能提升分数。
• 目标是规划接下来5分钟的路径遍历，要求避开过去5分钟已经走过的路径，以此最大化分数提升。

暴力算法的思路是从当前位置出发，尝试所有可能的路线，避开已访问区域，直到达到最大规划距离或时间后停止，统计虚拟奖励，最终选择分数最高的路线。但图中的节点和路径数量不少，就算只规划5分钟的行程，计算量也大得离谱。

想问问有没有比暴力法更高效的已知算法？哪怕只能得到近似解而非最优解也完全可以接受。

我的最终解决方案（供有相同问题的朋友参考） #

感谢@SaiBot的提示，我最终实现了以下方案，分享给大家：

• 路径唯一标识与缓存机制：给每条从节点A到B的路径分配唯一ID，B到A的路径单独分配ID。在DFS搜索函数外部维护一个以路径ID为键的哈希表，值存储遍历该路径前的已行驶距离和当前累计奖励。
• 路径排序优化：将每个节点的outgoing paths按长度从短到长排序，减少额外计算开销。
• 剪枝逻辑：当DFS需要评估已处理过的路径时，先检查缓存结果：
  • 如果满足 (奖励 <= 历史奖励 && 距离 >= 历史距离) || 奖励/距离 <= 历史分数，则判定递归这条路径没有收益，直接返回0分以排除该路径；
  • 否则，将新的奖励、距离和分数记录到缓存中，继续正常执行递归。
• 路径新颖性与 fallback 机制：为了避免算法只局限于获取最大奖励的短路径，我添加了对outgoing nodes的过滤规则——如果节点在过去X分钟内已被访问过，就将其排除。但这可能导致算法陷入死胡同，因此又补充了 fallback 机制：如果没有可用选项，就把outgoing paths按最后访问时间从早到晚排序，依次尝试。

目前这个方案的效果还不错，不过我会继续做实验来优化结果。

内容的提问来源于Stack Exchange，提问作者John Arrowwood