6
我已經在Python中實現了一個Rush Hour（拼圖板遊戲）版本，作爲一些AI算法的演示。這個遊戲並不重要，因爲AI相對獨立於它的細節：我試圖在Python中實現一個迭代加深深度優先搜索的版本，如下所示（請注意，該代碼幾乎直接從Russell和Norvig的AI文本複製而來，第三版，對於那些瞭解它的人）：迭代深度優化的優化誤差搜索算法
def depth_limited_search(game, limit):
node = GameNode(game)
frontier = []
#frontier = Queue.Queue()
frontier.append(node)
#frontier.put(node)
frontier_hash_set = set()
frontier_hash_set.add(str(node.state))
explored = set()
cutoff = False
while True:
if len(frontier) == 0:
#if frontier.empty():
break
node = frontier.pop()
#node = frontier.get()
frontier_hash_set.remove(str(node.state))
explored.add(str(node.state))
if node.cost > limit:
cutoff = True
else:
for action in node.state.get_actions():
child = node.result(action)
if str(child.state) not in frontier_hash_set and str(child.state) not in explored:
if child.goal_test():
show_solution(child)
return child.cost
frontier.append(child)
#frontier.put(child)
frontier_hash_set.add(str(child.state))
if cutoff:
return 'Cutoff'
else:
return None
def iterative_deepening_search(game):
depth = 0
while True:
result = depth_limited_search(game, depth)
if result != 'Cutoff':
return result
depth += 1
實施的搜索算法確實會在合理的時間內返回一個答案。問題是答案是非最優的。我選擇的測試板在8次移動中有最佳答案，但是此算法使用10次移動返回一個。如果我用註釋行替換上面註釋過的行的行，有效地將迭代加深的深度優先搜索轉變爲迭代加深的廣度優先搜索，算法會返回最佳答案！
我一直在盯着這個很長一段時間，現在試圖弄清楚遍歷順序中的一個簡單的變化可能會導致非最優化，我無法弄清楚。任何幫助指出我的愚蠢的錯誤將不勝感激
我會看看費用的計算，不包括在這裏，因爲這段代碼看起來一眼就能看出來，畢竟你得到的結果是錯誤的成本值。 – 2011-02-15 08:27:30
啊，對不起，我應該更加明確。節點的「成本」只是達到它的動作數量;由node.result（action）生成的孩子的成本等於node.cost + 1。此外，show_solution（）打印出爲達到目標節點而採取的一系列動作，所以看起來似乎不太可能，因爲我可以只需計算步驟。 – Sean 2011-02-15 08:56:10
爲什麼這麼多轉換爲str？ – 2011-02-15 11:31:28