language-agnostic - Peg Solitaire / Senku 解算法

Question

我需要为Peg solitaire / Senku 游戏编写求解器这里
已经有一个问题，但建议的答案是带有回溯的蛮力算法，这不是我正在寻找的解决方案。 我需要找到一些启发式方法来应用 A* 算法。剩余的钉子不是一个好的启发式，因为每一步都会丢弃一个钉子，因此成本始终是统一的。 有任何想法吗？

Answer 1

我正在阅读一篇关于此问题链接的论文，他们提出了 3 个启发式方法：

1 - 下一步可用的节点数，考虑哪些可用的下一步越多，节点越好。

2 - 孤立钉的数量 - 孤立钉越少，节点越好。

3 - 板上钉子越少，节点越好。

对于这个问题，这可能不是更好的启发式方法，但似乎是一种简单的方法。

Answer 2

您可以按照 rossum 的建议进行操作。另一种选择是使用距中心的距离总和（或距离的其他函数）。或者你可以将两者结合起来。