解决 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?
推荐答案
我将尝试重写之前的答案，详细说明为什么它是最佳的.
I will just attempt to rewrite the previous answer with more details on why it is optimal.
直接取自 wikipedia 的 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 是函数 Σd(xi) 其中 d(.) 是每个正方形 xi 与其目标状态的曼哈顿距离.
heuristic_estimate_of_distance is the function Σ d(xi) where d(.) is the Manhattan distance of each square xi 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 离目标位置 2d(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 转换到 y 所发生的方格移动次数.出于算法的目的，这在 A* 中通常等于 1.
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.)
用words表述的单调性要求是:任何节点的启发式成本(到目标状态的估计距离)必须小于或等于转换到任何相邻节点的成本加上该节点的启发式成本."
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."
主要是为了防止出现负循环的可能性，在这种情况下，转换到一个不相关的节点可能会减少到目标节点的距离，而不是实际进行转换的成本，这表明启发式方法很差.
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.
在我们的例子中，显示单调性非常简单.根据我们对 d 的定义，任何相邻节点 x,y 都具有 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) <= 1
h(x) - h(y) <= 1
相当于
Σd(xi) - Σd(yi) <= 1
Σ d(xi) - Σ d(yi) <= 1
相当于
Σd(xi) - d(yi) <= 1
Σ d(xi) - d(yi) <= 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
d(xi) - d(yi) = 0
d(xi) - d(yi) = 0
对于除 i 的 1 个值之外的所有值.让我们在不失一般性的情况下说 i=k 是正确的.此外，我们知道对于 i=k，节点最多移动了一个位置，所以它到目标状态最多只能比前一个状态多一个，因此:
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:
Σd(xi) - d(yi) = d(xk) - d(yk) <= 1
Σ d(xi) - d(yi) = d(xk) - d(yk) <= 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!
(很久之后)再读一遍，我意识到我写它的方式有点混淆了这个算法的最优性的含义.
Reading this over again (much) later, I realized the way I wrote it sort of confounds the meaning of optimality of this algorithm.
我试图在这里得到两种不同的优化含义:
There are two distinct meanings of optimality I was trying to get at here:
1) 该算法产生一个最优解，即给定客观标准的最佳可能解.
1) The algorithm produces an optimal solution, that is the best possible solution given the objective criteria.
2) 该算法使用相同的启发式扩展所有可能算法中最少数量的状态节点.
2) The algorithm expands the least number of state nodes of all possible algorithms using the same heuristic.
理解为什么需要启发式的可采性和单调性来获得 1) 的最简单方法是将 A* 视为 Dijkstra 最短路径算法在图上的应用，其中边权重由到目前为止所行进的节点距离给出加上启发式距离.如果没有这两个属性，图中就会有负边，因此可能出现负循环，Dijkstra 的最短路径算法将不再返回正确答案！(构建一个简单的例子来说服自己.)
The simplest way to understand why you need admissibility and monotonicity of the heuristic to obtain 1) is to view A* as an application of Dijkstra's shortest path algorithm on a graph where the edge weights are given by the node distance traveled thus far plus the heuristic distance. Without these two properties, we would have negative edges in the graph, thereby negative cycles would be possible and Dijkstra's shortest path algorithm would no longer return the correct answer! (Construct a simple example of this to convince yourself.)
2) 实际上很容易理解.为了完全理解这句话的意思，这个语句有很多量词，比如在谈到其他算法时，将similar算法称为A*，扩展节点和搜索没有先验信息(启发式除外).显然，人们可以通过其他方式构建一个微不足道的反例，例如预言机或精灵，它会在每一步告诉您答案.要深入理解此声明，我强烈建议您阅读 维基百科历史部分的最后一段 以及查看那个仔细陈述的句子中的所有引文和脚注.
2) is actually quite confusing to understand. To fully understand the meaning of this, there are a lot of quantifiers on this statement, such as when talking about other algorithms, one refers to similar algorithms as A* that expand nodes and search without a-priori information (other than the heuristic.) Obviously, one can construct a trivial counter-example otherwise, such as an oracle or genie that tells you the answer at every step of the way. To understand this statement in depth I highly suggest reading the last paragraph in the History section on Wikipedia as well as looking into all the citations and footnotes in that carefully stated sentence.
我希望这能消除潜在读者之间的任何困惑.
I hope this clears up any remaining confusion among would-be readers.
这篇关于解决 8 个难题的有效方法是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
