11
A
回答
0
編輯：這個答案混淆了可接受性和一致性。我已經糾正它是指可接受性，但最初的問題是關於一致性，而這個答案沒有完全回答這個問題。
你可以通過區分所有不同的情況來分析，因此證明你的啓發式確實是可以接受的。
知情搜索，啓發式是受理與搜索問題（比如，尋求在遊戲中最好的移動）當且僅當低估的「距離」，以一個合適的狀態吧。
示例：通過城市之間的高速公路網絡搜索到目標城市的最短路線。在這裏，可以使用Eucidean距離作爲啓發式：到目標的直線的長度總是比最佳可能的方式更短或者更長。
像A*這樣的算法需要可接受性，然後這些算法會使您處於最佳狀態（即如果存在目標狀態，它們將找到最佳'路線'）。
我會建議您在AI textbook中查看主題。
+8
儘管所有一致的啓發式規則都是可以接受的，但在可接受和一致的啓發式方法之間也有區別。可允許意味着啓發式會低估總路徑成本，並且如果在遍歷一個步驟後啓發式降低不超過步驟成本，則它是一致的。 – 2010-04-18 09:38:14
1
啓發式爲給定狀態產生某種成本值。在這種情況下的一致性意味着一個國家的估計加上轉移到下一個國家的成本小於或等於該新國家的估計。如果這不是真的，那麼它意味着 - 如果啓發法是準確的 - 從一個狀態轉換到下一個狀態可能產生負面成本，這通常是不可能的或不正確的。
這是直觀的證明，當涉及到尋路，因爲你期望沿着路徑的每一步需要一些時間，因此步驟1的估計必須低於任何步驟2的估計。它可能多一點因爲你可能不得不隨意決定什麼構成你的系統中的「成本」。如果您的啓發式遊戲可以通過玩家移動而上下移動 - 例如。因爲你用正數編碼好動作，用負數編碼動作不好 - 那麼你的啓發式就不能保持一致。
然而，缺少一致的啓發式並不總是一個問題。你可能無法保證沒有一個最佳的解決方案，但它可能會加快搜索速度，而不是蠻力狀態搜索。
這是一個真正的問題。 – 2009-10-08 19:48:03
兩人已將此標記爲「不是真正的問題」。我也不同意他們。 – Kylotan 2009-10-09 09:22:15