gpt4 book ai didi

algorithm - 如何获得解决 `game of fifteen` 的最小步数?

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:02:30 25 4
gpt4 key购买 nike

我正在阅读 this并想形成一个算法来找到解决这个问题的最小步数。

我制定的约束条件:具有一个空槽的 N X N 矩阵,比如 0,将被绘制为具有数字 0 到 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

现在的问题是如何以尽可能少的步骤完成此操作。在游戏中(提供链接),您可以向左、向右、向上或向下移动,并将 0(空槽)移动到相应位置以形成最终矩阵。

此算法要打印的输出是步数,例如 M,然后 Tile(数字)朝 1 的方向移动用于与上相邻元素交换,2 用于下相邻元素,3 用于左相邻元素,4 用于右相邻元素。

喜欢,为了

2     <--- order of N X N matrix
3 1
0 2

答案应该是:3 4 1 2 其中 3M4 1 2 是步骤瓷砖运动。

所以我必须最小化此算法的复杂性,并希望找到最少的移动次数。请建议我解决此算法的最有效方法。

编辑:

我用c++写的请看算法,不要指出代码中的其他问题

#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;
}

在上面的代码中,我正在检查具有最小成本的每个子节点(有多少数字从最终矩阵数字中错位)。

我想让这个算法更高效并降低它的时间复杂度。任何建议将不胜感激。

最佳答案

虽然这听起来很像家庭作业问题,但我会提供一些帮助。

对于非常小的问题,例如 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

然后,从那里进行所有可能的移动。所有这些 Action 的排列等级为 1,即需要解决一个 Action 。

                         012
0 345
678
/ \
/ \
/ \
102 312
1 345 045
678 678

重复上述操作。每个新级别都具有相同的排列等级。生成所有可能的移动(在这种情况下,直到您的所有分支都作为重复项被杀死)。

然后您可以将它们全部存储到一个对象中。展平矩阵将使这变得容易(例如使用 JavaScript 语法):

{
'012345678': 0,
'102345678': 1,
'312045678': 1,
'142305678': 2,
// and so on
}

然后,要解决您的问题“最少步数”,只需找到与您的起点相同的条目即可。排列的秩就是答案。

如果您处于可以预先生成整个解决方案的场景中,这将是一个很好的解决方案。生成需要时间,但查找速度快如闪电(这类似于破解哈希的“彩虹表”)。

如果您必须即时解决(没有预生成),那么第一个解决方案,从答案开始,逐步解决,直到找到更好的解决方案。

虽然最大复杂度为 O(n!),但只有 O(n^2) 种可能的解决方案。边走边从树中切掉重复项,您的复杂度将介于这两者之间,可能在 O(n^3) ~ O(2^n) 附近

关于algorithm - 如何获得解决 `game of fifteen` 的最小步数?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44642285/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com