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();
    }
}

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

4

1 回答 1

5

Using Dijkstra or any kind of graph-based search seems like total overkill here. At each vertex, you just need to choose the next vertex that brings you closer to your target.

So you start in the centre of (1,1). You need to choose the starting vertex. Obviously this is the one in the south-east.

From there, you have three choices: move west, move north-east or move south-east. This is in fact the choice you have at every second vertex. You choose the direction that brings you closer (ie, subtends smallest angle with your target).

In fact, you can represent all your vertex co-ordinates in a sort of cheaty way. Notice that they are all roughly half-way between the hexagon coordinates. So you could say the first vertex is at (1.5,1.33).

Your possible moves at the first co-ordinate are the directions:

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 并使用整数。

于 2012-11-11T23:13:01.797 回答