六边形平面中的最短路径？

Question

六边形平面中的最短路径？

c++algorithmshortest-path

3

在最新的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();
    }
}

有没有比这更快的方法？我能在这个无向图中使用迪杰斯特拉算法吗？

- Rami Jarrar

也许可以使用广度优先搜索？ - irrelephant

使用深度优先搜索似乎是最糟糕的想法！广度优先搜索似乎是正确的选择（因为所有步骤大小相同，所以应该等同于最佳优先搜索）。考虑到从源到目标的方向已知，您还可以排除任何朝错误方向移动的内容。 - Dietmar Kühl

啊哈，我会尝试使用广度优先搜索算法，但是如何知道到达目标的方向呢？ - Rami Jarrar

在对六边形的边进行深度优先搜索之前，你可以先计算六边形的广度优先搜索：这样你就可以丢弃那些距离太远的六边形，从而减少空间。 - lucasg

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- paddy · Accepted Answer

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

所以你需要做的就是，针对每个可能的方向，测试到目标点的新距离（作为直线距离 - 即勾股定理）。选择具有三个选项中最小距离的新顶点。显然，您不必计算实际距离 - 距离平方是可以的。

我相信您可以找出初始和最终移动。

最后一点，显然我使用的是不精确的双倍浮点运算。您可以将所有方向（当然也包括您的六边形坐标）缩放6倍并使用整数。