为什么这个启发式算法是可行的？

Question

对于井字游戏，我的讲师提出了一种可接受的启发式（意味着它从未高估距离），用于下一步井字游戏中O玩家的移动，如下所示：

O的可能线数 - X的可能线数

我想知道为什么这个启发式是可接受的？

- IApp

---

好的，至少，玩家X（要获胜）必须使X的可能线路数大于O的可能线路数。否则，游戏就不会以X的胜利结束，对吗？因此，它们之间差异的行数是可以接受的，因为至少必须弥补这个距离才能取得X的胜利。 - im so confused

肯定不是在目标处允许的函数应该是 <= 0。很多资料似乎都说它应该等于0。 - Bernhard Barker

@Dukeling 我不知道。那似乎不是一个真正的要求。此外，一致的启发式是可接受的。CH从不回溯其估计值（到达目标的成本<=到达状态S和从S的估计值）。对于这种情况似乎非常正确：在Tic Tac Toe游戏中，你不能打开新的道路，对吧？ - im so confused

你可以将它改为 if (at goal) 0 else {what you wrote}，以使 =0 的情况成立。但我们所说的目标是什么？是让 O 赢？还是让 X 赢？或者两者都可以？请看下面我的回答，了解为什么这可能不可行。 - Bernhard Barker

Answer 1

这不是。

O..
XOX
OX.

那么到目标的距离为(3-1)=2

实际到目标的距离为1(赢得了'O')

2 > 1，因此它高估了。

或者我错过了什么？

- Bernhard Barker

---

这块板子从 O 的角度来看是不可能的，对吧？ - im so confused

我不知道，你已经让我开始怀疑自己了，但我无法说服自己仅凭这里的内容就是不可接受的。 - im so confused

下一步操作 - 我想我错过了那部分。 - Bernhard Barker

编辑为 O 执棋的局面。 - Bernhard Barker

那我就有点被难住了。你能看出我的一致启发式注释中的缺陷在哪里吗？因为 CH => AH，而对我来说（根据 CH 的定义），这似乎非常单调... - im so confused

@AK4749，你似乎没有考虑到O的胜利，而行数并不是获胜的衡量标准，只是一种不错的策略（比如一个玩家沿着边跑，他会赢但永远不会有最多的线）。 - Bernhard Barker

Answer 2

来自维基百科：

如果启发式函数从不高估到达目标的成本，则称其为可接受的

这基本上意味着当您使用启发式函数时，仅当实际到达目标的成本保证高于或等于估计成本时，该启发式函数才是可接受的。一个很好的例子是A*路径查找算法的启发式函数。对于该算法，通常使用估计直接连接到目标的距离的启发式。如果您使用高估距离的启发式，则可能无法找到最短可能的路径。

- kokx