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
{
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;
}
6 回答
我将尝试重写之前的答案，详细说明为什么它是最优的 .
直接取自wikipedia的A *算法是
所以让我在这里填写所有细节 .
heuristic_estimate_of_distance是函数Σd（xi）其中d（ . ）是每个平方xi与其目标状态的曼哈顿距离 .所以设置
因为每个8,5都离他们的目标位置一个，d（ . ）= 1并且7距离目标状态2，d（7）= 2，所以它将具有1 12 1 = 4的
heuristic_estimate_of_distance.A *搜索到的节点集被定义为起始位置，后跟所有可能的合法位置 . 那就是说起始位置
x如上：那么函数
neighbor_nodes(x)会产生两种可能的合法动作：函数
dist_between(x,y)定义为从状态x过渡到y的平方移动数 . 对于算法而言，这总是等于A *中的1 .closedset和openset都是特定于A *算法的，并且可以使用标准数据结构（我相信优先级队列）来实现.came_from是一个数据结构，用于重建使用函数_637789找到的解决方案，其详细信息可以在维基百科上找到 . 如果您不想记住解决方案，则无需实现此目的 .最后，我将解决最优性问题 . 考虑一下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（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历史部分的最后一段，并查看该精心陈述的句子中的所有引文和脚注 .我希望这可以清除潜在读者之间的任何混淆 .
您可以使用基于数字位置的启发式算法，即每个字母距其目标状态的所有距离的总和越高，启发式值越高 . 然后你可以实现A *搜索，它可以被证明是时间和空间复杂性方面的最佳搜索（假设启发式是单调的并且是可接受的 . ）http://en.wikipedia.org/wiki/A*_search_algorithm
由于OP无法发布图片，这就是他所说的：
至于解决这个难题，请看一下iterative deepening depth-first search算法，因为this page与8-puzzle问题相关 .
甜甜圈得到了它！考虑到这个难题的相对有限的搜索空间，IDDFS将做到这一点 . 这将是有效的，因此回应OP的问题 . 它会找到最佳解决方案，但不一定是最佳复杂性 .
实现IDDFS将是这个问题中更复杂的部分，我只想提出一种简单的方法来管理电路板，游戏规则等 . 这特别针对获得可解决的难题的初始状态的方法 . 在问题的笔记中暗示，并非所有9个tites的随机特性（考虑空槽特殊的瓷砖），都会产生可解决的难题 . 这是一个数学平等的问题......所以，这是建模游戏的建议：
制作代表游戏有效“移动”的所有3x3排列矩阵的列表 . 这样的列表是具有全零和3个的3x3的子集 . 在IDDFS搜索树中，每个矩阵都有一个ID，可以非常方便地跟踪移动 . 矩阵的替代方法是将两个元组的tile位置数交换，这可能会导致更快的实现 .
这些矩阵可用于创建初始拼图状态，从"win"状态开始，并运行随机选择的任意数量的排列 . 除了确保初始状态是可解的之外，该方法还提供了指示性的移动数量，利用该移动可以解决给定的谜题 .
现在让我们实现IDDFS算法和[笑话]返回A [/笑话]的分配......
这是经典最短路径算法的示例 . 您可以阅读有关最短路径here和here的更多信息 .
简而言之，在一些图中考虑拼图的所有可能状态作为顶点 . 每次移动都会改变状态 - 因此，每个有效移动代表图形的边缘 . 由于移动没有任何成本，您可能会认为每次移动的成本为1.以下类似c的伪代码将适用于此问题：
请参阅此链接以获取我的parallel iterative deepening search for a solution to the 15-puzzle，这是8-puzzle的4x4大哥 .