3

最新の IEEE Xtreme コンペティションで、私が解決しようとした問題は次のとおりです。

入力 2 点 p1(x1,y1) , p2(x2,y2) p1 から p2 への最短経路の長さを見つける必要があります。

たとえば、 p1(1,1) 、 p2(4,4) の場合、最短パスの長さは 9 つのエッジになります。

ここに画像の説明を入力

私は深さ優先検索のようなことをしました.2点間の距離が小さく、例えば点(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();
    }
}

これより速い方法はありますか?? この無向グラフにダイクストラを使用できますか??

4

1 に答える 1

5

Dijkstra やあらゆる種類のグラフベースの検索を使用すると、ここでは完全にやり過ぎのように思えます。各頂点で、ターゲットに近づく次の頂点を選択するだけです。

したがって、(1,1) の中心から開始します。開始頂点を選択する必要があります。明らかに、これは南東にあるものです。

そこから、西へ移動、北東へ移動、南東へ移動の 3 つの選択肢があります。これは実際、2 つ目の頂点ごとに選択できます。あなたはあなたを近づける方向を選択します (つまり、ターゲットとの角度が最小になります)。

実際、すべての頂点座標を一種の不正な方法で表すことができます。それらはすべて六角形座標のほぼ中間にあることに注意してください。したがって、最初の頂点は にあると言えます(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)

したがって、考えられる方向ごとに、ターゲットまでの新しい距離 (カラスが飛ぶとき、つまりピタゴラス) をテストするだけです。3 つの選択肢の中で最小の距離を持つ新しい頂点を選択します。明らかに、実際の距離を計算する必要はありません。距離の 2 乗で問題ありません。

初動と終盤の動きを把握できるはずです。

最後のポイントとして、明らかに不正確な倍精度演算を使用しています。すべての方向 (そしてもちろん六角形の座標) を 6 でスケーリングし、整数を使用できます。

于 2012-11-11T23:13:01.797 に答える