如何获得解决“十五人游戏”的最少步数？
How to get minimum number of moves to solve `game of fifteen`?
我正在阅读有关 this 的内容，并想形成一个算法来找到解决此问题的最小步数。
我做的约束：一个 N X N 有一个空槽的矩阵，比如 0，将被绘制成数字 0 to n-1.
现在我们必须重新创建这个矩阵并形成从顶行开始从左到右按递增顺序排列数字并具有最后一个元素 0 即 (N X Nth) 元素的矩阵。
例如，
Input :
8 4 0
7 2 5
1 3 6
Output:
1 2 3
4 5 6
7 8 0
现在的问题是如何以尽可能少的步骤完成此操作。
在游戏中（提供link），您可以向左、向右、向上或向下移动，并将0（空槽）移动到相应的位置以形成最终矩阵。
此算法打印的输出是步数 M 然后 Tile(number) 移动方向 1 与上相邻元素交换， 2 表示下相邻元素，3 表示左相邻元素，4 表示右相邻元素。
喜欢，为了
2 <--- order of N X N matrix
3 1
0 2
答案应该是：3 4 1 2 其中 3 是 M 并且 4 1 2 是瓷砖移动的步骤。
所以我必须最小化这个算法的复杂度，并想找到最少的移动次数。请建议我解决此算法的最有效方法。
编辑：
我用 c++ 编写的代码, Please see the algorithm rather than pointing out other issues in code .
#include <bits/stdc++.h>
using namespace std;
int inDex=0,shift[100000],N,initial[500][500],final[500][500];
struct Node
{
Node* parent;
int mat[500][500];
int x, y;
int cost;
int level;
};
Node* newNode(int mat[500][500], int x, int y, int newX,
int newY, int level, Node* parent)
{
Node* node = new Node;
node->parent = parent;
memcpy(node->mat, mat, sizeof node->mat);
swap(node->mat[x][y], node->mat[newX][newY]);
node->cost = INT_MAX;
node->level = level;
node->x = newX;
node->y = newY;
return node;
}
int row[] = { 1, 0, -1, 0 };
int col[] = { 0, -1, 0, 1 };
int calculateCost(int initial[500][500], int final[500][500])
{
int count = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (initial[i][j] && initial[i][j] != final[i][j])
count++;
return count;
}
int isSafe(int x, int y)
{
return (x >= 0 && x < N && y >= 0 && y < N);
}
struct comp
{
bool operator()(const Node* lhs, const Node* rhs) const
{
return (lhs->cost + lhs->level) > (rhs->cost + rhs->level);
}
};
void solve(int initial[500][500], int x, int y,
int final[500][500])
{
priority_queue<Node*, std::vector<Node*>, comp> pq;
Node* root = newNode(initial, x, y, x, y, 0, NULL);
Node* prev = newNode(initial,x,y,x,y,0,NULL);
root->cost = calculateCost(initial, final);
pq.push(root);
while (!pq.empty())
{
Node* min = pq.top();
if(min->x > prev->x)
{
shift[inDex] = 4;
inDex++;
}
else if(min->x < prev->x)
{
shift[inDex] = 3;
inDex++;
}
else if(min->y > prev->y)
{
shift[inDex] = 2;
inDex++;
}
else if(min->y < prev->y)
{
shift[inDex] = 1;
inDex++;
}
prev = pq.top();
pq.pop();
if (min->cost == 0)
{
cout << min->level << endl;
return;
}
for (int i = 0; i < 4; i++)
{
if (isSafe(min->x + row[i], min->y + col[i]))
{
Node* child = newNode(min->mat, min->x,
min->y, min->x + row[i],
min->y + col[i],
min->level + 1, min);
child->cost = calculateCost(child->mat, final);
pq.push(child);
}
}
}
}
int main()
{
cin >> N;
int i,j,k=1;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
cin >> initial[j][i];
}
}
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
final[j][i] = k;
k++;
}
}
final[N-1][N-1] = 0;
int x = 0, y = 1,a[100][100];
solve(initial, x, y, final);
for(i=0;i<inDex;i++)
{
cout << shift[i] << endl;
}
return 0;
}
在上面的代码中，我正在检查具有最低成本 (how many numbers are misplaced from the final matrix numbers) 的每个子节点。
我想让这个算法更高效并降低它的时间复杂度。任何建议将不胜感激。
虽然这听起来很像作业题，但我会提供一些帮助。
对于非常小的问题，比如你的 2x2 或 3x3，你可以直接暴力破解。基本上，你对每一个可能的动作进行每一种可能的组合，跟踪每个动作转了多少圈，然后打印出最小的。
要对此进行改进，请维护已解决方案的列表，然后在任何时候进行可能的移动，如果该移动已经完成，请停止尝试该移动，因为它不可能是最小的。
例如，假设我处于这种状态（将矩阵展平为字符串以便于显示）：
5736291084
6753291084
5736291084
请注意，我们回到了之前看到的状态。这意味着它不可能是最小的移动，因为最小的移动将在不返回到先前状态的情况下完成。
你会想要创建一棵树来做这个，所以你会得到类似的东西：
134
529
870
/ \
/ \
/ \
/ \
134 134
529 520
807 879
/ | \ / | \
/ | X / X \
134 134 134 134 134 130
509 529 529 502 529 524
827 087 870 879 870 879
等等。请注意，我用 X 标记了一些，因为它们是重复的，因此我们不想进一步研究它们，因为我们知道它们不可能是最小的。
您只需不断重复此操作，直到您尝试了所有可能的解决方案（即，所有不间断的叶子都到达了一个解决方案），然后您就可以看到哪个是最短的。您也可以并行进行，这样您就可以在有人找到解决方案后停止，从而节省您的时间。
这种蛮力方法对大型矩阵无效。要解决这些问题，您需要研究一些严肃的软件工程。您可以采用的一种方法是将其分解成更小的矩阵并以这种方式求解，但这可能不是最佳路径。
这是一个需要解决较大值的棘手问题，并且与一些更棘手的 NP 问题一样。
从解开始，确定排列的秩
与上面相反的是如何预先生成所有可能值的列表。
从解决方案开始。它的排列等级为 0（例如，零步）：
012
345
678
然后，从那里进行所有可能的移动。所有这些动作的排列等级均为 1，即需要解决一个动作。
012
0 345
678
/ \
/ \
/ \
102 312
1 345 045
678 678
重复上述操作。每个新级别都具有相同的排列等级。生成所有可能的移动（在这种情况下，直到您的所有分支都被重复杀死）。
然后您可以将它们全部存储到一个对象中。展平矩阵将使这变得容易（例如使用 JavaScript 语法）：
{
'012345678': 0,
'102345678': 1,
'312045678': 1,
'142305678': 2,
// and so on
}
然后，要解决您的问题"minimum number of moves"，只需找到与您的起点相同的条目即可。排列的秩就是答案。
如果您处于可以预先生成整个解决方案的场景中，这将是一个很好的解决方案。生成需要时间，但查找速度快如闪电（这类似于破解哈希的 "rainbow tables"）。
如果你必须即时解决（没有预生成），那么第一个解决方案，从答案开始，逐步解决，直到找到更好的解决方案。
虽然最大复杂度为 O(n!)，但只有 O(n^2) 种可能的解决方案。边走边从树中切掉重复项，您的复杂度将介于这两者之间，可能在 O(n^3) ~ O(2^n)
附近
你可以使用 BFS。
每个状态就是一个顶点，两个顶点之间如果可以相互传递则有一条边
例如
8 4 0
7 2 5
1 3 6
和
8 0 4
7 2 5
1 3 6
已连接。
通常，您可能希望使用一些数字来表示您当前的状态。对于小格子，按照数字的顺序即可。例如，
8 4 0
7 2 5
1 3 6
只是 840725136.
如果网格很大，您可以考虑使用数字排列的等级作为状态的表示。例如，
0 1 2
3 4 5
6 7 8
应该是0，因为它是排列中的第一个。
和
0 1 2
3 4 5
6 7 8
（用0表示）
和
1 0 2
3 4 5
6 7 8
（用其他数字 X 表示）
连接与图中的 0 和 X 连接相同。
算法的复杂度应该是 O(n!) 因为最多有 n! vertices/permutations.
我正在阅读有关 this 的内容，并想形成一个算法来找到解决此问题的最小步数。
我做的约束：一个 N X N 有一个空槽的矩阵，比如 0，将被绘制成数字 0 to n-1.
现在我们必须重新创建这个矩阵并形成从顶行开始从左到右按递增顺序排列数字并具有最后一个元素 0 即 (N X Nth) 元素的矩阵。
例如，
Input :
8 4 0
7 2 5
1 3 6
Output:
1 2 3
4 5 6
7 8 0
现在的问题是如何以尽可能少的步骤完成此操作。
在游戏中（提供link），您可以向左、向右、向上或向下移动，并将0（空槽）移动到相应的位置以形成最终矩阵。
此算法打印的输出是步数 M 然后 Tile(number) 移动方向 1 与上相邻元素交换， 2 表示下相邻元素，3 表示左相邻元素，4 表示右相邻元素。
喜欢，为了
2 <--- order of N X N matrix
3 1
0 2
答案应该是：3 4 1 2 其中 3 是 M 并且 4 1 2 是瓷砖移动的步骤。
所以我必须最小化这个算法的复杂度，并想找到最少的移动次数。请建议我解决此算法的最有效方法。
编辑：
我用 c++ 编写的代码, Please see the algorithm rather than pointing out other issues in code .
#include <bits/stdc++.h>
using namespace std;
int inDex=0,shift[100000],N,initial[500][500],final[500][500];
struct Node
{
Node* parent;
int mat[500][500];
int x, y;
int cost;
int level;
};
Node* newNode(int mat[500][500], int x, int y, int newX,
int newY, int level, Node* parent)
{
Node* node = new Node;
node->parent = parent;
memcpy(node->mat, mat, sizeof node->mat);
swap(node->mat[x][y], node->mat[newX][newY]);
node->cost = INT_MAX;
node->level = level;
node->x = newX;
node->y = newY;
return node;
}
int row[] = { 1, 0, -1, 0 };
int col[] = { 0, -1, 0, 1 };
int calculateCost(int initial[500][500], int final[500][500])
{
int count = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (initial[i][j] && initial[i][j] != final[i][j])
count++;
return count;
}
int isSafe(int x, int y)
{
return (x >= 0 && x < N && y >= 0 && y < N);
}
struct comp
{
bool operator()(const Node* lhs, const Node* rhs) const
{
return (lhs->cost + lhs->level) > (rhs->cost + rhs->level);
}
};
void solve(int initial[500][500], int x, int y,
int final[500][500])
{
priority_queue<Node*, std::vector<Node*>, comp> pq;
Node* root = newNode(initial, x, y, x, y, 0, NULL);
Node* prev = newNode(initial,x,y,x,y,0,NULL);
root->cost = calculateCost(initial, final);
pq.push(root);
while (!pq.empty())
{
Node* min = pq.top();
if(min->x > prev->x)
{
shift[inDex] = 4;
inDex++;
}
else if(min->x < prev->x)
{
shift[inDex] = 3;
inDex++;
}
else if(min->y > prev->y)
{
shift[inDex] = 2;
inDex++;
}
else if(min->y < prev->y)
{
shift[inDex] = 1;
inDex++;
}
prev = pq.top();
pq.pop();
if (min->cost == 0)
{
cout << min->level << endl;
return;
}
for (int i = 0; i < 4; i++)
{
if (isSafe(min->x + row[i], min->y + col[i]))
{
Node* child = newNode(min->mat, min->x,
min->y, min->x + row[i],
min->y + col[i],
min->level + 1, min);
child->cost = calculateCost(child->mat, final);
pq.push(child);
}
}
}
}
int main()
{
cin >> N;
int i,j,k=1;
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
cin >> initial[j][i];
}
}
for(i=0;i<N;i++)
{
for(j=0;j<N;j++)
{
final[j][i] = k;
k++;
}
}
final[N-1][N-1] = 0;
int x = 0, y = 1,a[100][100];
solve(initial, x, y, final);
for(i=0;i<inDex;i++)
{
cout << shift[i] << endl;
}
return 0;
}
在上面的代码中，我正在检查具有最低成本 (how many numbers are misplaced from the final matrix numbers) 的每个子节点。
我想让这个算法更高效并降低它的时间复杂度。任何建议将不胜感激。
虽然这听起来很像作业题，但我会提供一些帮助。
对于非常小的问题，比如你的 2x2 或 3x3，你可以直接暴力破解。基本上，你对每一个可能的动作进行每一种可能的组合，跟踪每个动作转了多少圈，然后打印出最小的。
要对此进行改进，请维护已解决方案的列表，然后在任何时候进行可能的移动，如果该移动已经完成，请停止尝试该移动，因为它不可能是最小的。
例如，假设我处于这种状态（将矩阵展平为字符串以便于显示）：
5736291084
6753291084
5736291084
请注意，我们回到了之前看到的状态。这意味着它不可能是最小的移动，因为最小的移动将在不返回到先前状态的情况下完成。
你会想要创建一棵树来做这个，所以你会得到类似的东西：
134
529
870
/ \
/ \
/ \
/ \
134 134
529 520
807 879
/ | \ / | \
/ | X / X \
134 134 134 134 134 130
509 529 529 502 529 524
827 087 870 879 870 879
等等。请注意，我用 X 标记了一些，因为它们是重复的，因此我们不想进一步研究它们，因为我们知道它们不可能是最小的。
您只需不断重复此操作，直到您尝试了所有可能的解决方案（即，所有不间断的叶子都到达了一个解决方案），然后您就可以看到哪个是最短的。您也可以并行进行，这样您就可以在有人找到解决方案后停止，从而节省您的时间。
这种蛮力方法对大型矩阵无效。要解决这些问题，您需要研究一些严肃的软件工程。您可以采用的一种方法是将其分解成更小的矩阵并以这种方式求解，但这可能不是最佳路径。
这是一个需要解决较大值的棘手问题，并且与一些更棘手的 NP 问题一样。
从解开始，确定排列的秩
与上面相反的是如何预先生成所有可能值的列表。
从解决方案开始。它的排列等级为 0（例如，零步）：
012
345
678
然后，从那里进行所有可能的移动。所有这些动作的排列等级均为 1，即需要解决一个动作。
012
0 345
678
/ \
/ \
/ \
102 312
1 345 045
678 678
重复上述操作。每个新级别都具有相同的排列等级。生成所有可能的移动（在这种情况下，直到您的所有分支都被重复杀死）。
然后您可以将它们全部存储到一个对象中。展平矩阵将使这变得容易（例如使用 JavaScript 语法）：
{
'012345678': 0,
'102345678': 1,
'312045678': 1,
'142305678': 2,
// and so on
}
然后，要解决您的问题"minimum number of moves"，只需找到与您的起点相同的条目即可。排列的秩就是答案。
如果您处于可以预先生成整个解决方案的场景中，这将是一个很好的解决方案。生成需要时间，但查找速度快如闪电（这类似于破解哈希的 "rainbow tables"）。
如果你必须即时解决（没有预生成），那么第一个解决方案，从答案开始，逐步解决，直到找到更好的解决方案。
虽然最大复杂度为 O(n!)，但只有 O(n^2) 种可能的解决方案。边走边从树中切掉重复项，您的复杂度将介于这两者之间，可能在 O(n^3) ~ O(2^n)
附近你可以使用 BFS。
每个状态就是一个顶点，两个顶点之间如果可以相互传递则有一条边
例如
8 4 0
7 2 5
1 3 6
和
8 0 4
7 2 5
1 3 6
已连接。
通常，您可能希望使用一些数字来表示您当前的状态。对于小格子，按照数字的顺序即可。例如，
8 4 0
7 2 5
1 3 6
只是 840725136.
如果网格很大，您可以考虑使用数字排列的等级作为状态的表示。例如，
0 1 2
3 4 5
6 7 8
应该是0，因为它是排列中的第一个。
和
0 1 2
3 4 5
6 7 8
（用0表示） 和
1 0 2
3 4 5
6 7 8
（用其他数字 X 表示） 连接与图中的 0 和 X 连接相同。
算法的复杂度应该是 O(n!) 因为最多有 n! vertices/permutations.