java - 表示 NxN 板的最有效数据结构

Question

我想知道你们是否可以指出一些更有效的数据结构，我可以在其中表示 NxN 拼图板。

此时，它仍然是一个基本的二维矩阵 (int[][])。虽然它达到了它的目的，但我觉得它在整个性能方面有所欠缺。

这个谜题本身被称为“滑动问题”，例如8puzzle, 15puzzle,..

一个 8 拼图看起来像这样:

  1 3         1 2 3
4 2 5   --->  4 5 6
7 8 6         7 8 

我正在使用的一个操作是 O(n^4)，我想为此找到一个“解决方案”。此操作尝试为每个板条目找到应该的值的坐标。 (距离启发式)

value = 1;
for(int i = 0; i <puzzle.length; i++)
   for(int j = 0; j < puzzle[0].length; j++)
      getPosition(value++)

getPosition 也使用 2 个 for 循环:

    for (int i = 0; i < puzzle.length; i++)
        for (int j = 0; j < puzzle[0].length; j++) 
            if(puzzle[i][j]==value)
                return new int[]{i,j};

我在考虑使用 HashMap，使用 new int[]{x_coord, y_coord} 作为每个条目的键。

期待您的建议，在此先感谢您!

Answer 1

为了根据复杂性优化数据结构(假设你有大小为 100x100 左右的板，这确实值得考虑)你首先必须弄清楚 哪些操作将被最频繁地执行。

在这样的谜题中可能经常需要的一个操作是

Given coordinates (r,c) : Which number is at these coordinates?

阵列已经非常适合这个。可以考虑使用一维数组来强制执行更多的数据局部性，但需要详细的基准来证明这一决定的合理性。

你提到了另一个操作:

“此操作尝试为每个板条目查找应该存在的值的坐标”

这听起来有点不寻常，因为我无法想象您可能需要它做什么 - 除了，也许，用于某种“距离测量”。然而，这个操作的核心可以表述为

Given a number x: Which are the coordinates (r,c) of this number?

这又可以用数组来解决，即两个数组

int rows[] = new int[totalSize];
int cols[] = new int[totalSize];

因此，根据您的示例中的电路板:

  1 3
4 2 5
7 8 6

这些数组可以包含

rows = { 0, 0, 1, 0, 1, 1, 2, 2, 2 }
cols = { 0, 1, 1, 2, 0, 2, 2, 0, 1 }

即5的坐标当前为(rows[5], columns[5]) = (1,2)

当然，您必须为应用于棋盘的每一步移动更新此数据结构。这意味着每次移动的开销都是恒定的(!)。但是对于更大的板，这将很快得到返回，因为找到某个值的坐标现在只需要 O(1)，与以前的 O(n²) 相比。