什么是有效的方法来解决8数码问题？ [英] What can be the efficient approach to solve the 8 puzzle problem?

问题描述

8，让人不解的是方形板9的位置，填补了8号的瓷砖，一个缺口。在任何时候，相邻的间隙的瓦片可以移动到间隙，创建一个新的间隙的位置。换句话说，间隙可以交换与相邻（水平和垂直）的瓷砖。在本场比赛的目标是开始与瓷砖的任意配置，并将其移动，从而获得升序排列或者围绕板的周边运行，或下令编号的瓷砖，从左至右，用1左上方 - 手的位置。

The 8-puzzle is a square board with 9 positions, filled by 8 numbered tiles and one gap. At any point, a tile adjacent to the gap can be moved into the gap, creating a new gap position. In other words the gap can be swapped with an adjacent (horizontally and vertically) tile. The objective in the game is to begin with an arbitrary configuration of tiles, and move them so as to get the numbered tiles arranged in ascending order either running around the perimeter of the board or ordered from left to right, with 1 in the top left-hand position.

我不知道用什么办法将有效地解决这个问题？

I was wondering what approach will be efficient to solve this problem?

推荐答案

我只是尝试重写previous答案与为什么它是最佳的更多的细节。

I will just attempt to rewrite the previous answer with more details on why it is optimal.

A *算法直接从维基百科采取的是

The A* algorithm taken directly from wikipedia is

            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

所以，让我在所有的细节在这里填写。

So let me fill in all the details here.

heuristic_estimate_of_distance 是函数与西格玛; ð（X <子>我）其中d（。）是每平方米x <子>我从目标状态。

heuristic_estimate_of_distance is the function Σ d(x_i) where d(.) is the Manhattan distance of each square x_i from its goal state.

所以设置

            1 2 3
            4 7 6
            8 5 

将有一个的 heuristic_estimate_of_distance 1 + 2 + 1 = 4，因为每8,5是一体的距离为d（）= 1和7的目标位2是远离其与D目标状态（7）= 2。

would have a heuristic_estimate_of_distance of 1+2+1=4 since each of 8,5 are one away from their goal position with d(.)=1 and 7 is 2 away from its goal state with d(7)=2.

节点集的A *搜索过被定义为起始位置，接着用一切可能的法律立场。这是可以说的起始位置 X 如上：

The set of nodes that the A* searches over is defined to be the starting position followed by all possible legal positions. That is lets say the starting position x is as above:

            x =
            1 2 3
            4 7 6
            8 5 

那么函数 neighbor_nodes（X）生成2个可能的法律行动：

then the function neighbor_nodes(x) produces the 2 possible legal moves:

            1 2 3
            4 7 
            8 5 6

            or

            1 2 3
            4 7 6
            8   5

功能 dist_between（X，Y）定义为方举动，发生从状态 X 到是。这主要将是等于1中的A *总是为你的算法的目的

The function dist_between(x,y) is defined as the number of square moves that took place to transition from state x to y. This is mostly going to be equal to 1 in A* always for the purposes of your algorithm.

closedset 和 openset 都具体到A *算法，并可以使用标准的数据结构来实现的（优先级队列相信。） came_from 是使用的数据结构 重建使用功能 reconstruct_path 谁的细节可以在维基百科中找到找到了解决办法。如果你不想记住的解决方案，你并不需要实现这一点。

closedset and openset are both specific to the A* algorithm and can be implemented using standard data structures (priority queues I believe.) came_from is a data structure used to reconstruct the solution found using the function reconstruct_path who's details can be found on wikipedia. If you do not wish to remember the solution you do not need to implement this.

最后，我将讨论最优的问题。可考虑从A *维基百科文章的节选：

Last, I will address the issue of optimality. Consider the excerpt from the A* wikipedia article:

如果启发式函数h是可接受的，这意味着它永远不会高估到达目标的实际最低的成本，那么A *本身是可以受理（或最佳），如果我们不使用密闭集。如果一个封闭的集用过的，则h也必须是单调的（或一致）为A *是最佳的，这意味着，对于任一对相邻节点x和y中，其中，d（X，Y）表示它们之间的边缘的长度，就必须有： H（X）＆其中; = D（X，Y）+ H（y）的

"If the heuristic function h is admissible, meaning that it never overestimates the actual minimal cost of reaching the goal, then A* is itself admissible (or optimal) if we do not use a closed set. If a closed set is used, then h must also be monotonic (or consistent) for A* to be optimal. This means that for any pair of adjacent nodes x and y, where d(x,y) denotes the length of the edge between them, we must have: h(x) <= d(x,y) +h(y)"

因此​​，它足以说明，我们的启发是允许的，单调的。对于前者（受理），请注意，鉴于任何配置我们的启发式（所有距离的总和）估计，每平方米不被唯一合法的移动约束，并且可以实现其目标的位置，这显然是一个乐观的估计，因此，我们的启发式自由移动是受理（或它永远不会过高估计，因为到达目标位将始终的至少的许多举措为启发式的估计。）

So it suffices to show that our heuristic is admissible and monotonic. For the former (admissibility), note that given any configuration our heuristic (sum of all distances) estimates that each square is not constrained by only legal moves and can move freely towards its goal position, which is clearly an optimistic estimate, hence our heuristic is admissible (or it never over-estimates since reaching a goal position will always take at least as many moves as the heuristic estimates.)

在口头上说的单调性的要求是： 任何节点的启发式成本（到目标状态估计的距离）必须小于或等于转换到任何相邻节点加上该节点的启发式成本的成本。

The monotonicity requirement stated in words is: "The heuristic cost (estimated distance to goal state) of any node must be less than or equal to the cost of transitioning to any adjacent node plus the heuristic cost of that node."

有主要以prevent负周期，其中转变到一个不相关的节点可能会降低到目标节点的距离超过实际进行的过渡，这表明一个差启发式的成本的可能性。

It is mainly to prevent the possibility of negative cycles, where transitioning to an unrelated node may decrease the distance to the goal node more than the cost of actually making the transition, suggesting a poor heuristic.

要显示其单调pretty的在我们的例子简单。任何相邻节点的x，y由我们的D定义有D（X，Y）= 1。因此，我们需要表现出

To show monotonicity its pretty simple in our case. Any adjacent nodes x,y have d(x,y)=1 by our definition of d. Thus we need to show

H（X）＆其中; = H（Y）+1

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

这相当于

H（X） - H（Y）＆LT; = 1

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

这相当于

＆Sigma公司; ð（X <子>我） - 西格玛;坐标（Y <子>我）＆LT; = 1

Σ d(x_i) - Σ d(y_i) <= 1

这相当于

＆Sigma公司; ð（X <子>我） - D（是<子>我）＆LT; = 1

Σ d(x_i) - d(y_i) <= 1

我们知道，我们的 neighbor_nodes定义（X）两个相邻节点的x，y最多只能有一平方的位置不同，这意味着我们的款项中长期

We know by our definition of neighbor_nodes(x) that two neighbour nodes x,y can have at most the position of one square differing, meaning that in our sums the term

ð（X <子>我） - D（是<子>我）= 0

d(x_i) - d(y_i) = 0

为所有，但我值为1。比方说不失一般性此为i = k的真实。此外，我们知道，对于i = K，节点移到最多一个地方，所以它的距离 一个目标状态必须是最多一个多在previous状态是这样的：

for all but 1 value of i. Lets say without loss of generality this is true of i=k. Furthermore, we know that for i=k, the node has moved at most one place, so its distance to a goal state must be at most one more than in the previous state thus:

＆Sigma公司; ð（X <子>我） - D（是<子>我）= D（X <子> K ） - D（是<子> K ）＆LT; = 1

Σ d(x_i) - d(y_i) = d(x_k) - d(y_k) <= 1

显示单调性。这说明什么需要加以表现，从而证明该算法将是最佳的（在一个大O符号或渐进的一种方式。）

showing monotonicity. This shows what needed to be showed, thus proving this algorithm will be optimal (in a big-O notation or asymptotic kind of way.)

请注意，我已经表明最优的大O记法的条件，但仍有大量的空间在调整启发式方面的发挥。您可以添加额外的曲折，以便它是目标状态的实际距离的接近估计，然而的你必须做出的确定的是启发式始终是一个低估的，否则你失去最优！

Note, that I have shown optimality in terms of big-O notation but there is still lots of room to play in terms of tweaking the heuristic. You can add additional twists to it so that it is a closer estimate of the actual distance to the goal state, however you have to make sure that the heuristic is always an underestimate otherwise you loose optimality!

这篇关于什么是有效的方法来解决8数码问题？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！