8

多くのグラフ (最大数百万のグラフ比較) を比較する必要がありますが、それを行うための最速の方法は何でしょうか。

グラフの頂点は最大 8 つの隣接/エッジを持つことができ、頂点は値 0 または 1 を持つことができます。回転したグラフは同じグラフであり、すべてのグラフは同じ数の頂点を持ちます。

グラフは次のようになります。

グラフの例

現在、最初のグラフから 1 つの頂点を取得し、2 番目のグラフのすべての頂点と比較して、グラフを比較しています。同一の頂点が見つかった場合は、両方の頂点の隣接点が同一であるかどうかを確認し、グラフが同一かどうかがわかるまでこれを繰り返します。

このアプローチは遅すぎます。確実に異なるグラフを捨てずに、数千のグラフと約 100 の頂点を比較するのに 40 秒以上かかります。

すべてのグラフの一意の値を計算し、値のみを比較することを考えていました。私はこれをやろうとしましたが、等しい場合はグラフが等しい可能性があり、値が異なる場合はグラフも異なるという値しか思いつきませんでした。
私のプログラムがこれらの値を比較すると、約 2.5 秒ですべてが計算されます (それでも遅すぎます)。

そして、このグラフに頂点を追加してエッジを更新する最良/最速の方法は何ですか? std::map< COORD, Vertex >頂点を検索する方が簡単/高速だと思うので、現在このグラフを保存しています。
COORD はゲーム ボード上の頂点の位置 (頂点の位置はグラフを比較する際には関係ありません) であり、頂点は次のとおりです。

struct Vertex
{
    Player player; // Player is enum, FIRST = 0, SECOND = 1
    Vertex* neighbours[8];
};

そして、このグラフは、ボードの端でラッピングされた五目並べの現在のボードの状態と、ボードのサイズ n*n (n は 2^16 まで) を表しています。

これを書いている間、あまり多くの間違いを犯さなかったことを願っています。誰かが私を助けてくれることを願っています。

4

4 に答える 4

5

最初に、各グラフを一貫した表現にする必要があります。これを行う自然な方法は、グラフの順序付き表現を作成することです。

順序付けの最初のレベルは、近隣の数に従ってグループ化することによって実現されます。

次に、同じ数の隣接ノードを持つノードの各グループが、隣接ノードの値 (0 と 1) を 2 進数にマッピングすることによって並べ替えられ、グループ ノード間の順序を強制するために使用されます。

次に、順序付けられた形式で各グループの各ノードを反復処理するハッシュ関数を使用できます。ハッシュされた値を使用して、ルックアップを高速化できます

于 2013-04-04T19:30:40.987 に答える
3

あなたが解決しようとしている問題は、グラフ同形性と呼ばれます。

問題は NP にあり (NP-Complete かどうかは不明ですが)、そのための多項式時間アルゴリズムは見つかりませんでした。

あなたが説明するアルゴリズムは、指数関数的な時間がかかるようです。

于 2013-04-04T19:21:31.380 に答える
0

同形性をチェックするには、一方のボードをすべて n*n シフトでもう一方のボードの 8 回転を掛けてチェックすることで行うことができるため、O(n^3)複雑になることがわかりました。

これは に減らすことができますO(n^2)。軸を動かして、一方向にだけシフトしましょうx。y次に、適切な-offsetを見つけるだけです。このために、両方のグラフの要素を次のように連結します。

. . 1 .            0 . . 3
0 1 . .     =>     0 1 2 .     =>     0 3 0 1 2 0 2
. 0 . .            0 . 2 .
_______            
1 2 3 4            ^---- a 0 indicates start of a row

サイズの 2 つの配列を取得nし、一方が他方の巡回順列であるかどうかを確認する必要があります。このために、配列 a をそれ自体と連結し、もう一方を検索します。

たとえば、2 つの配列が でa=0301202あり、時間内に実行される KMP などを使用してinb=0203012を検索する場合(最初の配列は常に同じであるため、前処理全体を取り除くことができます)。020301203012020301202O(n + 2n)=O(n)

O(n)このx チェックをny シフトおよび8回転と組み合わせると、追加のスペースO(n^2)を使用して全体的に複雑になります。O(n)

于 2013-04-04T20:08:55.123 に答える