algorithm - 一意のフリーポリオミノ (またはポリオミノハッシュ) を識別するアルゴリズム

Question

要するに、無料のポリオミノをハッシュする方法は?

これは次のように一般化できます:任意の 2D 整数座標のコレクションを効率的にハッシュする方法。セットには負でない整数の一意のペアが含まれており、変換、回転、反転のいずれもマッピングできない場合にのみ、セットは一意と見なされます。別のセットと同じですか？

せっかちな読者のために、私は力ずくのアプローチを十分に認識していることに注意してください. 私はより良い方法を探しています -- または、他の方法が存在しないという非常に説得力のある証拠を探しています。

ランダムなポリオミノを生成するために、いくつかの異なるアルゴリズムに取り組んでいます。それらの出力をテストして、それらがどの程度ランダムであるかを判断したいと思います。つまり、特定の注文の特定のインスタンスが他のインスタンスよりも頻繁に生成されているかどうかを判断します。視覚的に、フリーポリオミノのさまざまな方向を識別するのは非常に簡単です。たとえば、次のウィキペディアの図は、「F」ペントミノの 8 つの方向すべてを示しています (出典)。

ザ・ファ・ペンティミノ

このポリオミノにどのように数字を付けるか、つまり、自由なポリオミノをハッシュしますか? 「名前付き」ポリオミノの事前に入力されたリストに依存したくありません。とにかく、広く合意された名前はオーダー 4 と 5 にのみ存在します。

これは、特定の順序のすべての自由 (または片側または固定) ポリオミノを列挙することと必ずしも同等ではありません。特定の構成が表示される回数を数えたいだけです。生成アルゴリズムが特定のポリオミノを生成しない場合、それは単にカウントされません。

カウントの基本的なロジックは次のとおりです。

testcount = 10000 // Arbitrary
order = 6         // Create hexominos in this test
hashcounts = new hashtable
for i = 1 to testcount
    poly = GenerateRandomPolyomino(order)
    hash = PolyHash(poly)
    if hashcounts.contains(hash) then  
        hashcounts[hash]++
    else
        hashcounts[hash] = 1

私が探しているのは、効率的なPolyHashアルゴリズムです。入力ポリオミノは、座標のセットとして単純に定義されます。T tetronimo の 1 つの向きは、たとえば次のようになります。

[[1,0], [0,1], [1,1], [2,1]]:

 |012
-+---
0| X
1|XXX

入力 polyomino は、X 軸と Y 軸に対して整列するように既に正規化されており、正の座標のみを持っていると想定できます。正式には、各セット:

x 値が 0 の座標が少なくとも 1 つある
y 値が 0 である座標が少なくとも 1 つある
x < 0 または y < 0 の座標はありません

以下で説明する、一般的な力ずくのアプローチで必要とされる整数演算の数の増加を回避する新しいアルゴリズムを本当に探しています。

強引な

こことここで提案されているブルートフォースソリューションは、各座標をバイナリフラグとして使用して各セットを符号なし整数としてハッシュし、すべての可能な回転 (および私の場合は反転) の最小ハッシュを取得することで構成されます。各回転/反転も必要です。原文に訳します。これにより、「フリー」ハッシュを取得するために、入力セットごとに合計 23 のセット操作が行われます。

回転 (6x)
フリップ (1x)
翻訳 (7x)
ハッシュ (8x)
計算されたハッシュの最小値を見つける (1x)

各ハッシュを取得する一連の操作は次のとおりです。

ハッシュ
回転、平行移動、ハッシュ
回転、平行移動、ハッシュ
回転、平行移動、ハッシュ
反転、変換、ハッシュ
回転、平行移動、ハッシュ
回転、平行移動、ハッシュ
回転、平行移動、ハッシュ

score 12 · Accepted Answer

さて、私はまったく異なるアプローチを思いつきました。(また、有益な洞察を提供してくれた corsiKa にも感謝します!) 正方形をハッシュ/エンコードするのではなく、それらの周りのパスをエンコードします。パスは、各ユニットセグメントを描画する前に実行する一連の「ターン」(ターンなしを含む) で構成されます。正方形の座標からパスを取得するアルゴリズムは、この質問の範囲外だと思います。

これは非常に重要なことを行います。必要のないすべての位置情報と方向情報が破棄されます。反転したオブジェクトのパスを取得するのも非常に簡単です。要素の順序を逆にするだけです。各要素は 2 ビットしか必要としないため、ストレージはコンパクトです。

追加の制約が 1 つ導入されます: polyomino には完全に囲まれた穴があってはなりません。(正式には、単純に接続する必要があります。) ポリオミノに関するほとんどの議論では、接触する 2 つの角だけで塞がれている場合でも穴が存在すると見なされます。エッジのトレースは、コーナーに接触しても妨げられませんが (穴のある単一のヘプトミノのように)、完全なリング型のオクトミノのように、1 つの外側のループから内側のループにジャンプすることはできません。

ここに画像の説明を入力

また、エンコードされたパスループの最小順序を見つけるという、もう 1 つの課題も発生します。これは、(文字列の回転という意味での) パスの回転が有効なエンコーディングであるためです。常に同じエンコーディングを取得するには、パス命令の最小 (または最大) 回転を見つける必要があります。ありがたいことに、この問題はすでに解決されています。たとえば、http://en.wikipedia.org/wiki/Lexicographically_minimal_string_rotationを参照してください。

例：

移動操作に次の値を任意に割り当てた場合:

ノーターン：1
右折：2
左折: 3

以下は F ペントミノを時計回りにトレースしたものです。

ここに画像の説明を入力

F ペントミノの任意の初期エンコーディングは次のとおりです (右下隅から):

2,2,3,1,2,2,3,2,2,3,2,1

エンコードの結果の最小回転は次のとおりです。

1,2,2,3,1,2,2,3,2,2,3,2

12 要素の場合、このループは、命令ごとに 2 ビットを使用する場合は 24 ビットにパックでき、命令が 3 の累乗としてエンコードされている場合は 19 ビットのみにパックできます。2 ビット要素エンコーディングを使用しても、単一の符号なし 32 ビット整数に簡単に収まります0x6B6BAE。

   1- 2- 2- 3- 1- 2- 2- 3- 2- 2- 3- 2
= 01-10-10-11-01-10-10-11-10-10-11-10
= 00000000011010110110101110101110
= 0x006B6BAE

ループの開始点が 3 の最上位ベキである base-3 エンコーディングは次の0x5795Fとおりです。

    1*3^11 + 2*3^10 + 2*3^9 + 3*3^8 + 1*3^7 + 2*3^6 
  + 2*3^5  + 3*3^4  + 2*3^3 + 2*3^2 + 3*3^1 + 2*3^0
= 0x0005795F

次数の polyomino の周りのパスの頂点の最大数nはです2n + 2。2 ビット符号化の場合、ビット数は移動数の 2 倍であるため、必要な最大ビット数はです4n + 4。base-3 エンコーディングの場合は次のとおりです。

ベース 3 でエンコードされた最大ビット数

「絞首台」は天井機能です。したがって、次数 9 までのポリオミノは、単一の 32 ビット整数にエンコードできます。これを知っていれば、ハッシュするポリオミノの最大次数を考慮して、最速のハッシュ比較に応じてプラットフォーム固有のデータ構造を選択できます。

score 4 · Accepted Answer

反転、回転、または再変換する必要なく、8 つのハッシュ操作に減らすことができます。

このアルゴリズムは、それ自体を基準とした座標で操作していることを前提としていることに注意してください。つまり、野生ではないということです。

反転、回転、平行移動の操作を適用する代わりに、ハッシュの順序を変更するだけです。

たとえば、上記の F pent を考えてみましょう。簡単な例では、ハッシュ操作が次のようなものであると仮定しましょう:

int hashPolySingle(Poly p)
    int hash = 0
    for x = 0 to p.width
        fory = 0 to p.height
            hash = hash * 31 + p.contains(x,y) ? 1 : 0
    hashPolySingle = hash

int hashPoly(Poly p)
    int hash = hashPolySingle(p)
    p.rotateClockwise() // assume it translates inside
    hash = hash * 31 + hashPolySingle(p)
    // keep rotating for all 4 oritentations
    p.flip()
    // hash those 4

関数をポリゴンの 8 つの異なる方向すべてに適用する代わりに、8 つの異なるハッシュ関数を 1 つのポリゴンに適用します。

int hashPolySingle(Poly p, bool flip, int corner)
    int hash = 0
    int xstart, xstop, ystart, ystop
    bool yfirst
    switch(corner)
        case 1: xstart = 0
                xstop = p.width
                ystart = 0
                ystop = p.height
                yfirst = false
                break
        case 2: xstart = p.width
                xstop = 0
                ystart = 0
                ystop = p.height
                yfirst = true
                break
        case 3: xstart = p.width
                xstop = 0
                ystart = p.height
                ystop = 0
                yfirst = false
                break
        case 4: xstart = 0
                xstop = p.width
                ystart = p.height
                ystop = 0
                yfirst = true
                break
        default: error()
    if(flip) swap(xstart, xstop)
    if(flip) swap(ystart, ystop)

    if(yfirst)
        for y = ystart to ystop
            for x = xstart to xstop
                hash = hash * 31 + p.contains(x,y) ? 1 : 0
    else
        for x = xstart to xstop
            for y = ystart to ystop
                hash = hash * 31 + p.contains(x,y) ? 1 : 0
    hashPolySingle = hash

これは、8 つの異なる方法で呼び出されます。また、hashPolySingle を for ループにカプセル化して、コーナーの周りやフリップの周りにカプセル化することもできます。すべて同じです。

int hashPoly(Poly p)
    // approach from each of the 4 corners
    int hash = hashPolySingle(p, false, 1)
    hash = hash * 31 + hashPolySingle(p, false, 2)
    hash = hash * 31 + hashPolySingle(p, false, 3)
    hash = hash * 31 + hashPolySingle(p, false, 4)
    // flip it
    hash = hash * 31 + hashPolySingle(p, true, 1)
    hash = hash * 31 + hashPolySingle(p, true, 2)
    hash = hash * 31 + hashPolySingle(p, true, 3)
    hash = hash * 31 + hashPolySingle(p, true, 4)
    hashPoly = hash

このように、ポリゴンを各方向から暗黙的に回転させますが、実際には回転と移動を実行していません。これは、8 つの方向すべてを正確にハッシュするために完全に必要と思われる 8 つのハッシュを実行しますが、実際にハッシュを実行していないポリゴン上のパスを無駄にしません。これは私には最もエレガントなソリューションのようです。

使用するより良い hashPolySingle() アルゴリズムがあるかもしれないことに注意してください。私のは、オーダーのデカルト枯渇アルゴリズムを使用しO(n^2)ます。その最悪のシナリオは L 字型であり、要素N/2 * (N-1)/2のみのサイズの正方形、またはの効率が、I 字型のと比較されます。また、アーキテクチャによって課される固有の不変条件により、実際には単純なアルゴリズムよりも効率が低下する可能性もあります。N1:(N-1)/41:1

私の疑惑は、ノードのセットをトラバース可能な双方向グラフに変換することでデカルトの枯渇をシミュレートすることで、上記の懸念を軽減できるのではないかと考えています。空きスペースは無視。O(n)これにより、グラフを時間内に構築できるようになるため、アルゴリズムが低下しO(n)ます。私はこれをやったことがないので、確かなことは言えません。

score 3 · Accepted Answer

これが私のDFS（深さ優先検索）の説明です：

一番上のセルから始めます (タイブレーカーとして一番左)。訪問済みとしてマークします。セルを訪問するたびに、訪問していない隣人がないか、4 つの方向すべてを確認してください。常に上、左、下、右の順に 4 方向を確認してください。

例

ここに画像の説明を入力

この例では、上と左は失敗しますが、下は成功します。これまでの出力は 001 で、「下」のセルを再帰的に検索します。

新しい現在のセルを訪問済みとしてマークします (このセルの検索が終了すると、元のセルの検索も終了します)。ここでは、上 = 0、左 = 1 です。

一番左のセルを検索し、未確認の隣接セルはありません (上 = 0、左 = 0、下 = 0、右 = 0)。これまでの総出力は 001010000 です。

ここに画像の説明を入力

2 番目のセルの検索を続けます。下=0、右=1。右側のセルを検索します。

ここに画像の説明を入力

上=0、左=0、下=1。下のセルを検索します。すべて 0 です。これまでの合計出力は 001010000010010000 です。次に、下のセルから戻ります...

ここに画像の説明を入力

右=0、戻ります。戻る。(今、開始セルにいます。) right=0. 終わり！

したがって、合計出力は 20 (N*4) ビット、つまり 00101000001001000000 です。

エンコーディングの改善

しかし、いくつかのビットを節約できます。

最後にアクセスしたセルは、その 4 つの方向に対して常に 0000 をエンコードします。したがって、最後にアクセスしたセルをエンコードして 4 ビットを節約しないでください。

別の改善: 左に移動してセルに到達した場合、そのセルの右側をチェックしないでください。したがって、最初のセルに 4 ビット、最後のセルに 0 ビットを除いて、セルごとに 3 ビットしか必要ありません。

最初のセルには上または左の隣接セルがないため、これらのビットは省略します。したがって、最初のセルには 2 ビットが必要です。

したがって、これらの改善により、N*3-4 ビットのみを使用します (例: 5 セル -> 11 ビット; 9 セル -> 23 ビット)。

本当に必要な場合は、正確に N-1 ビットが「1」になることに注意して、もう少しコンパクトにすることができます。

警告

はい、polyomino の 8 回の回転/フリップすべてをエンコードし、正規のエンコードを取得するには最小のものを選択する必要があります。

これはアウトラインアプローチよりもまだ速いと思います。また、ポリオミノの穴は問題になりません。

score 1 · Accepted Answer

polyominoを (ハッシュするだけでなく) 一意に識別するトライのようなものを設定できます。正規化された polyomino を使用して、(0,0) にピクセルが設定されているかどうかでルートが分岐し、(0,1) にピクセルが設定されているかどうかで次のレベルに分岐するというように、二分探索ツリーを設定します。ポリオミノを調べるときは、単純に正規化してからツリーをたどります。トライで見つかったら完了です。そうでない場合は、その polyomino に一意の ID を割り当て (カウンターをインクリメントするだけ)、8 つの可能な回転と反転をすべて生成し、それらの 8 つをトライに追加します。

トライミスでは、すべての回転と反射を生成する必要があります。しかし、トライヒットの場合はコストが低くなります (k-ポリオミノの場合は O(k^2))。

ルックアップをさらに効率的にするには、一度に数ビットを使用し、バイナリツリーの代わりにより広いツリーを使用します。

score 1 · Accepted Answer

私は最近同じ問題に取り組みました。この問題はかなり簡単に解決できました。(1) polyomino の一意の ID を生成し、同一の各 poly が同じ UID を持つようにします。たとえば、境界ボックスを見つけ、境界ボックスの角を正規化し、空でないセルのセットを収集します。(2) ポリオミノを回転 (および必要に応じて反転) して可能なすべての順列を生成し、重複を探します。

このブルートアプローチの利点は、その単純さ以外に、ポリゴンが他の方法で区別できる場合 (たとえば、ポリゴンの一部が色付けされているか番号が付けられている場合) に機能することです。

score 0 · Accepted Answer

ハッシュの衝突が本当に怖い場合、有効なハッシュ関数は、座標に対してハッシュ関数 x + order * y を作成し、ピースのすべての座標をループして (order ^ i) * hash(coord[ i]) ピースハッシュに。そうすれば、ハッシュの衝突が発生しないことを保証できます。

algorithm - 一意のフリー ポリオミノ (またはポリオミノ ハッシュ) を識別するアルゴリズム

6 に答える 6

例

エンコーディングの改善

警告

Related

Reference

algorithm - 一意のフリーポリオミノ (またはポリオミノハッシュ) を識別するアルゴリズム