以矩阵最短路径

本文介绍了以矩阵最短路径的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我有点糊涂了，我有以下模式

I am a bit confused, i have following pattern

S...*... ....*..... **...**. .G1....*. ........ ...G2**.. ........ ....*.G3D

传说的含义如下：

meaning of legends are as follows

S = source D = Destination G = point to be visited before reaching destination . = paths * = blocked path

请问这种做法给我的最短路径？

Will this approach give me the shortest path?

Distance = Min((S,G1) (S,G2) (S,G3)) Distance = Distance + Min((G1,G2) (G1,G3)) // Assuming that G1 is shortest Distance = Distance + Distance(G3 , D)

G points can be randomly distributed and i am using BFS

G＆LT; 15和矩阵LT = 100×100

G<15 and matrix <= 100x100

推荐答案

没有。这是行不通的。那是什么叫做贪婪的办法，也不会工作，因为它可能会迫使你做不好的最后一步。

No. That won't work. That is what's called a greedy approach, and it will not work because it may force you to do a bad last move.

例如考虑这种情况：

S G3 G1 G2 D

• G1 最接近取值，以便将第一选择。
• G2 则是最接近 G1 ，以便将第二选择
• 左是 G3
• G1 is closest to S, so that will be chosen first.
• G2 is then closest to G1, so that will be chosen second
• Left is G3

即。你的方法将选择 G1 ， G2 ， G3 而最佳的解决方案是访问 G3 ， G1 然后 G2 的一条直线上。

i.e. your approach will chose G1, G2, G3 while the optimal solution is to visit G3, G1 then G2 in a straight line.

事实上，这是微不足道的减少旅行商问题这个问题。只需设置取值和 D 彼此相邻。这证明了你所描述的问题是NP难的，也就是说你不能做的比穷举搜索更好。

In fact, it's trivial to reduce the traveling salesman problem to this problem. Just set S and D next to each other. This proves that the problem you're describing is NP-hard, i.e. you can't do better than an exhaustive search.