1

私の著書(Artificial Intelligence A modern approach) では、遺伝的アルゴリズムは、人口と呼ばれるk 個のランダムに生成された状態のセットから始まると述べています。各状態は、有限のアルファベットの文字列 (最も一般的には 0 と 1 の文字列) として表されます。たとえば、8 クイーン状態では、それぞれが 8 つの正方形の列にある 8 つのクイーンの位置を指定する必要があるため、8 * log(2)8 = 24 ビットが必要です。別の方法として、状態を 1 から 8 の範囲の 8 桁で表すこともできます。

[ http://en.wikipedia.org/wiki/Eight_queens_puzzle ]

8 * log(2)8 = 24 ビットという式がわかりません。なぜ log2 ^ 8 なのですか? そして、これらの 24 ビットは何のためにあるのでしょうか?

4

2 に答える 2

1

ウィキペディアのページの最初の例を取り上げると、解は [2,4,6,8,3,1,7,5] としてエンコードできます。最初の数字は列 A の女王の行番号を示し、2 番目の数字は列 A の女王の行番号を示します。列Bの女王など。行の番号付けを 1 から始める代わりに、0 から始めます。解は [1,3,5,7,0,6,4] でエンコードされます。このように任意の位置をエンコードできます。
バイナリ 3 ビット (=log2(8)) で書き込めば、0 から 7 までの数字しかありません。

000 -> 0
001 -> 1
...
110 -> 6
111 -> 7

位置は 3 桁の 8 倍を使用してエンコードできます。たとえば、[1,3,5,7,2,0,6,4] から [001,011,101,111,010,000,110,100] またはもっと簡単に 001011101111010000110100 : 24 ビットを取得します。
逆に、ビット文字列 000010001011100101111110 は 000.010.001.011.100.101.111.110 としてデコードされ、[0,2,1,3,4,5,7,6] となり、[1,3,2,4,5,8, 7] : 列 A のクイーンは行 1、列 B のクイーンは行 3 などです。

于 2012-09-13T18:19:19.713 に答える
0

可能な正方形 (0 ~ 7 の 8 つの可能性) を格納するために必要なビット数は、log(2)8 です。2 進数の 111 は 10 進数の 7 であることに注意してください。8列の正方形を指定する必要があるため、3ビット8回必要です

于 2012-09-13T18:19:33.740 に答える