Python エイト・クイーン問題 |
「総当りした場合と、適切に枝刈りした場合では実装速度に
大きな差が出る。アルゴリズムは適切に選択しましょう。」
という内容だったかと思います。
どの程度差がでるのか試してみたときのメモです。
#総当りロジック
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import time, copy
#縦・横・斜で重複が存在しないかチェックする
def check8q(q):
ans = copy.copy(q)
while(True):
target = q[0]
del(q[0])
#横方向に重複があるか確認
if target in q:
return
#斜めに重複があるか確認
for i, t in enumerate(q):
if target + (i + 1) == t or target - (i + 1) == t:
return
#キューがなくなるまで確認できれば正当
if len(q) == 0:
#結果を出力
print ans
break
if __name__ == '__main__':
#総当り
t1 = time.time()
#8重ループ
for i1 in range(8):
for i2 in range(8):
for i3 in range(8):
for i4 in range(8):
for i5 in range(8):
for i6 in range(8):
for i7 in range(8):
for i8 in range(8):
check8q([i1,i2,i3,i4,i5,i6,i7,i8])
t2 = time.time()
print t2 - t1,'sec'
#枝刈りロジック
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import time
def check8q(q):
#配置する要素が存在するか
if -1 in q:
#配置する要素のインデックスを取得
index = q.index(-1)
for i in range(8):
#配置しようとする要素がリストに存在する場合は、
#処理スキップ
if i in q:
continue
#斜めに重複が存在する場合は処理スキップ
isbreak = False
for j in range(index):
if i - (index - j) == q[j] or i + (index - j) == q[j]:
isbreak = True
break
if isbreak:
continue
#インデックスに検証を通過した要素を追加し再帰
q[index] = i
check8q(q)
#print 'cas', q
q[index] = -1
#追加できる要素なし
else:
#妥当な配置である
print q
if __name__ == '__main__':
#枝刈り
t1 = time.time()
check8q([-1] * 8)
t2 = time.time()
print t2 - t1,'sec'
実行速度は
総当り:80.379999876 sec
枝刈り:0.0940001010895 sec
80秒の処理が0.09秒に短縮です。
アルゴリズムの選定って重要ですね・・・