如何在矩阵中找到两点(即 S 和 D)之间的最短路径？它应该通过多个名为 & 的检查点。它不能通过 G。 * 表示一个打开的门。路径可以多次通过目的地和检查点。
示例:
GGGGG GS**G GGDGG G**&G GGGGG
此矩阵的输出应为 6。
最佳答案
当您只有一个必须访问的航点时，问题就很简单了。您找到到路点的路径(例如，使用 A*)，然后找到从路点到目标的路径。
当路标数量增加时，问题会呈指数级增加，因为您必须考虑接下来访问任何路标。这变成了 Traveling Salesman Problem .
一般的方法是通过选择下一个看起来最好的航路点来近似最短的解决方案，或者通过尝试所有可能性来找到最佳解决方案。 (上面链接的维基百科页面进入这些。)
但是，您需要对这些进行自己的研究——这远远超出了我们在这里可以帮助您的范围。
下一步是选择一种实现方法。如果您不理解它，您可以具体询问该方法的某些方面是如何工作的。但是，完整的解决方案很复杂，因此对于这样一个一般性问题，您不会获得太多编码帮助。
对于最佳解决方案，您最好的选择是深度优先分支定界搜索。这是一个带有修剪的深度优先搜索——消除肯定比你目前最好的解决方案更糟糕的路径。您可以在许多页面上找到有关该算法的信息，包括 this one ，但如果您有关于如何实现特定算法的问题，您应该开始研究该算法，然后提出一个新的问题。
这里的两个问题都以与您自己的问题相同的详细程度回答了您关于如何执行此操作的问题。没有人会在这里为您发布完整的源代码解决方案，因为这听起来像是类作业。当您开始实现某事并遇到困难时，请随时提出另一个问题，了解究竟是什么让您陷入困境。
关于c++ - 通过矩阵中 N 个检查点的两点之间的最短路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/25428848/