3

これまでの私のプログラムを説明しましょう。ルービックキューブソルバーです。スクランブル キューブが与えられます (これが初期状態です)。これがグラフのルート ノードになります。iterative deepening depth first searchこのスクランブルされた立方体を認識可能な状態にするために「総当たり」を使用しており、パターン認識を使用して解決できます。

ご想像のとおり、これは非常に大きなグラフなので、このグラフ内の重複ノードを検出するためのある種のハッシュ機能を考え出します (これにより、トラバーサルを高速化します)。

私はハッシュ関数にほとんど慣れていませんが、ここで私が考えていることは次のとおりです...各ノードは、本質的にルービックキューブの異なる状態です。なので、見たことのある立方体の状態（ノード）に来たら飛ばしたい。そのため、状態変数からチェックサム (状態変数は 54 文字の文字列) に移動するハッシュ関数が必要です。許可される文字はy, r, g, o, b, w(色に対応する) のみです。

このハッシュ関数の設計を手伝っていただければ幸いです。

4

5 に答える 5

2

暗号化ハッシュ関数はいつでも試すことができます。問題はセキュリティの問題ではないため (同じ値にハッシュされる個別の状態を意図的に見つけようとする攻撃者はいない)、壊れたハッシュ関数を使用できます。非常に高速な MD4を試すことをお勧めします。54 文字の文字列は、MD4 入力に非常に適しています (MD4 は最大 55 バイトの入力を 1 つのブロックとして処理できます)。

MD4Transform()基本的な 2.4 GHz PC は、単純な展開された C 実装 (たとえば、RFC 1320 に含まれるサンプル コードの関数のように見えるもの) を使用して、単一のコアを使用して、1 秒あたり約 1200 万のそのような文字列をハッシュできます。これで十分かもしれません。

于 2010-12-02T18:45:46.307 に答える
2

重複の検出と削除を最速で行うには、最初から多くの重複する位置を生成しないようにします。これは簡単に実行でき、繰り返しを生成してから見つけるよりも高速です。たとえば、F と B のような動きがある場合、サブ シーケンス FB を許可すると BF も許可されず、同じ結果が得られます。3F を行ったばかりの場合は、F を続けないでください。最後の 3 つの手が与えられた場合、許可された次の手の小さなルックアップ テーブルを生成できます。

残りの重複については、多くの位置があるため、高速なハッシュが必要です。他の人がコメントしているように、ハッシュを高速化するには、位置の表現であるハッシュ元を小さくする必要があります。12 個のエッジ キューブと 8 個のコーナー キューブがあります。各キュービーの位置と向きを表すには、キュービーごとに 5 ビット、つまり合計 100 ビット (12.5 バイト) しか必要ありません。エッジの場合、位置用の 4 ビットと反転用の 1 ビット。コーナーの場合、位置は 3 ビット、スピンは 2 ビットです。最後のエッジ キュービーは、その位置と反転が他のキュービーによって固定されているため、無視できます。この表現では、位置がすでに 12 バイトにまで減っています。

ルービックキューブの位置には約70ビットの実際の情報があり、96ビットは70に十分近いため、これらのビットをさらにハッシュすることは実際には生産的ではありません. つまり、このボードの表現をハッシュとして扱います。少し奇妙に聞こえるかもしれませんが、あなたの質問から、パターン マッチングにより適したコンパクトではないキューブの表現を同時に試してみることを想定しています。その場合、12 バイトの値は hash であるかのように扱うことができ、衝突のないハッシュであるという利点があります。これにより、テスト コードの複製と新しい値の挿入が短くなり、より簡単かつ高速になります。これまでに提案された MD5 ソリューションよりも安価になります。

繰り返される位置を検索する作業を削減するために使用できる他の多くのトリックがあります。アイデアについては、http://cube20.org/をご覧ください。

于 2010-12-02T20:48:52.710 に答える
2

1) ハッシュを使用しない9*6 = 54ルービック キューブに別々の面があります 。面ごとに 1 バイトを無駄に使用しても、これは 432 ビットであるため、ハッシュによってあまりスペースを節約することはできません。1 面あたり 3 ビットのより適切なパッキングは、162 ビット (21 バイト) になります。ルービックを表現するコンパクトな方法が必要なように思えます。

OTOH、以前に訪問した多くの状態のセットを保存しようとしている場合、真のセットの代わりにブルーム フィルターを使用すると、かなり低いスペース使用率でまともな結果が得られることがわかりました (ただし、最適ではないことがよくあります)。

2) ハッシュのアイデアと結婚している場合: MD5 を使用してください。提案されたルービックの状態よりもわずかにコンパクトで、かなり高速で、優れた衝突特性を備えています。悪意のある敵がルービック キューブ ハッシュを引き起こそうとしているようなものではありません。衝突;-)。

編集: MD4/MD5 などの暗号化ハッシュ関数の使用は、アルゴリズムを実装するライブラリまたは関数があれば、通常は簡単です (例: OpenSSL、GNU TLS、および多くのスタンドアロン実装が存在します)。通常、関数はvoid md5(unsigned char *buf, size_t len, unsigned char *digest)where がdigest事前に割り当てられた 16 バイトのバッファーを指し、bufハッシュされるデータ (ルービック キューブ構造) のようなものです。テストされていない C コードを次に示します。

#include <openssl/md5.h>
void main()
{
    unsigned char digest[16];
    unsigned char buf[BUFLEN];
    initializeBuffer(buf);
    MD5(buf,BUFLEN,digest);    // This is the openssl function
    printDigest(digest);
}

そして、必ずコンパイル/リンクして-lsslください。

于 2010-12-02T18:52:43.240 に答える
1

理論上の最小表現を確立するためだけに、有効なルービック キューブの状態空間は約4.3*10^19. Log 2 (4.3*10^19) は、上限が 66 であるその完全なスペースを表すために必要なビット数を決定します。したがって、理論的には、すべての有効な状態に番号を付けることができれば、任意の状態を 66 ビットで一意に表すことができます。

他の人のアドバイスに従い、立方体をよりコンパクトに表現する方法を見つけたいと思うかもしれませんが、状態をエッジ、コーナー、面の部分で表現することを検討してください。合法的な立方体移動のスワッピング法則により、12 個の 4 ビット エッジ位置、8 個の 3 ビット コーナー位置、および 6 個の 3 ビット フェース位置のシーケンスを連結できるはずです。これにより、90 ビットを使用した一意の表現が得られるはずです。

この表現は、ツリーを作成する方法には適していないかもしれませんが、一意であり、簡単に比較でき、既存の表現で与えられた状態を見つけることができるはずです。

于 2010-12-02T21:12:21.647 に答える