我已经成功地在 NxM 上的网格上实现了 A* 路径查找。
我知道 A* 的所有基础知识，我想知道如何为上述问题实现相同的算法。
有人可以指导我了解启发式函数 h 和 G 分数在这些问题中与什么相关以及如何进行。
-- 例如在网格搜索中，我们将邻居添加到打开列表中，然后搜索最低 F 分数，并将其添加到关闭列表中。
遵循相同的算法来解决 NQueens 和 Sliding 谜题会做些什么？
谢谢 ：）
问问题
4960 次
2 回答
3
您需要正确定义转换函数、成本函数和启发式函数。如果您了解 A* 的基础知识，而不是向您解释每个示例，您可能会发现看一下Hipster 库的N-Queens 问题和N-Puzzle 问题的实现很有用。如果您没有在 Java 中实现代码，请不要担心，代码足够清晰，可以让您知道如何去做。
我希望我的回答有帮助。
阿德里安
于 2014-09-29T08:34:43.057 回答
3
A* 是一种适用于图的算法，因此当您使用 A* 解决问题时，该问题必须看起来像一个图。当然，您通常不会实际构建图，它通常是隐式的，但它仍然是一个图（它有节点并且节点与邻居有边）。
所以你必须决定该图中的节点是什么。对于网格上的寻路，节点对应于网格中的位置。
然后定义一种（或几种）从节点生成邻居的方法。考虑图，这是一个从节点到一组出边的函数。对于网格中的寻路，这就是您生成可能 4 个相邻位置（或 8 个或其他位置）的地方。基本上，您定义了可以采取的“步骤”。
这些步骤是有代价的。那不是 G，它只是你增加 G 的值。通常它只是 1。再次以网格中的寻路为例，有时它被定义为 10 代表北/东/南/西一步，12 代表对角线步长（使用易于使用的小整数近似欧几里得距离） .
然后你会发现可接受的启发式方法（不会高估实际成本的方法），这在某种程度上就是 A* 的全部意义所在。没有它，这将是一个愚蠢的搜索，启发式使它有信息，并且它必须是可接受的以确保最优性。找到同样好的（即相当高的）可接受的启发式方法可能很棘手。如果您找到其中的几个，说出函数h0和h1，那么您可以采用max(h0, h1)，但当然，这只有在它们都不是明显的“赢家”的情况下才有帮助，因为它总是至少与另一个一样高（并且仍然可以接受） ， 明显地）。如果有一个明显的赢家，你显然可以只使用那个而忘记另一个。
基本上，这一切都是在 A* 算法中“填补空白”的一种方式，它本身不会根据你用它解决的问题而改变.. 除了一个细节：封闭列表只能在以下情况下使用启发式是一致的。所以你仍然做熟悉的事情，从打开列表中取出 F 分数最低的节点，把它放在最近的列表中，查看它的邻居并将它们放在打开列表中，我在这里跳过了很多，但是你知道演习。
于 2014-09-27T16:28:27.980 回答