填补（fill-up）算法我们的初始算法的第二个缺点是它本质上会生成许多孤岛。之所以发生这种情况是因为我们采用了块的一种排列，并且在切换至块的下一个排列之前在图板上移动了该块。例如，在图 5 中，我们已经将蓝色块的当前排列移动到其第三个可能的图板位置上。正如您可以看到的，这在图板的顶部生成了一个孤岛。由于我们正生成许多孤岛，所以在上一节添加的孤岛检测剪枝显著地改进了性能，尽管如此，如果可以更新我们的算法以便在一开始就使其生成的孤岛数目最小化，则会更好。
图 5. 生成孤岛 要减少生成的孤岛的数量，最好我们的算法集中于填充空的图板位置。因此，我们将尝试从左到右、从上到下来填充图板，而不是致力于尝试填充图板的每种可能方法。在清单 9 中显示了这个新的解拼图算法：
清单 9. 填补解拼图算法1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
| public void solve() {
if (!pieceList.isEmpty()) {
// We'll try to find a piece that fits on this board cell
int emptyBoardCellIdx = board.getFirstEmptyBoardCellIndex();
// Try all available pieces
for (int h = 0; h < pieceList.size(); h++) {
Piece currentPiece = (Piece)pieceList.remove(h);
for (int i = 0; i < Piece.NUMBEROFPERMUTATIONS; i++) {
Piece permutation = currentPiece.nextPermutation();
/* Instead of always using the first cell to manipulate
the piece, we now try to fit any cell of the piece on
the first empty board cell */
for (int j = 0; j < Piece.NUMBEROFCELLS; j++) {
if (board.placePiece(permutation, j, emptyBoardCellIdx)) {
if (!prune()) solve();
board.removePiece(permutation);
}
}
}
/* Put the piece back into the list at the position where
we took it to maintain the order of the list */
pieceList.add(h, currentPiece);
}
}
else {
puzzleSolved();
}
}
|
我们的新方法尝试将任何可用的块填充到第一个空的图板单元。只尝试所有可用的块的全部可能排列是不够的。我们还应该尝试用块中的任何块单元覆盖空的图板单元。在初始算法中，我们以默认方式假设我们操作的块使用它的第一个单元。现在，我们必须尝试块中的每个单元，如图 6 中所示。当我们尝试将带有索引 0 的块单元放入图板位置 5（图 6 中画圈的）时，粉红色块的当前排列不适合图板。然而，当我们使用第二个块单元时，它却很适合。
图 6. 块的单元 运行更新的程序当我们运行初始程序时，它无法在适当的时间内找到任何解决方案。让我们使用改进的算法和孤岛检测剪枝再次尝试。可以在 meteor.algorithm 包中找到程序这一版本的代码。当我们用 java meteor.algorithm.Solver 启动它时，几乎立即看到弹出解决方案。我们的测试机器用 157 秒计算出所有 2,098 种可能的解决方案。这样，我们已经获得了巨大的性能改进：从几个小时生成一个解决方案到不到十分之一秒生成一个解决方案。快了大约 400,000 倍。另外，与孤岛检测剪枝结合的初始算法以 6,363 秒完成。因此，剪枝优化使速度提高了 10,000 倍，而填补算法使速度又提高了 40 倍。很明显，花一些时间研究您的算法并试图对其进行优化是值得的。 |
