4

私は Ant Colony Optimization による 15 パズル ソルバーを実装しており、各状態を効率的に数値にハッシュする方法を考えているため、バイトの無駄遣いを最小限に抑えています。

状態は、0 から 15 までの 16 個の数字のリストで表されます (0 は穴)。

お気に入り：

[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0]

そのため、その州を識別するための一意の番号を作成したいと考えています。すべての数字を 16 進数に変換できますが、あまり効率的ではないと思います。

ありがとう

4

2 に答える 2

7

あなたの状態は、16 要素の順列に同型です。それらを列挙するには 45 ビットの数値で十分ですが (log2 16!)、それが有益な場合は 64 ビットに丸めることもできます。問題は、状態の列挙における状態からその位置への効率的な変換を見つけることになります。

0..16 の各数値が 1 回しか発生しないことがわかっているため、それぞれ log2 16 = 4 ビットの 16 個の変数を作成できます。ここで、i番目の変数は数値 i が発生する位置を示します。これにはかなりの冗長性があります。log2(16) * 16 ビットかかりますが、それは正確に 64 ビットです。かなり効率的に実装できます (テストされていない疑似コード):

state2number(state):
  idx = 0
  for i in [0;16):
    val = state[i]
    idx |= i << (val * 4)
  return idx

これが「すべての数字を 16 進数に変換する」という意味かどうかはわかりません。それは非常に効率的で、アンロールされた場合やマイクロ最適化された場合は、わずか数十サイクルです。必要以上に2バイトかかりますが、64ビットは依然としてスペース効率が高く、64ビットでも45ビットでも、配列へのインデックスとして直接使用することはできません。

于 2013-12-23T23:59:09.840 に答える
3

16あります！= 2.09*10^13 の可能な状態で、エンコードには約 44.25 ビットが必要です。

したがって、状態をバイト単位でエンコードする場合は、少なくとも 6 バイトが必要です。

このようにエンコードしない理由:
値に a、b、c、d、e、f、g、h、i、j、k、l、m、n、o、p という名前を付けましょう。

値は次のとおりです。

b`:= b - (b>a)?1:0;
c`:= c - (c>a)?1:0 - (c>b)?1:0
d`:= d - (d>a)?1:0 - (d>b)?1:0 - (d>c)?1:0
....

hashNumber= a+b *15+c*15*14+d`*15*14*15+....

これにより、考えられる各ステートの 6 バイトに収まる数値への全単射マッピングが得られます。

また、必要に応じて、数値を参照状態に戻すのは非常に簡単です。

最適ではありませんが高速です:
15*4 ビット = 60 ビットを必要とする各数値に 4 ビットを使用します (前の 15 数値から計算できるため、最後の数値は省略します)。7.5 バイトで保存できますが、それ以上無駄にしてもよい場合は、単純に 8 バイトを使用してください。

于 2013-12-24T00:00:50.613 に答える