哪个是最好的algorithm来提供解决15难题的动作？

我正在努力寻找一个随机生成的“15难题”的解决scheme步骤。 所以告诉我哪个是最好的algorithm来快速解决它。 提供给我的方法来做到这一点。

我正在做一个包含4 * 4数组的节点树，遍历所有尚未处理的节点，当我得到解决scheme时，我停止迭代。

在viewcontroller我有一些代码为

- (IBAction)getSolution:(id)sender { while (!appDelegate.isResultFound) { TreeNode *node=[self nodeWithLowestCostAndUnproceessedInRootNode]; [node expandNodeToChilds]; //break; } NSLog(@"Result Found"); if([appDelegate.result isEqualToString:@""]) NSLog(@"No move required"); else NSLog(@"%@",appDelegate.result); 

}

 -(TreeNode*)nodeWithLowestCostAndUnproceessedInRootNode{ TreeNode *node1; int lowestCost=200; for (TreeNode *node in appDelegate.treeNodes) { if([node myHeuristicsFunction]<lowestCost&&node.isProcessed==NO){ node1=node; lowestCost=[node.cost intValue]; } } return node1;} 

并在节点类我扩大了节点（除了家长使用的移动）

 -(void)expandNodeToChilds{ [self checkMovesForEmptyPlace]; if(top.x>=0){ [self addPuzzleBoxToTreeBySwapingPoint:top withMove:@"Bottom"]; } if(right.y<=3){ [self addPuzzleBoxToTreeBySwapingPoint:right withMove:@"Left"]; } if(bottom.x<=3){ [self addPuzzleBoxToTreeBySwapingPoint:bottom withMove:@"Top"]; } if(left.y>=0){ [self addPuzzleBoxToTreeBySwapingPoint:left withMove:@"Right"]; } self.isProcessed=true;} 

目前我使用曼哈顿与A *的距离，但没有得到显着的时间的结果，应用程序内存增加到1GB和应用程序崩溃。

Answer 1

我假设你正在寻找达到这个难题的最短路线。 您可以使用当前板和目标板之间曼哈顿距离的 A *algorithm作为成本函数。

下面的Java代码实现了algorithm。 函数求解器将N×N的大小作为inputN，然后将相应的N * N个数从[0，N ^ 2]中给出，给出二维网格中数字的位置。 它输出所需移动的最小数量和实际移动。 0表示拼图中的空位。

 import java.io.InputStreamReader; import java.util.*; class Solver{ private int N ; private int minMoves ; public static int[] correctRow; public static int[] correctCol; private class Node implements Comparable<Node>{ private Board board ; private int moves ; private Node prevNode ; public Node(Board board,int moves,Node prev){ this.board = board ; this.moves = moves ; this.prevNode = prev ; } public int compareTo(Node that){ int thisPriority = this.moves+this.board.manhattan() ; int thatPriority = that.moves+that.board.manhattan() ; if(thisPriority<thatPriority){ return -1 ; }else if(thisPriority>thatPriority){ return 1 ; }else{ return 0 ; } } } private Node lastNode ; private boolean solvable ; public Solver(Board initial){ N = initial.dimension() ; PriorityQueue<Node> pq = new PriorityQueue<Node>() ; PriorityQueue<Node> pq2 = new PriorityQueue<Node>() ; pq.add(new Node(initial,0,null)) ; pq2.add(new Node(initial.twin(),0,null)) ; while(true){ Node removed = pq.poll(); Node removed2 = pq2.poll(); if(removed.board.isGoal()){ minMoves = removed.moves ; lastNode = removed ; solvable = true ; break ; } if(removed2.board.isGoal()){ minMoves = -1 ; solvable = false ; break ; } Iterable<Board> neighbors = removed.board.neighbors() ; Iterable<Board> neighbors2 = removed2.board.neighbors() ; for(Board board : neighbors){ if(removed.prevNode != null && removed.prevNode.board.equals(board) ){ continue ; } pq.add(new Node(board,removed.moves+1,removed)) ; } for(Board board : neighbors2){ if(removed2.prevNode != null && removed2.prevNode.board.equals(board) ){ continue ; } pq2.add(new Node(board,removed2.moves+1,removed2)) ; } } } public boolean isSolvable(){ return solvable ; } public int moves(){ return minMoves ; } public Iterable<Board> solution(){ if(!isSolvable()){ return null ; } Stack<Board> stack = new Stack<Board>() ; Node node = lastNode ; while(true){ if(node == null) break ; Board board = node.board ; node = node.prevNode ; stack.push(board) ; } return stack ; } static void initCorrectRowsCols(int N){ correctRow = new int[N*N] ; int z = 0 ; for(int i = 0 ; i < N ; i++ ){ for(int j = 0 ; j < N ; j++ ){ correctRow[z++] = i ; } } z = 0 ; correctCol = new int[N*N] ; for(int i = 0 ; i < N ; i++ ){ for(int j = 0 ; j < N ; j++ ){ correctCol[z++] = j ; } } } public static void main(String[] args) { long start = System.currentTimeMillis(); // create initial board from file Scanner in = new Scanner(new InputStreamReader(System.in)); int N = in.nextInt(); initCorrectRowsCols(N); int[][] blocks = new int[N][N]; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) blocks[i][j] = in.nextInt(); Board initial = new Board(blocks); // solve the puzzle Solver solver = new Solver(initial); long end = System.currentTimeMillis(); System.out.println("time taken " + (end-start) + " milli seconds"); // print solution to standard output if (!solver.isSolvable()) System.out.println("No solution possible"); else { System.out.println("Minimum number of moves = " + solver.moves()); Stack<Board> stack = new Stack<Board>(); for (Board board : solver.solution()) stack.push(board); while(!stack.isEmpty()){ System.out.println(stack.pop()); } } } } class Board{ private int[][] array ; private int N ; int emptyRow; int emptyCol; boolean reached; int manhattan = 0; public Board(int[][] blocks){ N = blocks.length ; array = new int[N][N] ; reached = true; for(int i = 0 ; i < N ; i++ ){ for(int j = 0 ; j < N ; j++ ) { array[i][j] = blocks[i][j] ; if(array[i][j] == 0){ emptyRow = i; emptyCol = j; } if(array[i][j] != N*i + j+1){ if(!(i==N-1 && j==N-1)){ reached = false; } } int num = array[i][j] ; if(num==0){ continue ; } int indManhattan = Math.abs(Solver.correctRow[num-1] - i) + Math.abs(Solver.correctCol[num-1]-j) ; manhattan += indManhattan ; } } } public int dimension(){ return N ; } public int hamming(){ int outOfPlace = 0 ; for(int i = 0 ; i < N ; i++ ) { for(int j = 0 ; j < N ; j++ ){ if(i==N-1 && j==N-1) { break ; } if(array[i][j] != i*N+j+1){ outOfPlace++ ; } } } return outOfPlace ; } public int manhattan(){ return manhattan ; } public boolean isGoal(){ return reached ; } public Board twin(){ int[][] newArray = new int[N][N] ; for(int i = 0 ; i < N ; i++ ){ for(int j = 0 ; j < N ; j++ ){ newArray[i][j] = array[i][j] ; } } for(int i = 0 ; i < 2 ; i++ ) { if(newArray[i][0]==0 || newArray[i][5]==0){ continue ; } int temp = newArray[i][0] ; newArray[i][0] = newArray[i][6] ; newArray[i][7] = temp ; break ; } return new Board(newArray) ; } public boolean equals(Object y){ if(y==this){ return true ; } if(y == null){ return false ; } if(y.getClass() != this.getClass()){ return false ; } Board that = (Board)y ; if(that.array.length != this.array.length){ return false ; } for(int i = 0 ; i < N ; i++ ) { for(int j = 0 ; j < N ; j++ ) { if(that.array[i][j] != this.array[i][j] ){ return false ; } } } return true ; } public Iterable<Board> neighbors(){ Queue<Board> q = new ArrayDeque<Board>() ; int firstIndex0 = 0 ; int secondIndex0 = 0 ; for(int i = 0 ; i < N ; i++ ){ for(int j = 0 ; j < N ; j++ ) { if(array[i][j] == 0){ firstIndex0 = i ; secondIndex0 = j ; break ; } } } if(secondIndex0-1>-1){ int[][] newArr = getCopy() ; exch(newArr,firstIndex0,secondIndex0,firstIndex0,secondIndex0-1) ; q.add(new Board(newArr)) ; } if(secondIndex0+1<N){ int[][] newArr = getCopy() ; exch(newArr,firstIndex0,secondIndex0,firstIndex0,secondIndex0+1) ; q.add(new Board(newArr)) ; } if(firstIndex0-1>-1){ int[][] newArr = getCopy() ; exch(newArr,firstIndex0,secondIndex0,firstIndex0-1,secondIndex0) ; q.add(new Board(newArr)) ; } if(firstIndex0+1<N){ int[][] newArr = getCopy() ; exch(newArr,firstIndex0,secondIndex0,firstIndex0+1,secondIndex0) ; q.add(new Board(newArr)) ; } return q ; } private int[][] getCopy(){ int[][] copy = new int[N][N] ; for(int i = 0 ; i < N ; i++ ) { for(int j = 0 ; j < N ; j++ ){ copy[i][j] = array[i][j] ; } } return copy ; } private void exch(int[][] arr, int firstIndex,int secIndex,int firstIndex2,int secIndex2){ int temp = arr[firstIndex][secIndex] ; arr[firstIndex][secIndex] = arr[firstIndex2][secIndex2] ; arr[firstIndex2][secIndex2] = temp ; } public String toString(){ StringBuilder s = new StringBuilder() ; s.append(N + "\n") ; for(int i = 0 ; i < N ; i++ ){ for(int j = 0 ; j < N ; j++ ) { s.append(String.format("%4d",array[i][j])) ; } s.append("\n") ; } return s.toString() ; } } 

所以对于input

 3 7 8 5 4 0 2 3 6 1 

该algorithm生成输出

 Minimum number of moves = 28 3 7 8 5 4 0 2 3 6 1 3 7 0 5 4 8 2 3 6 1 3 7 5 0 4 8 2 3 6 1 3 7 5 2 4 8 0 3 6 1 3 7 5 2 4 0 8 3 6 1 3 7 5 2 4 6 8 3 0 1 3 7 5 2 4 6 8 3 1 0 3 7 5 2 4 6 0 3 1 8 3 7 5 2 4 0 6 3 1 8 3 7 5 2 0 4 6 3 1 8 3 0 5 2 7 4 6 3 1 8 3 5 0 2 7 4 6 3 1 8 3 5 4 2 7 0 6 3 1 8 3 5 4 2 7 1 6 3 0 8 3 5 4 2 7 1 6 0 3 8 3 5 4 2 0 1 6 7 3 8 3 5 4 2 1 0 6 7 3 8 3 5 0 2 1 4 6 7 3 8 3 0 5 2 1 4 6 7 3 8 3 1 5 2 0 4 6 7 3 8 3 1 5 2 4 0 6 7 3 8 3 1 5 2 4 3 6 7 0 8 3 1 5 2 4 3 6 7 8 0 3 1 5 2 4 3 0 7 8 6 3 1 5 2 4 0 3 7 8 6 3 1 0 2 4 5 3 7 8 6 3 1 2 0 4 5 3 7 8 6 3 1 2 3 4 5 0 7 8 6 3 1 2 3 4 5 6 7 8 0 

我也想提一下

• 寻找一个N-N的滑块拼图的最短解决scheme是NP-Hard ，所以不太可能存在一个有效的解决scheme。
• 如果您不是在寻找最短path解决scheme，而是在input中快速运行的任何解决scheme，那么本文描述了一个保证至多执行N ^ 3个移动的algorithm。

因此，尽pipe我给出的解决scheme在大多数input上运行得很快，但是在其他困难的input上可能会失败。

另外请注意，并非所有的谜题都是可以解决的。 对于无法解决的难题，该algorithm打印难题不能解决。

PS。 以上实现的algorithm遵循此编程任务的指导原则。