我有点糊涂了,我有以下模式
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. 例如考虑这种情况:
- 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.
更多推荐
以矩阵最短路径
发布评论