8 拼图是一个有 9 个位置的方板，由 8 个编号的瓷砖和一个间隙填充。在任何时候，与间隙相邻的瓷砖都可以移动到间隙中，从而创建新的间隙位置。换句话说，间隙可以与相邻（水平和垂直）的瓷砖交换。游戏的目标是从任意配置的图块开始，然后移动它们以使编号的图块按升序排列，或者围绕棋盘周边排列，或者从左到右排列，左上角为 1 -手的位置。
我想知道什么方法可以有效地解决这个问题？
问问题
33626 次
6 回答
15
我将尝试重写之前的答案，并详细说明为什么它是最佳的。
直接取自维基百科的 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(x i )，其中 d(.) 是每个正方形 x i与其目标状态的曼哈顿距离。
所以设置
1 2 3
4 7 6
8 5
将具有heuristic_estimate_of_distance1+2+1=4 的 a，因为 8,5 中的每一个都与 d(.)=1 时的目标位置相差 1，而 d(7)=2 时 7 与目标状态的距离为 2。
A* 搜索的节点集定义为起始位置，后跟所有可能的合法位置。也就是说，起始位置x如上：
x =
1 2 3
4 7 6
8 5
然后该函数neighbor_nodes(x)产生 2 个可能的合法移动：
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)"
所以只要证明我们的启发式是可接受的和单调的就足够了。对于前者（可接受性），请注意，给定任何配置，我们的启发式（所有距离的总和）估计每个方格不受合法移动的限制，并且可以自由移动到其目标位置，这显然是一个乐观的估计，因此我们的启发式是可以接受的（或者它永远不会高估，因为达到目标位置总是需要至少与启发式估计一样多的动作。）
用文字表述的单调性要求是：“任何节点的启发式成本（到目标状态的估计距离）必须小于或等于过渡到任何相邻节点的成本加上该节点的启发式成本。”
这主要是为了防止出现负循环的可能性，在这种情况下，转换到不相关的节点可能会减少到目标节点的距离，而不是实际进行转换的成本，这表明启发式方法很差。
在我们的例子中，要显示单调性非常简单。根据我们对 d 的定义，任何相邻节点 x,y 都具有 d(x,y)=1。因此我们需要展示
h(x) <= h(y) + 1
这相当于
h(x) - h(y) <= 1
这相当于
Σ d(x i ) - Σ d(y i ) <= 1
这相当于
Σ d(x i ) - d(y i ) <= 1
根据我们对两个相邻节点 x,y 的定义，我们知道neighbor_nodes(x)最多可以有一个平方差的位置，这意味着在我们的总和中
d(x i ) - d(y i ) = 0
对于 i 的 1 个值以外的所有值。让我们不失一般性地说，这对于 i=k 是正确的。此外，我们知道对于 i=k，节点最多移动了一个位置，因此它到目标状态的距离最多只能比前一个状态多一个，因此：
Σ d(x i ) - d(y i ) = d(x k ) - d(y k ) <= 1
表现出单调性。这显示了需要显示的内容，从而证明该算法将是最优的（以大 O 表示法或渐近的方式。）
请注意，我已经在大 O 表示法方面展示了最优性，但在调整启发式方法方面仍有很大的发挥空间。您可以对其添加额外的扭曲，以便更接近地估计到目标状态的实际距离，但是您必须确保启发式始终被低估，否则您会失去最优性！
稍后编辑许多月亮
（很久以后）再读一遍，我意识到我写它的方式有点混淆了这个算法的最优性的含义。
我试图在这里理解最优性有两种不同的含义：
1) 该算法产生一个最优解，即给定客观标准的最佳可能解。
2）该算法使用相同的启发式扩展所有可能算法的最少状态节点数。
理解为什么需要启发式算法的可接受性和单调性来获得 1) 的最简单方法是将 A* 视为 Dijkstra 最短路径算法在图上的应用，其中边权重由到目前为止行进的节点距离加上启发式算法给出距离。如果没有这两个属性，我们将在图中有负边，从而可能出现负循环，并且 Dijkstra 的最短路径算法将不再返回正确答案！（构建一个简单的例子来说服自己。）
2）实际上理解起来很混乱。为了充分理解这句话的意思，这句话有很多量词，比如在谈到其他算法时，将similar算法称为 A* 扩展节点和搜索而不需要先验信息（启发式除外）。显然，人们可以构建一个微不足道的反例，例如在每一步告诉你答案的神谕或精灵。为了深入理解这个陈述，我强烈建议阅读维基百科历史部分的最后一段，并查看那个仔细陈述的句子中的所有引文和脚注。
我希望这可以消除潜在读者之间的任何剩余困惑。
于 2010-09-27T17:34:02.027 回答
11
您可以使用基于数字位置的启发式方法，即每个字母与其目标状态的所有距离的总和越高，启发式值越高。然后你可以实现 A* 搜索，它可以被证明是时间和空间复杂度方面的最佳搜索（假设启发式是单调的和可接受的。）http://en.wikipedia.org/wiki/A*_search_algorithm
于 2009-09-08T20:44:13.017 回答
6
于 2009-09-08T18:34:07.917 回答
4
甜甜圈明白了！考虑到这个谜题相对有限的搜索空间，IDDFS 会做到这一点。这将是有效的，因此可以回答 OP 的问题。它会找到最优解，但不一定是最优复杂度。
实现 IDDFS 将是这个问题中更复杂的部分，我只想提出一种简单的方法来管理棋盘、游戏规则等。这特别解决了一种获取可解谜题初始状态的方法。问题的注释中暗示，并非所有 9 个牌的随机分配（将空槽视为特殊牌）都会产生可解决的难题。这是一个数学奇偶性问题......所以，这里有一个对游戏建模的建议：
列出所有代表游戏有效“移动”的 3x3 置换矩阵。这样的列表是 3x3s 的子集，其中包含全零和两个一。在 IDDFS 搜索树中，每个矩阵都有一个 ID，这将非常方便地跟踪移动。矩阵的另一种选择是让两个图块位置编号的元组交换，这可能会导致更快的实现。
此类矩阵可用于创建初始拼图状态，从“获胜”状态开始，并运行随机选择的任意数量的排列。除了确保初始状态是可解决的之外，这种方法还提供了一个指示性的移动数量，可以用来解决给定的难题。
现在让我们实现 IDDFS 算法并 [joke] 返回 A+[/joke] 的分配...
于 2009-09-08T19:22:32.313 回答
4
这是经典最短路径算法的一个例子。您可以在此处和此处阅读有关最短路径的更多信息。
简而言之，将拼图的所有可能状态视为某个图中的顶点。每次移动都会改变状态 - 因此，每个有效移动都代表图形的一条边。由于移动没有任何成本，您可能会认为每次移动的成本为 1。以下类似 c++ 的伪代码将适用于这个问题：
{
int[][] field = new int[3][3];
// fill the input here
map<string, int> path;
queue<string> q;
put(field, 0); // we can get to the starting position in 0 turns
while (!q.empty()) {
string v = q.poll();
int[][] take = decode(v);
int time = path.get(v);
if (isFinalPosition(take)) {
return time;
}
for each valid move from take to int[][] newPosition {
put(newPosition, time + 1);
}
}
// no path
return -1;
}
void isFinalPosition(int[][] q) {
return encode(q) == "123456780"; // 0 represents empty space
}
void put(int[][] position, int time) {
string s = encode(newPosition);
if (!path.contains(s)) {
path.put(s, time);
}
}
string encode(int[][] field) {
string s = "";
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) s += field[i][j];
return s;
}
int[][] decode(string s) {
int[][] ans = new int[3][3];
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) field[i][j] = s[i * 3 + j];
return ans;
}
于 2009-09-10T15:12:27.670 回答
2
请参阅此链接以了解我的并行迭代深化搜索 15-puzzle 的解决方案，它是 8-puzzle 的 4x4 老大哥。
于 2010-09-27T01:32:55.320 回答