algorithm - 解决8个难题的有效方法是什么？

Question

8拼图是一个9个位置的正方形板，由8个编号的瓷砖和一个缝隙填充。在任何时候，可以将与间隙相邻的图块移动到间隙中，以创建新的间隙位置。换句话说，可以与相邻的(水平和垂直)贴砖交换间隙。游戏的目标是从任意配置的图块开始，然后移动它们，以便获得编号的图块以升序排列，既可以绕着板的周边运行，也可以从左到右排列，左上角为1手的位置。

我想知道哪种方法可以有效解决这个问题？

Answer 1

我将尝试重写前面的答案，并详细说明为什么它是最佳选择。

直接从wikipedia获取的A *算法是

            function A*(start,goal)
                    closedset := the empty set                 // The set of nodes already evaluated.     
                    openset := set containing the initial node // The set of tentative nodes to be evaluated.
                    came_from := the empty map                 // The map of navigated nodes.
                    g_score[start] := 0                        // Distance from start along optimal path.
            h_score[start] := heuristic_estimate_of_distance(start, goal)
                    f_score[start] := h_score[start]           // Estimated total distance from start to goal through y.
                    while openset is not empty
                    x := the node in openset having the lowest f_score[] value
                    if x = goal
            return reconstruct_path(came_from, came_from[goal])
                    remove x from openset
                    add x to closedset
            foreach y in neighbor_nodes(x)
                    if y in closedset
                    continue
            tentative_g_score := g_score[x] + dist_between(x,y)

                    if y not in openset
                    add y to openset
                    tentative_is_better := true
                    elseif tentative_g_score < g_score[y]
                    tentative_is_better := true
                    else
                    tentative_is_better := false
                    if tentative_is_better = true
                    came_from[y] := x
                    g_score[y] := tentative_g_score
            h_score[y] := heuristic_estimate_of_distance(y, goal)
                    f_score[y] := g_score[y] + h_score[y]
                    return failure

            function reconstruct_path(came_from, current_node)
                    if came_from[current_node] is set
                    p = reconstruct_path(came_from, came_from[current_node])
            return (p + current_node)
                    else
                    return current_node

因此，让我在这里填写所有详细信息。
heuristic_estimate_of_distance是函数Σd(xi)，其中d(.)是每个正方形xi距其目标状态的曼哈顿距离。

所以设置

            1 2 3
            4 7 6
            8 5 

由于8.5(d，。)= 1时距离其目标位置1个位置，而d(7)= 2则其目标状态2远离状态位置2，则 heuristic_estimate_of_distance将为1 + 2 + 1 = 4。

A *搜索的节点集被定义为起始位置，后跟所有可能的合法位置。也就是说，起始位置 x如下:

            x =
            1 2 3
            4 7 6
            8 5 

然后函数 neighbor_nodes(x)会产生2种可能的合法 Action :

            1 2 3
            4 7 
            8 5 6

            or

            1 2 3
            4 7 6
            8   5

函数 dist_between(x,y)定义为从状态 x转换为 y发生的平方移动的数量。就您的算法而言，该值总是总是等于A *中的1。
closedset和 openset都特定于A *算法，可以使用标准数据结构(我相信优先级队列)来实现。 came_from是使用的数据结构
重构使用 reconstruct_path函数找到的解决方案，其详细信息可以在Wikipedia上找到。如果您不希望记住该解决方案，则无需实现此解决方案。

最后，我将讨论最优性问题。考虑一下A *维基百科文章的摘录:

“如果启发式函数h是可允许的，这意味着它永远不会高估达到目标的实际最小成本，那么如果我们不使用封闭集，则A *本身是可容许的(或最优的)。如果使用封闭集，则h还必须是单调的(或一致的)，以使A *最优，这意味着对于任何一对相邻节点x和y，其中d(x，y)表示它们之间边的长度，我们必须:
h(x)<= d(x，y)+ h(y)“

因此足以证明我们的启发式是可容许的并且是单调的。对于前者(可接纳性)，请注意，在任何配置下，我们的启发式(所有距离的总和)估计每个正方形都不受法律限制，并且可以自由移动到其目标位置，这显然是乐观的估计，因此我们的启发式是可以接受的(或者永远不要过高估计，因为达到目标位置将总是采取至少与启发式估计一样多的 Action 。)

用词表示的单调性要求是:
“任何节点的启发式成本(到目标状态的估计距离)必须小于或等于过渡到任何相邻节点的成本加上该节点的启发式成本。”

这主要是为了防止出现负循环的可能性，在这种情况下，过渡到不相关的节点可能比实际完成转换的成本要减少到目标节点的距离，这表明启发式方法较差。

要显示单调性，在我们的案例中非常简单。根据我们对d的定义，任何相邻节点x，y的d(x，y)= 1。因此我们需要证明

h(x)<= h(y)+ 1

相当于

h(x)-h(y)<= 1

相当于

Σd(xi)-Σd(yi)<= 1

相当于

Σd(xi)-d(yi)<= 1

通过对 neighbor_nodes(x)的定义，我们知道两个相邻节点x，y最多可以具有一个正方形的位置不同，这意味着我们将

d(xi)-d(yi)= 0

除了i的1个值可以说，不失一般性，i = k是正确的。此外，我们知道对于i = k，节点最多移动了一个位置，因此它到
目标状态必须比以前的状态最多多一个，因此:

Σd(xi)-d(yi)= d(xk)-d(yk)<= 1

表现出单调性。这显示了需要显示的内容，因此证明该算法将是最佳的(以大O表示或渐近式的方式。)

请注意，我已经在big-O表示法上显示了最优性，但是在调整启发式方法方面仍有很大的空间。您可以对其添加更多的扭曲，以便更精确地估计到目标状态的实际距离，但是您必须确保启发式算法总是被低估了，否则就会失去最优性!

稍后再编辑

稍后(很多)再读一遍，我意识到我编写它的方式有点混淆了该算法的最优性含义。

我试图在此处获得最优性有两种不同的含义:

1)该算法产生一个最优解，这是给定客观标准的最佳解决方案。

2)该算法使用相同的启发式算法扩展了所有可能算法中最少数量的状态节点。

理解为什么需要启发式的可取性和单调性才能获得1)的最简单方法是，将A *视为Dijkstra最短路径算法在图形上的应用，在该图形上，边的权重由到目前为止所经过的节点距离加上启发式给出距离。如果没有这两个属性，则图中的边将为负，从而可能出现负循环，并且Dijkstra的最短路径算法将不再返回正确的答案! (构造一个简单的例子来说服自己。)

2)实际上很难理解。为了充分理解其含义，该语句上有很多量词，例如在谈论其他算法时，有人将 similar算法称为A *，它扩展了节点并在没有先验信息的情况下进行搜索(启发式除外)。 )很明显，可以用其他方式构造一个平凡的反例，例如oracle或genie，它可以在每一步告诉您答案。为了深入理解此声明，我强烈建议阅读“历史记录”部分中有关 Wikipedia的最后一段，并仔细研究该句子中的所有引文和脚注。

我希望这可以消除潜在读者之间的任何困惑。