Java 优化技术（2）

look_w

首先，一种有效的解决方案在本节中，我们将讨论我们的解拼图程序的初始实现。这将包含好几个代码段，所以耐心些；一旦解释了涉及的基本算法，我们就开始进行优化。可以在        参考资料中获取这一初始实现的源代码以及我们将在本文后面讨论的优化源代码。      
解拼图算法我们的解拼图算法将计算 Meteor 拼图所有可能的解决方案。这意味着我们必须穷举搜索使用块填充图板的每种可能方法。完成这个任务的一个步骤是确定块的所有        排列。一种排列是在图板上放置一个图块的一种可能方法。我们知道每块都可以被上下翻转并且可以沿着其中一个六边形的六条边旋转，所以得到了总共 12 种（2 x 6）可能的方法将一块放入图板的一个位置。因为有 50 个图板位置，所以在图板上放置单一块的可能方法总共有 600（2 x 6 x 50）种。      
当然，实际上所有这些“可能的方法”并非都行得通。例如，一些方法中有一块悬于图板的边上，这显然不能生成一种解决方案。对所有块递归地重复这一过程就产生了第一种算法，它将通过尝试用块填充图板的每种可能方法来找出每种可能的解决方案。清单 1 显示了这一算法的代码。我们使用一个称为         pieceList 的简单         ArrayList 对象来保存所有块。         board 对象表示拼图板，我们将简略地讨论它。      
清单 1. 初始的解拼图算法

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 33 34 35

public void solve() {   if (!pieceList.isEmpty()) {     // Take the first available piece     Piece currentPiece = (Piece)pieceList.remove(0);     for (int i = 0; i < Piece.NUMBEROFPERMUTATIONS; i++) {       Piece permutation = currentPiece.nextPermutation();       for (int j = 0; j < Board.NUMBEROFCELLS; j++) {         if (board.placePiece(permutation, j)) {                       /* We have now put a piece on the board, so we have to              continue this process with the next piece by              recursively calling the solve() method */                       solve();                       /* We're back from the recursion and we have to continue              searching at this level, so we remove the piece we              just added from the board */                       board.removePiece(permutation);         }         // Else the permutation doesn't fit on the board       }     }     // We're done with this piece     pieceList.add(0, currentPiece);   }   else {           /* All pieces have been placed on the board so we        have found a solution! */           puzzleSolved();   } }

既然我们已经建立了基本算法，现在就需要研究其它两个重要问题：

• 将如何表示一块拼图？
• 将如何实现拼图板？

在清单 1 显示的算法中，我们使用         Piece 类和         Board 类。现在让我们研究一下这两个类的实现。      
Piece 类在开始设计         Piece 类之前，需要考虑这个类应该表示什么。当您查看图 2 时，可以看见 Meteor 拼图块是由 5 个相连的单元构成的。每个单元都是一个正六边形，它有六条边：EAST、SOUTHEAST、SOUTHWEST、WEST、NORTHWEST 和 NORTHEAST。当两个单元在特定边相连时，我们称它们        邻居。最后，         Piece 只是一组五个相连的         Cell 对象。每个         Cell 对象都有 6 条边和 6 个可能相邻的单元。如清单 2 所示，实现         Cell 类很简单。注：我们在         Cell 对象中保留了一个         processed 标志。以后，我们将使用这一标志以避免无限循环。      
图 2. 拼图块及其单元清单 2. Cell 类

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

public class Cell {   public static final int NUMBEROFSIDES = 6;   // The sides of a cell   public static final int EAST      = 0;   public static final int SOUTHEAST = 1;   public static final int SOUTHWEST = 2;   public static final int WEST      = 3;   public static final int NORTHWEST = 4;   public static final int NORTHEAST = 5;   private Cell[] neighbours = new Cell[NUMBEROFSIDES];   private boolean processed = false;   public Cell getNeighbour(int side) {     return neighbours[side];   }   public void setNeighbour(int side, Cell cell) {     neighbours[side] = cell;   }   public boolean isProcessed() {     return processed;   }   public void setProcessed(boolean b) {     processed = b;   } }