A* 启发式实现
A* Heuristic implementation
我正在创建一个程序来以最低的成本解决这个难题
sliding-title 拼图由三个黑色标题、三个白色标题和一个空 space 组成，如图所示。
WWW_BBB
The goal of the puzzle is to get all white tiles to the right of the
black tiles while the location of the space does not matter
The puzzle has two legal moves(i.e. actions) with associated costs:
• A title may move into an adjacent empty location. – This has a step cost of
• A title can hop over one or two other tiles into the empty position.
– This has a step cost equal to the number of tiles jumped over.
我无法理解如何创建要在算法中实现的启发式算法。
我了解 Dijkstra 算法在这个问题中的实现，但无法弄清楚如何将其变成 A* 算法。
假设您想在拼图状态图上使用 A*，其边缘可通过两个规则之一到达状态，那么一个很好的启发式方法是使用反转数：https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)
这是乱序的 W,B 对的数量（假设同色方块的相对顺序不变）。当版本数为 0 时，W 和 B 是有序的，并且每种移动类型固定的反转次数小于或等于其成本。因此，作为启发式的反转次数永远不会高估最佳序列的成本。
我正在创建一个程序来以最低的成本解决这个难题
sliding-title 拼图由三个黑色标题、三个白色标题和一个空 space 组成，如图所示。
WWW_BBB
The goal of the puzzle is to get all white tiles to the right of the black tiles while the location of the space does not matter
The puzzle has two legal moves(i.e. actions) with associated costs:
• A title may move into an adjacent empty location. – This has a step cost of
• A title can hop over one or two other tiles into the empty position.
– This has a step cost equal to the number of tiles jumped over.
我无法理解如何创建要在算法中实现的启发式算法。
我了解 Dijkstra 算法在这个问题中的实现，但无法弄清楚如何将其变成 A* 算法。
假设您想在拼图状态图上使用 A*，其边缘可通过两个规则之一到达状态，那么一个很好的启发式方法是使用反转数：https://en.wikipedia.org/wiki/Inversion_(discrete_mathematics)
这是乱序的 W,B 对的数量（假设同色方块的相对顺序不变）。当版本数为 0 时，W 和 B 是有序的，并且每种移动类型固定的反转次数小于或等于其成本。因此，作为启发式的反转次数永远不会高估最佳序列的成本。