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

Question

我正在阅读 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 其中 3 是 M 而 4 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;
}

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

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

Answer 1

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

对于非常小的问题，例如 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) 附近