每个人都知道在矩阵中找到最短路径的经典问题。假设 0 表示空闲单元，1 表示墙，S 表示开始，F 表示结束。通过广度优先搜索解决。我需要解决一个类似的问题：现在地图上也有物体，你需要将它们全部收集并返回到S点（F点不再存在，因为不需要它）。你需要找到最短的路线。我有这样一个想法：每次都找到最近的物体，然后捡起来。但我不确定这样的算法是否有反测试，而且我通常无法证明其正确性。有人能准确地告诉我这个算法是否正确吗？或者提供一个 100% 正确的算法。
RError.com
每个人都知道在矩阵中找到最短路径的经典问题。假设 0 表示空闲单元，1 表示墙，S 表示开始，F 表示结束。通过广度优先搜索解决。我需要解决一个类似的问题：现在地图上也有物体，你需要将它们全部收集并返回到S点（F点不再存在，因为不需要它）。你需要找到最短的路线。我有这样一个想法：每次都找到最近的物体，然后捡起来。但我不确定这样的算法是否有反测试，而且我通常无法证明其正确性。有人能准确地告诉我这个算法是否正确吗？或者提供一个 100% 正确的算法。
很容易证明，所提出的贪心算法不一定能找到最优解。图中反例：
在这种情况下，算法将构建路线 S-1-2-3-4-5-S，而另一条路线将是最优的：S-1-2-5-3-4-S。
一般来说，这是您遇到的一种旅行商问题，请朝这个方向看。
很明显，这是最佳算法，您不会比每个对象的最短路径更快。而且由于每一步都没有其他障碍，因为我们在上一步消除了它们，那么你到达每个对象的路径将是最短的。但是这里也不需要波浪算法，因为障碍是分阶段消除的，并且在每个阶段基本上没有障碍。
如果任务中的每个项目都需要单独返回到 F 点，就会出现这种情况。如果全部一起，则不是最优的，请参见 Yaant 的示例。