8 パズルの訪問済み状態が再び生成されないようにする方法を実装しようとしています。
私の最初のアプローチは、訪問した各パターンをリストに保存し、アルゴリズムが子を生成するたびに線形チェックを行うことでした。今、私はリストアクセスを通じて
これを間に合わせたいと思っています。O(1)8 パズルの各パターンは、1 から 9 までの数字の順列順列です (9 は空白のブロックです)。たとえば、125346987 は次のようになります。
1 2 5
3 4 6
_ 8 7
この種の可能な順列の総数は約 363,000 (9!) です。これらの数値をそのサイズのリストのインデックスにハッシュする最良の方法は何ですか?
N 個の項目の順列を、N 個の項目のすべての順列のリスト (辞書順) のインデックスにマップできます。
これを行うコードと、4 文字シーケンスのすべての順列に対して 0 から 23 までのインデックスを 1 回ずつ生成するデモを示します。
import itertools
def fact(n):
r = 1
for i in xrange(n):
r *= i + 1
return r
def I(perm):
if len(perm) == 1:
return 0
return sum(p < perm[0] for p in perm) * fact(len(perm) - 1) + I(perm[1:])
for p in itertools.permutations('abcd'):
print p, I(p)
コードを理解する最善の方法は、その正確性を証明することです。長さ n の配列の場合、(n-1)! 配列の最小要素が最初に現れる順列 (n-1)! 2 番目に小さい要素が最初に現れる順列など。
したがって、特定の順列のインデックスを見つけるには、順列の最初のものよりも小さいアイテムの数を数え、それに (n-1)! を掛けます。次に、（n-1）要素の順列と見なされる順列の残りのインデックスを再帰的に追加します。基本的なケースは、長さ 1 の順列がある場合です。明らかに、そのような順列は 1 つしかないため、そのインデックスは 0 です。
実際の例: [1324].
[1324]: 1 が最初に表示され、それが配列の最小要素であるため、0 * (3!) が得られます。[324]ます。最初の要素は 3 です。小さい要素が 1 つあるため、1 * (2!) となります。[24]ます。最初の要素は 2 です。これが残りの最小要素なので、0 * (1!) になります。[4]ます。要素は 1 つしかないため、基本ケースを使用して 0 を取得します。合計すると、0*3 になります。+ 1*2! + 0*1! + 0 = 1*2! = 2. [1324]4 つの順列のソートされたリストのインデックス 2 にあります。これは正解です。インデックス 0 は[1234]、インデックス 1 は[1243]であり、辞書順で次の順列は our であるため[1324]です。
順列を配列インデックスにマップする関数を求めていると思います。このディクショナリは、1 ～ 9 の数値のすべての順列を 0 ～ 9!-1 の値にマップします。
import itertools
index = itertools.count(0)
permutations = itertools.permutations(range(1, 10))
hashes = {h:next(index) for h in permutations}
たとえば、 hashes[(1,2,5,3,4,6,9,8,7)] は 1445 の値を返します。
タプルではなく文字列で必要な場合は、次を使用します。
permutations = [''.join(x) for x in itertools.permutations('123456789')]
または整数として：
permutations = [int(''.join(x)) for x in itertools.permutations('123456789')]
この問題に対するスペースとルックアップの効率的な構造はトライ タイプの構造です。これは、任意の順列で辞書式の一致に共通のスペースを使用するためです。つまり、1234 と 1235 で「123」に使用されるスペースは同じになります。
簡単にするために、例の「_」の代わりに0を想定しましょう。
保管
調べる
トライが 4 桁の例をどのように検索するかを次に示します。
Python トライ このトライは、myList などのブール値のリストに簡単に格納できます。ここの概念で説明されているように、myList[0] はルートです。
https://webdocs.cs.ualberta.ca/~holte/T26/tree-as-array.html
リストの最後のトライは、約 9+9^2+9^3....9^8 ビット、つまりすべてのルックアップで 10 MB 未満になります。
順列にアクセスしたことがあるかどうかだけに関心があるようです。
を使用する必要がありますset。O(1)興味のあるルックアップを許可します。
この特定のケース用のヒューリスティック関数を開発しました。[0,9!-1]マッピングは 間ではなく間であるため、完全なハッシュではありません[1,767359]が、 ですO(1)。
767359 ビットが 0 に設定されたファイル / 予約メモリ / が既にあると仮定しましょう (例: mem = [False] * 767359)。8puzzle パターンを python 文字列 (例: '125346987') にマッピングします。次に、ハッシュ関数は次のように決定されます。
def getPosition( input_str ):
data = []
opts = range(1,10)
n = int(input_str[0])
opts.pop(opts.index(n))
for c in input_str[1:len(input_str)-1]:
k = opts.index(int(c))
opts.pop(k)
data.append(k)
ind = data[3]<<14 | data[5]<<12 | data[2]<<9 | data[1]<<6 | data[0]<<3 | data[4]<<1 | data[6]<<0
output_str = str(ind)+str(n)
output = int(output_str)
return output
つまり、8puzzle パターン =125346987が既に使用されているかどうかを確認するには、次のようにする必要があります。
pattern = '125346987'
pos = getPosition(pattern)
used = mem[pos-1] #mem starts in 0, getPosition in 1.
完全なハッシングを行うと、9 個必要になります。ブール値を格納するビット。この場合、さらに 2 倍 ( 767359/9! = 2.11) が必要ですが、1Mb にも満たないことを思い出してください (かろうじて100KB )。
この関数は簡単に元に戻せることに注意してください。
これが機能する理由と、衝突が発生しない理由を数学的に証明できますが、これはプログラミング フォーラムなので、考えられるすべての順列に対して実行し、すべてのハッシュ値 (位置) が実際に異なることを確認してみましょう。
def getPosition( input_str ):
data = []
opts = range(1,10)
n = int(input_str[0])
opts.pop(opts.index(n))
for c in input_str[1:len(input_str)-1]:
k = opts.index(int(c))
opts.pop(k)
data.append(k)
ind = data[3]<<14 | data[5]<<12 | data[2]<<9 | data[1]<<6 | data[0]<<3 | data[4]<<1 | data[6]<<0
output_str = str(ind)+str(n)
output = int(output_str)
return output
#CHECKING PURPOSES
def addperm(x,l):
return [ l[0:i] + [x] + l[i:] for i in range(len(l)+1) ]
def perm(l):
if len(l) == 0:
return [[]]
return [x for y in perm(l[1:]) for x in addperm(l[0],y) ]
#We generate all the permutations
all_perms = perm([ i for i in range(1,10)])
print "Number of all possible perms.: "+str(len(all_perms)) #indeed 9! = 362880
#We execute our hash function over all the perms and store the output.
all_positions = [];
for permutation in all_perms:
perm_string = ''.join(map(str,permutation))
all_positions.append(getPosition(perm_string))
#We wan't to check if there has been any collision, i.e., if there
#is one position that is repeated at least twice.
print "Number of different hashes: "+str(len(set(all_positions)))
#also 9!, so the hash works properly.
この背後にある考え方は、ツリーと関係があります。最初は、それぞれが数字に対応する 9 つのノードに向かう 9 つの分岐があります。これらのノードのそれぞれから、8 つのノードに向かう 8 つのブランチがあり、それぞれが親を除く数字に対応し、次に 7 というようになります。
まず、入力文字列の最初の数字を別の変数に格納し、「ノード」リストからポップアウトします。これは、最初の数字に対応する分岐を既に取っているためです。
次に、8 つのブランチがあり、2 番目の桁に対応するブランチを選択します。8 つの分岐があるため、選択した分岐のインデックスを格納するには 3 ビットが必要であり、最大値111は 8 番目の分岐のものであることに注意してください (分岐 1 ～ 8 を binary にマップします000-111)。ブランチ インデックスを選択して保存したら、その値を取り出して、次のノード リストにこの数字が再び含まれないようにします。
分岐 7、6、および 5 についても同様に処理を進めます。最大値は になりますが、7 つの分岐がある場合でも 3 ビットが必要であることに注意してください110。5 つのブランチがある場合、インデックスはせいぜい binary になり100ます。
次に、4 つのブランチに到達します。これは、3 つのブランチの場合と同じように、2 ビットだけで格納できることに気付きます。2 つの分岐の場合は 1 ビットだけ必要で、最後の分岐の場合はビットは必要ありません。最後の桁を指す分岐が 1 つだけあり、元の 1-9 リストの残りになります。
これまでのところ、分離された変数に格納されている最初の数字と、ブランチを表す 7 つのインデックスのリストがあります。最初の 4 つのインデックスは 3 ビットで表現でき、次の 2 つのインデックスは 2 ビットで表現でき、最後のインデックスは 1 ビットで表現できます。
アイデアは、このすべてのインデックスをビット形式で連結して、より大きな数を作成することです。17 ビットなので、この数は最大で2^17=131072. ここで、格納した最初の数字をその数字の末尾に追加するだけです (最大でこの数字は 9 になります)。作成できる最大の数字は です1310729。
しかし、もっとうまくやることができます: 最大値は binary でしたが、5 つの分岐があるときは 3 ビットが必要だったことを思い出してください100。0 の数が多いビットが最初になるようにビットを配置するとどうなるでしょうか。その場合、最悪のシナリオでは、最終的なビット番号は次の連結になります。
100 10 101 110 111 11 1
10 進数で は76735です。次に、前と同じように処理を進め (末尾に 9 を追加)、可能な最大の生成数は767359であり、これは必要なビットの量であり、入力 string987654321に対応し、最小の可能な数は1入力 string に対応します123456789。
最後に、なぜ最初の数字を別の変数に格納して最後に追加したのか疑問に思うかもしれません。その理由は、それを保持していた場合、最初の分岐の数は 9 であったため、最初のインデックス (1-9) を格納するために 4 ビット ( 0000～1000) が必要だったからです。その場合、可能な最大数 (したがって、必要なメモリ量) は次のようになります。
1000 100 10 101 110 111 11 1
これは 10 進数で 1125311 です (1.13Mb 対 768Kb)。1.13M/0.768K = 1.4710 進数の値 ( ) を加算するだけの場合と比較して、比率が 4 ビットの比率と関係があることを確認するのは非常に興味深いことです2^4/10 = 1.6(違いは、最初のアプローチでは4 ビットを完全には使用していません)。
hash(125346987) と入力すると、125346987 が返されることに注意してください。これには理由があります。整数を整数以外にハッシュする意味がないからです。
あなたがすべきことは、パターンを見つけたら、それをリストではなく辞書に追加することです。これにより、現在行っているようにリストをトラバースするのではなく、必要な高速検索が提供されます。
したがって、実行できるパターン 125346987 を見つけたとします。
foundPatterns = {}
#some code to find the pattern
foundPatterns[1] = 125346987
#more code
#test if there?
125346987 in foundPatterns.values()
True
初め。ブール値のリストよりも高速なものはありません。タスクには可能な順列の合計があり9! == 362880ます。これは、メモリに保存するのに十分な少量のデータです。
visited_states = [False] * math.factorial(9)
または、バイト配列を使用することもできます。これは、わずかに遅く (それほどではありません)、メモリ フットプリントがはるかに小さくなります (少なくとも 1 乗分)。ただし、配列を使用することによるメモリの節約は、次のステップを考えるとおそらくほとんど価値がありません。
2番。特定の順列をそのインデックスに変換する必要があります。これを行うアルゴリズムがあります。このトピックに関する最も優れた StackOverflow の質問の 1 つは、おそらく次の質問です。
permutation size が固定されているn == 9ため、アルゴリズムの複雑さに関係なく、状況では O(1) と同等になります。
ただし、さらに高速な結果を生成するために、O(1) ルックアップを提供するマッピング ディクショナリを事前設定することができます。
all_permutations = map(lambda p: ''.join(p), itertools.permutations('123456789'))
permutation_index = dict((perm, index) for index, perm in enumerate(all_permutations))
このディクショナリは約 50 MB のメモリを消費しますが、実際にはそれほど多くはありません。特に、一度だけ作成する必要があるためです。
これがすべて完了したら、特定の組み合わせを確認するには、次のようにします。
visited = visited_states[permutation_index['168249357']]
訪問済みのマークは、同じ方法で行われます。
visited_states[permutation_index['168249357']] = True
順列インデックス アルゴリズムを使用すると、マッピング ディクショナリよりもはるかに遅くなることに注意してください。これらのアルゴリズムのほとんどは O(n 2 ) の複雑さであり、あなたの場合、余分な python コード自体を割り引いても 81 倍のパフォーマンスが低下します。そのため、メモリの制約が大きい場合を除き、マッピング ディクショナリを使用するのがおそらく速度的に最適なソリューションです。
補遺。Palec が指摘したように、visited_stateslist は実際にはまったく必要ありません。 True/False値を辞書に直接保存することは完全に可能permutation_indexであり、メモリと追加のリスト検索を節約できます。