algorithm - 解决迷宫收集硬币的高效算法
问题描述
解决迷宫的最佳算法是什么，理想情况下是一个图，同时在固定数量的步骤中收集最多数量的硬币？
每条边都有距离，每个节点都有一定数量的硬币（0 - n 个硬币）
总固定步数作为输入给出，保证在这些步骤之后有解决迷宫的解决方案。
谢谢
解决方案
抱歉，你找不到这个问题的有效解决方案，它是NP-hard，这意味着如果你想要一个精确的解决方案，它将具有指数级的复杂性。这可以通过减少背包问题来证明。
假设您有一个带有n 个项目的背包实例，设置w_0...w_n的权重并设置v_0..._v_n的值和容量W，我们可以构建一个图，其中每个顶点对应一个值，加上 2 个额外的顶点s和e表示开始和结束。创建一条从s到每个顶点v_i的边，权重为w_i/2，还创建一条从v_i到顶点e的边，权重为w_i/2。现在找到从s到e的路径，长度限制为W. 该路径不会再访问顶点v_i一次，因为在收集硬币后没有理由返回该节点。此外，要访问任何v_i并到达e，无论是从 s 出发还是从 e 返回，都将花费w_i步。该解决方案保证不超过步数限制并且值的组合是最大的。因此，只需选择v_i访问过的所有顶点，我们就有了一个解决 NP-hard 的背包优化版本的解决方案。
现在情况并没有那么糟糕。问题有解决方案，只是效率低下。对于一个小迷宫，它可能仍然使用蛮力工作，即从一个顶点开始并尝试递归地向任何方向前进。如果超过最大步数 - 中止。如果到达目的地 - 返回路径。然后在所有返回的路径中选择产生最大硬币的路径。
此外，如果您不需要精确的解决方案 - 您可以尝试给出一个近似的解决方案。例如，您可以使用Dijkstra算法生成最短路径树。所以现在你有了从源到每个顶点的最短路径。选择从源到目的地的路径，并尝试迭代地改进它。在每次迭代中选择路径上的一个顶点，查看它的所有邻居，看看它通过这个邻居会给你更好的价值，同时仍然受到步数约束。这不一定会为您提供最佳解决方案，但可能会产生一些好的解决方案。
然后你可以尝试其他优化，比如“捡硬币然后跑”。查看您的路径并尝试通过从某个顶点到其邻居并立即返回来改进它。如果您的迷宫有死胡同，这可能会很有用，这样您自然不会去那里到达目的地，但您确实有足够的步骤去那里收集一些硬币并返回。
我希望这有帮助。