首页 文章

8难题：可解决性和最短的解决方案

提问于
浏览 次
7

我使用广度优先搜索构建了一个8拼图解算器 . 我现在想要修改代码以使用启发式 . 如果有人能回答以下两个问题，我将不胜感激：

Solvability

我们如何确定8拼图是否可以解决？ （给定起始状态和目标状态）这就是维基百科所说的：

不变量是所有16个方格的排列的奇偶校验加上从右下角开始的空方格的出租车距离（行数加上列数）的奇偶校验 .

不幸的是，我无法理解这意味着什么 . 理解起来有点复杂 . 有人可以用更简单的语言解释它吗？

Shortest Solution

给定启发式，是否可以保证使用A *算法提供最短的解决方案？更具体地说，打开列表中的第一个节点是否总是具有深度（或移动的数量如此之大），这是打开列表中存在的所有节点的深度的最小值？

启发式是否应满足上述陈述的某些条件？

编辑：可接受的启发式方法如何始终提供最佳解决方案？和 how do we test whether a heuristic is admissible?

我将使用列出的启发式here

Manhattan Distance 
Linear Conflict 
Pattern Database 
Misplaced Tiles
Nilsson's Sequence Score 
N-MaxSwap X-Y 
Tiles out of row and column

有关Eyal Schneider的说明：

enter image description here

enter image description here

enter image description here

java algorithm artificial-intelligence 8-puzzle

4 回答

  • 3

    我只会提到可解决性问题 . 需要一些排列的背景 .

    置换是有序集的重新排序 . 例如，2134是列表1234的重新排序，其中1和2交换位置 . 置换具有奇偶性;它指的是倒数的奇偶性 . 例如，在下面的排列中，您可以看到正好存在3个反转（23,24,34）：

    1234
1432

    这意味着置换具有奇数奇偶性 . 以下排列具有偶数奇偶校验（12,34）：

    1234
2143

    当然，身份置换（保持项目顺序）具有均衡性 .

    如果我们从第一行开始将它看作行的串联，那么15拼图（或8拼图）中的任何状态都可以被视为最终状态的排列 . 请注意，每个合法移动都会更改排列的奇偶性（因为我们交换了两个元素，并且涉及它们之间的项的反转数必须是偶数） . 因此，如果您知道空方必须经过偶数步骤才能达到其最终状态，那么排列也必须是偶数 . 否则，你将以最终状态的奇数排列结束，这必然与它不同 . 与空方块的奇数步数相同 .

    根据您提供的维基百科链接，上述标准对于给定的谜题是可解的是足够的和必要的 .

    回复于
  • 6

    A algorithm* 是 guaranteed 找到（一个如果有多个相等的短的）最短的解决方案，如果你的启发式 always underestimates 实际成本（在你的情况下，所需的实际数量移动到解决方案） .

    但在飞行中我无法为您的问题提出一个好的启发式方法 . 这需要一些思考才能找到这样的启发式方法 .

    使用A *的真正艺术是找到一种始终低估实际成本的启发式算法，但尽可能少地加速搜索 .

    这种启发式的第一个想法：

    • 在我的脑海中突然出现了一个非常有效但是有效的启发式算法，就是空旷地到达最终目的地的距离 .

    • 每个字段与其最终目的地的平均距离之和除以可在一次移动中改变位置的最大字段数 . （我认为这是一个很好的启发式）

    回复于
  • 0

    我将尝试回答与“最短解决方案”部分相关的问题 . 如果启发式是可接受的（即，永远不会过高估计到最近目标的路径成本），则保证A *树搜索算法是最优的（即，如果存在，则找到最短路径） . 形式上，如果对于每个节点n，0 <= h（n）<= h *（n），则启发式h是可接受的，其中h *（n）是从n到达最近目标的确切成本 .

    但是，A *树搜索最终可能会进行指数级重复的工作 . 我们需要一种方法来关闭扩展节点，以便它们不会再次展开，从而产生图搜索算法 . 只有当使用的启发式是一致的时，A *图搜索才是最佳的，即，它逐渐估计路径成本，因此沿路径的启发式值永远不会减少 . 形式上，如果对于每个节点，启发式h是一致的n和n的每个后继者，h（n）<= h（p）成本（n，p） .

    曼哈顿距离是8-puzzle问题的一致启发式算法，A *图搜索，如果存在曼哈顿距离作为启发式，则确实会找到最短的解决方案 .

    我已经写了A *搜索的详细解释，并在这里使用A *提供了N-puzzle问题的python实现：A* search explanation and N-puzzle python implementation

    回复于
  • 0

    对于任何一个人来说，我将尝试解释OP如何得到 Value 对以及他如何确定突出的那些，即反转，因为我花了几个小时来弄明白 . 首先是对 . 首先采取目标状态并将其想象为一维数组（例如A）[1,2,3,8,0,4,7,5] . 该数组中的每个值在表中都有自己的列（一直向下，这是该对的第一个值 . ）然后在数组中向右移动1个值（i 1）并一直向下移动再次，第二对 Value . 例如（状态A）：第一列，第二个值将开始[2,3,8,0,4,7,5]下降 . 第二栏，将开始[3,8,0,4,7,5]等 .

    好的，现在反转 . 对于2对值中的每一个，在起始状态中找到它们的 INDEX 位置 . 如果左 INDEX >右 INDEX 那么它是一个反转（突出显示） . 前四对状态A是：（1,2），（1,3），（1,8），（1,0）
    1是在索引3
    2是指数0
    3> 0如此倒置 .

    1是3
    3是2
    3> 2如此倒置

    1是3
    8是1
    3> 2如此倒置

    1是3
    0是7
    3 <7所以 No inversion

    对每对进行此操作并计算总反转量 . 如果偶数或两者都是奇数（曼哈顿距离的空白点和总反转）那么它是可以解决的 . 希望这可以帮助！

    回复于

相关问题