我有一个最佳路径问题需要解决。 给定一个 nxn 网格，其中填充了可步行的瓷砖和不可步行的瓷砖，我必须通过最短路径从 A 点到达 B 点。 诀窍是一些可步行的瓷砖包含点。当我达到目标时，要成为一个有效的解决方案，我必须有一定数量的分数。 瓷砖上有可变数量的点(或没有)，我需要最短的路径才能到达目标，但在途中也至少收集了 M 个点。
我尝试的是 A* 算法，它找到 2 点之间的最短路径，并尝试对其进行自定义，使其不仅在达到目标时具有停止条件，而且还具有必要的点。它不像我做的那样工作，因为我挡住了路径。
如果您对如何解决此问题或其他更适合的算法有任何建议，我将不胜感激。 谢谢。
最佳答案
如果您仍然被这个问题所困，因为其他答案/评论只给了您部分答案——这里是问题空间的一个裂缝。
您实际上可以使用 A* 并进行一些修改来捕获(大部分)无序的 M 点路径。您唯一需要更改的是启发式和终止标准。
首先，您需要更改启发式以考虑通过 M 个点的路径。启发式必须是可接受的和一致的，因此它必须等于小于或等于真实路径成本的值，并且它只能在您接近目标时减少(必须单调递增)。
您可以将您现在选择的路径视为您必须完成的 M 条子路径，每条子路径都充当正常路径。因此，对于单点图(只有一个终止空间)，您可以使用标准启发式算法，如欧氏距离。这是一个贪婪的估计，表明直线路径是最优的，并且在理想情况下你不能做得更好(这是可以接受的)。
对于不止一条路径，贪心法同样表示点之间畅通无阻的直线路径是您可以走的最快路径。它仍然是一种一致的启发式方法，因为你不能走得更远并且仍然有更好的分数。困难的部分是在没有障碍的情况下选择 M 点的哪个排序最快，以保持可接受的启发式。您可以在图形中找到 M 点的最佳选择，其中所有图 block 都可以通过广度优先搜索欧几里德距离从当前图 block 到每个 M 点，到每个 M-1 剩余点，...，到终止广场。此操作非常昂贵，因为您需要为到达的每个方 block 都执行此操作——但您可以使用动态规划或搜索缓存将所需的分摊计算降低到每步 O(M)。
现在，一旦您有了 M 条无障碍最快的点路径，您就可以使用该路径中每个点与您当前位置之间的欧几里得距离作为启发式。这是一个贪婪的移动估计，所以它总是可以接受的(你不能超过估计的成本)并且它是一致的，因为你不能离开下一个贪婪的最佳点并减少你的成本，因为从当前的瓷砖中选择不同的贪婪点不会被接受。
最后，您的终止标准需要更改为达到 M 点，其中最后一个点是终止方 block 。这模仿了行走 M 图而不需要构造 M!可能的图走。所提供的启发式算法将让 A* 在不改变底层算法的情况下发挥它的魔力，并且应该尽可能有效，同时保持对通用网格上的启发式算法所需的约束。
关于c++ - 网格中的最佳路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/16020645/