通过矩阵中的N个检查点的两点之间的最短路径 [英] Shortest path between two points through N checkpoints in a matrix
问题描述
如何在矩阵中找到两点之间的最短路径，即S和D？它应该通过多个检查点名为&。它不能通过G. *表示打开的门。路径可以通过目标和检查点任意多次。
示例：
< >
GGGGG
GS ** G
GGDGG
G **& G
GGGGG
此矩阵的输出应为6.
当你只有一个航点，你必须访问的问题很容易。你找到路径（例如使用A *）到航点，然后找到从航点到目标的路径。
当航点数量增加时，问题指数级更难，因为你必须考虑访问任何waypoint下一步。这将成为旅行推销员问题。
一般方法是通过选择看起来最好的路点来近似最短解，或者通过尝试所有可能性来找到最优解。
但是，你需要对这些进行自己的研究 - 远远超出了我们可以帮助的范围你在这里。
下一步是选择一种方法来实现。如果你不明白它，你可以问具体该方法的某些方面如何工作。但是，完整的解决方案是复杂的，所以你不会得到很多的编码帮助这样一个一般的问题。
解决方案你最好的打赌是深度优先分支和绑定搜索。这是一个深度优先搜索与修剪 - 消除的路径，保证是更糟的是你最好的解决方案到目前为止。您可以在多个网页上找到有关算法的信息，包括此一，但如果您有问题关于如何实施特定的算法，您应该开始处理该算法，然后询问有关该算法的新问题。
您的问题如何做到这一点已经由两个问题在这里回答了同样水平的细节你自己的问题。没有人会在这里为你发布一个完整的源代码解决方案，因为这听起来像一个类赋值。当你开始实施某些东西并陷入困境时，请随时提出另一个问题，了解究竟是什么让你陷入困境。
How to find shortest path between two points, namely S and D, in a matrix ? It should pass through multiple checkpoints named &. It cannot pass through G. * represents an open gate. Paths can pass through destination and checkpoints any number of times.
Example:
GGGGG GS**G GGDGG G**&G GGGGG
Output for this matrix should be 6.
The problem is easy when you only have one waypoint that you have to visit. You find the path (using A*, for instance) to the waypoint and then the path from the waypoint to the goal.
When the number of waypoints increases the problem gets exponentially harder, because you have to consider visiting any waypoint next. This becomes the Traveling Salesman Problem.
General approaches are to approximate the shortest solution by choosing the waypoint that looks best next, or to find the optimal solution by trying all possibilities. (The wikipedia page linked above goes into these.)
But, you'll need to do your own research on these -- far beyond the scope of what we can help you with here.
A good next step would be to choose an approach to implement. If you don't understand it you can ask specifically how some aspect of the approach works. But, full solutions are complicated, so you won't get much coding help with such a general question.
For optimal solutions your best bet is a depth-first branch and bound search. This is a depth-first search with pruning - eliminating paths that are guaranteed to be worse that your best solution so far. You can find information about the algorithm on many pages, including this one, but if you have a question about how to implement a specific algorithm you should start working on that algorithm and then ask a new question about that.
Your question of how to do it has been answered by both questions here at the same level of detail of your own question. Nobody is going to post a full source-code solution for you here, as this sounds like a class assignment. When you start implementing something and get stuck, feel free to ask another question about exactly what is getting you stuck.
这篇关于通过矩阵中的N个检查点的两点之间的最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
