Ala*_*_AI 33 algorithm shortest-path
我知道有很多算法可用于计算图形或网格中两点之间的最短路径,如广度优先,全对(Floyd's),Dijkstra's.
但是,正如我所注意到的,所有这些算法都计算出该图或网格中的所有路径,而不仅仅是我们感兴趣的两点之间的路径.
我的问题是: 如果我有一个网格,即一个二维数组,我有兴趣计算两点之间的最短路径,比如P1和P2,如果我可以在网格上移动的方式有限制(例如,只对角,或只对角和向上等),什么算法可以计算这个？
请注意,如果您有答案,我希望您发布算法的名称而不是算法本身(当然,如果您也发布算法,则更好); 例如,无论是Dijkstra的算法,还是Floyd的算法,或者其他什么.
请帮助我,我几个月来一直在考虑这个问题!
好吧我们在TOPCODER.COM上发现这个算法在网格中你只能移动(对角线和向上)但我无法理解这是什么算法,任何人都知道？
#include<iostream>
#include <cmath>
using namespace std;
inline int Calc(int x,int y)
{
if(abs(x)>=abs(y)) return abs(x);
int z=(abs(x)+abs(y))/2;
return z+abs(abs(x)-z);
}
class SliverDistance
{
public:
int minSteps(int x1,int y1, int x2, int y2)
{
int ret=0;
if(((x1+y1)&1)!=((x2+y2)&1))y1++,ret++;
return ret+Calc(x2-x1,y2-y1);
}
};
IVl*_*lad 40
Lee的算法:http://en.wikipedia.org/wiki/Lee_algorithm
它本质上是一个BF搜索,这是一个例子:http://www.oop.rwth-aachen.de/documents/oop-2007/sss-oop-2007.pdf
要有效地实现它,请在此处检查我的答案:更改FloodFill算法以获取两个数据点的Voronoi Territory？ - 当我说马克时,你用你来自的位置上的数字+ 1标记它.
例如,如果你有这个网格,其中一个*=障碍物,你可以向上,向下,向左和向右移动,你从S开始,必须转到D,0 =自由位置:
S 0 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D
你将S放入队列中,然后"展开"它:
S 1 0 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D
然后展开所有邻居:
S 1 2 0
* * 0 *
* 0 0 *
0 0 * *
* 0 0 D
所有这些邻居的邻居:
S 1 2 3
* * 3 *
* 0 0 *
0 0 * *
* 0 0 D
等等,最终你会得到:
S 1 2 3
* * 3 *
* 5 4 *
7 6 * *
* 7 8 9
因此从S到D的距离是9.运行时间是O(NM),其中N =行数,M =列数.我认为这是在网格上实现的最简单的算法,它在实践中也非常有效.它应该比经典的dijkstra更快,虽然如果你用堆来实现它,dijkstra可能会赢.
您可能不知情。Dijkstra算法存在不同的变体。一个计算从每个点到每个其他点（如弗洛伊德的）的最短路径。
但是，典型的Dijkstra算法基于优先级队列，并且仅计算所需的最短路径。它在执行期间确实构造了几个路径，但是这些都是从A到最终解决方案路径上可能存在的从A到其他节点的部分路径。
因此，您可以轻松地将网格解释为图形（然后可以相应地考虑对角线之类的限制），并在Dijkstra中搜索从A到B的最短路径。这实际上仅是对问题进行建模的问题，而不是您需要一些精美的算法。