特定の例といくつかの一般原則に関する、ccoakleyの素敵な答えとstubbscrollのコメントに加えて、いくつかの発言。
この特定の問題には9つしかないというstubbscrollの発言について！= 362880 の異なる状態:
順列を数値としてエンコードする 1 つの (かなり簡単な) 方法は、辞書順で順列にインデックスを付けることです。例えば
0 1 2 3 --> 0
0 1 3 2 --> 1
0 2 1 3 --> 2
...
1 0 2 3 --> 6
1 0 3 2 --> 7
...
3 1 2 0 --> 21
3 2 0 1 --> 22
3 2 1 0 --> 23
トリックは階乗ベースでインデックスを書くことです、
n = a_1 * 1! + a_2 * 2! + a_3 * 3! + a_4 * 4! + ...
どこで0 <= a_k <= k。シンボルがある場合s、インデックスの範囲は 0 から s!-1 であるためs-1、n, の階乗ベース展開に係数があります(a_1,a_2,...,a_(s-1))。インデックス n の順列は、次のように求められます。
for i = 1 to s-1
the i-th symbol becomes the (a_(s-i)+1)-th smallest unused symbol
the last symbol is the left over one
それは特に明確ではないので、例を挙げます。{1,2,3,4,5,6,7,8} のインデックス 4231 を持つ順列を探すとします。まず、階乗ベースで 4231 を展開します。
4231 = 1 + 2*2115 : a_1 = 1
2115 = 0 + 3* 705 : a_2 = 0
705 = 1 + 4* 176 : a_3 = 1
176 = 1 + 5* 35 : a_4 = 1
35 = 5 + 6* 5 : a_5 = 5
5 = 5 + 7* 0 : a_6 = 5
それ以降のすべての係数 (ここでは a_7 のみ) は 0 です。a_i を逆の順序 (a_7、a_6、...a_1) で書く方がよいので、
coefficients symbols choice
0,5,5,1,1,0,1 1,2,3,4,5,6,7,8 1
5,5,1,1,0,1 2,3,4,5,6,7,8 7
5,1,1,0,1 2,3,4,5,6,8 8
1,1,0,1 2,3,4,5,6 3
1,0,1 2,4,5,6 4
0,1 2,5,6 2
1 5,6 6
- 5 5
結果: 17834265。
246351 のインデックスを見つけます。
symbols count perm index(head)
1,2,3,4,5,6 6 2,4,6,3,5,1 1 a_5 = 1
1,3,4,5,6 5 4,6,3,5,1 2 a_4 = 2
1,3,5,6 4 6,3,5,1 3 a_3 = 3
1,3,5 3 3,5,1 1 a_2 = 1
1,5 2 5,1 1 a_1 = 1
インデックスは `1*5! + 2*4! + 3*3! + 1*2! + 1*1! = 187。
これで、順列とそのインデックスを変換するかなり簡単な方法が得られました。変換は超高速ではありません (O(s^2)) が、簡単かつ高速な比較とルックアップが得られます (前に状態を見たことがありますか?)。それが利益であるかどうかは、それぞれのケースで決定される必要があります。
さて、当面の特定のケースでは、検索スペースを削減するいくつかの制限があります。
- 各移動は 3 つの要素の巡回順列であるため、偶順列です。
したがって、そのような動きのすべての組み合わせは偶数順列でもあり、可能な状態の半分は到達不可能です。(最大で) 9!/2 = 181440 の到達可能な州が残っています。辞書式順序付けによる偶数順列の索引付けは、わずかに複雑です。重要な点は、インデックスの階乗ベースの展開における係数 a_k の合計が偶数である場合にのみ、順列が偶数であるということです。
制約と対称性を使用して探索空間を減らします。考えられるすべての状態を持つ構造を使用する検索戦略を採用している場合、これにより、対応する係数だけメモリ要件が削減されます。検索戦略が到達可能な状態のみに触れる場合、制約によってステップ数が減ることはありませんが、メモリ フットプリントが小さいため、検索を高速化できます。対称性を使用すると、同等の状態を識別することでステップ数を減らすことができます。
例の問題では、5 がすでに正しい場所にあり、最適な解がそれを動かさないというさらに良い状況があります。したがって、8 つのシンボルの偶数順列を考慮するだけでよく、検索空間を 8!/2 = 20160 の可能な状態に減らします。（それは明らかではありませんが。）
ただし、一般に、最適な解が可能な状態の特定のサブセットを決して離れないことを証明することは困難であるため、そのような制限を検索に直接課すことはめったにありません。しかし、多くの場合、このような制限を使用して問題の適切な
解決策を
見つけ、その適切な解決策を使用して、制限のない検索空間で最適な解決策を探す初期段階で枝刈りを行うことができます。
よく使用できるバリアントは、貪欲な戦略によって近似を見つけ、これを限界として使用して、徹底的な検索の初期にプルーニングすることです。
