c++ - 六边形计划中的最短路径？

Question

在最近的IEEE Xtreme竞赛中，我试图解决的一个问题是，

输入两点 p1(x1,y1) , p2(x2,y2) 你必须找到从 p1 到 p2 的最短路径的长度，

例如，如果 p1(1,1) , p2(4,4) 则最短路径的长度为 9 条边，

我做了深度优先搜索之类的东西，如果两点之间的距离很小，效果很好，例如点 (1,1) 和 (10,10) 需要很长时间，

并且最大点数是有限制的(12,12)。

我的做法是将上图转化为权值全部为1的无向图，然后求最短路径。

这是我找到最短路径的函数:

int minCost;
vector<int> path;
multimap<int,int> Connections;
typedef multimap<int,int>::iterator mmit;

void shortestPath(int cs){
    if(cs > minCost)
        return;
    if(path.back() == Target){
        if(cs < minCost)
            minCost = cs;
        return;
    }

    pair<mmit,mmit> it = Connections.equal_range(path.back());
    mmit mit = it.first;

    for( ; mit != it.second ; ++mit){
        if(isVisited(mit->second))
            continue;
        markVisited(mit->second);
        path.push_back(mit->second);
        shortestPath(cs+1);
        markUnvisited(mit->second);
        path.pop_back();
    }
}

还有比这更快的方法吗？？我可以为这个无向图使用 dijkstra 吗？？

Answer 1

在这里使用 Dijkstra 或任何一种基于图形的搜索似乎完全是矫枉过正。在每个顶点，您只需选择下一个使您更接近目标的顶点。

所以你从 (1,1) 的中心开始。您需要选择起始顶点。很明显这是东南方向的。

从那里，您有三个选择:向西移动、向东北移动或向东南移动。这实际上是您在每个第二个顶点处的选择。您选择使您更接近的方向(即，与您的目标成最小角度)。

事实上，您可以用一种作弊的方式表示所有的顶点坐标。请注意，它们都大致位于六边形坐标之间的中间位置。所以你可以说第一个顶点位于 (1.5,1.33)。

您在第一个坐标可能的移动是方向:

west       = (0, -0.67)
north-east = (-0.5, 0.33)
south-east = (0.5, 0.33)

让我们称之为奇怪的运动。现在，您有以下选择:

east       = (0, 0.67)
north-west = (-0.5, -0.33)
south-west = (0.5, -0.33)

因此，您所要做的就是，对于每个可能的方向，测试到您的目标的新距离(如乌鸦飞行 - ie 毕达哥拉斯)。选择三个选项中距离最小的新顶点。显然，您不必计算实际距离——距离的平方就可以了。

我敢肯定，您可以弄清楚初始和最终步骤。

最后一点，显然我使用的是不精确的 double 运算。您可以将所有方向(当然还有您的六边形坐标)缩放 6 并使用整数。