爲什麼這種啓發式可以接受？

對於井字我的講師已提出啓發的（這意味着它永遠不會高估的距離）爲井字如下下一步的行動（從Ø玩家的角度看）：爲什麼這種啓發式可以接受？

數O可能的行數 - 可能的行數爲X

我想知道的是爲什麼這種啓發式可以接受？

2013-01-07 IApp

好吧，至少，玩家X（贏）必須使X的可能行數> O的可能行數。否則遊戲不會以X勝利結束，對嗎？因此，它們所不同的行數是可以接受的，因爲至少必須爲X勝利彌補該距離 –

如果允許的函數在目標上應該爲'<= 0'，那絕對不是。很多材料似乎都說它應該是0. – Dukeling

@ Dukeling我不知道。這似乎不是一個真正的要求。此外，一致的啓發式是可接受的啓發式。一個CH永遠不會回溯它的估計值（達到目標的成本<=進入狀態S並從S估計）。對於這種情況，這似乎是相當真實的：你不能在TTT遊戲中打開新的途徑，對嗎？ –

不是。

O.. 
XOX 
OX.

然後到目標=（3-1）的距離=（由O爲贏）到目標，1 2

實際距離

2> 1，從而它高估。

或者我錯過了什麼？

2013-01-07 19:14:55 Dukeling

好吧，從O的角度來看，這塊板子是不可能的，對吧？ –

我不知道，你已經開始讓我懷疑自己，但我無法說服自己，這是不可接受的，因爲「下一步」 –

「 - 我想我錯過了那部分。 – Dukeling

啓發式功能據說是受理如果它從來沒有高估到達目標

什麼，基本意思的成本，就是當你有一個啓發式的，只有在保證目標的實際成本高於或等於估計成本的情況下，這纔是可接受的。一個很好的例子就是A *尋路算法的啓發式。對於該算法，通常使用一種啓發式方法來估計與目標的距離，就像有一條直接通向目標的道路。如果您使用高估距離的啓發式算法，它可能找不到最短的路徑。

2013-01-07 19:14:14 kokx

回答