c++ - Hexagon 计划中的最短路径？

在最新的 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 吗？

最佳答案

使用 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)

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

你可以弄清楚最初和最后的 Action ，我敢肯定。

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

关于c++ - Hexagon 计划中的最短路径？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13336229/