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

Question

我正在进行 8 个谜题的挑战，我必须以最短的路径成本以正确的顺序排列图 block 。 对于我的启发式，我将错误放置的图 block 数量+ n 个图 block 到其目标位置的距离组合起来。

目标是

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 上算法的伪代码，您会注意到他们命名为 closeSet 的东西。这是一个集合，您可以在其中存储已扩展的状态(已为其生成后继状态)。然后，遍历所有后继者(或伪代码中的邻居)的循环以此开始:

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

该段代码的目的是为了防止您的问题发生。

请注意，您为 closeSet 选择的数据结构将显着影响算法的运行时间。它不应该像列表一样，检查对象是否已在其中需要循环遍历整个列表。相反，您会想要查看诸如 HashMap /集合之类的内容(确切的术语取决于您选择的编程语言)。