迭代加深爲什麼星星不需要測試重複狀態？

迭代加深星號（ID A *）是一個記憶有界搜索。我的問題是，當我們從ID A *中的開放狀態s到達新狀態s'時，爲什麼我們不測試s'是否已處於「打開狀態」或「關閉狀態」？迭代加深爲什麼星星不需要測試重複狀態？

對於一些問題，例如：數獨，因爲狀態永遠不會達到兩次，因爲「問題狀態圖」是一棵樹。但是，對於其他問題，例如：8個難題，它可能會一次又一次地達到一個狀態。因此，它應該被測試一個國家是否已經「訪問」（無論是在開放或封閉的狀態）或不。

如果這樣的測試必須完成，那麼ID A *不再是存儲器限制，因爲必須存儲所有可能狀態的大型哈希表。

2013-10-06 Peng Zhang

這個問題似乎是題外話題，因爲它涉及的算法不是特定於編程。 –

等一下。離題話題是什麼意思？有「算法」和「搜索」標籤。你怎麼能說算法不是編程的一部分？ –

個人而言，我認爲這是主題討論（儘管可能更適合http://cstheory.stackexchange.com。）閱讀幫助主題[我可以在這裏詢問什麼主題？]（http://stackoverflow.com/help/on-topic） –

爲了保持內存配置文件的小，我們不測試s'是否重複。實際上，IDA ^*實際上將多次擴展相同的狀態。

來源

2013-10-06 20:48:37

那麼，你的意思是說，即使是在一次特定的f-限制（評估函數的限制）搜索中，一個狀態將被多次訪問？我知道一個國家將在很多回閤中被訪問。但直觀地說，它不應該在單次搜索中多次訪問。 –

@ user2697964 - IDA *只記住當前路徑上的節點。它不會擴大自己的祖先狀態。但是，如果一個狀態可以從多個路徑到達，它可能會多次擴展該狀態，即使在單個f限制內也是如此。 –

@ user2697964爲了防止重新搜索節點，可以將IDA *與轉置表配對，轉置表使用主存儲器來緩存先前搜索到的節點。如果之前遇到過一個節點並且搜索到的深度大於或等於當前搜索深度，則可以使用其緩存的值代替。請參閱：http://en.wikipedia.org/wiki/Transposition_table –

人工智能編程往往是關於嘗試許多不同的算法調整，以找到最適合您的需求。如果已經訪問過一個新狀態的可能性很大，那麼增加確定一個狀態是否已經訪問過的額外開銷可能會提高性能。但是可能有許多其他變量需要考慮，例如算法如何適合問題，可用內存，處理能力，可擴展性。我認爲成爲一名優秀的AI程序員意味着你知道不同算法的優缺點，並且看到了有多少不同的問題會影響每種算法的性能。我認爲你不應該認爲像ID A *這樣的算法限於不考慮是否已經達到狀態。如果您認爲考慮重新進入的國家會更好地執行，請嘗試一下，看看是否改進了您的解決方案。

來源

2013-10-06 20:58:33

迭代加深爲什麼星星不需要測試重複狀態？

回答

相關問題