artificial-intelligence - 如何防止 A* 搜索重复路径

Question

我正在做 8 拼图挑战，我必须以最短的路径成本以正确的顺序排列图块。对于我的启发式方法，我将错位瓷砖的数量+ n 瓷砖的距离与其目标位置相结合。

目标是

1 2 3
8 0 4
7 6 5

对于这样的谜题

1 2 3 
7 8 4
6 0 5

它工作得很好

但是有了这个配置

1 3 4
8 0 2
7 6 5

它无限地选择这个组合作为最短的

1)

1 0 4
8 3 2
7 6 5

2)

1 3 4
8 0 2
7 6 5

然后 1) 然后 2)

Answer 1

如果您查看wikipedia上的算法伪代码，您会注意到他们命名的东西closedSet。这是一个集合，您可以在其中存储已扩展的状态（已为其生成后继的状态）。然后，通过所有后继者（或伪代码中的邻居）的循环从以下开始：

if neighbor in closedSet
    continue        // Ignore the neighbor which is already evaluated.

那段代码的目的是防止您的问题发生。

请注意，您选择的数据结构closedSet将显着影响算法的运行时间。它不应该像一个列表，检查一个对象是否已经在其中需要遍历整个列表。相反，您将希望查看诸如哈希映射/集合之类的东西（确切的术语取决于您选择的编程语言）。