以矩阵最短路径 [英] Shortest path in a matrix

问题描述

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

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.

这篇关于以矩阵最短路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！