哪个是提供解决15个谜题的最佳算法？ [英] Which is the best algorithm to provide moves to solve 15 puzzle?
本文介绍了哪个是提供解决15个谜题的最佳算法？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我正在努力寻找随机生成的15难题的解决方案步骤。那么告诉我哪个是最好的算法来快速解决它。为我提供这样做的方法。
i am working to find the solution steps for a randomly generated "15 puzzle". So tell me which is the best algorithm to use to solve it fast. Provide me approach to do so.
我正在制作一个包含4 * 4数组的节点树，并遍历尚未处理的所有节点，当我得到解决方案我停止迭代。
I am making a tree of nodes containing 4*4 array and traversing through all the node which are not yet processed and when i get the solution i stop the iteration.
在viewcontroller中，我有一些代码为
In viewcontroller i have some code as
- (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;}
和节点class我正在扩展节点为（除了父节点使用的移动）
and in node class i am expanding the node as (except the move used by the parent)
-(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和应用程序崩溃。
Currently i am using manhattan distance with A*, but not getting the result in significant time, app memory increases to 1GB and app crashes.
推荐答案
我是假设您正在寻找达到这个难题的目标的最短路径。您可以使用 A *算法和曼哈顿距离作为成本函数。
I am assuming that you are looking for the shortest way to reach the goal for this puzzle. You can use A* algorithm with the manhattan distance between the current board and the goal board as the cost function.
以下Java代码实现了该算法。函数Solver将NxN板的大小作为输入N，然后将相应的N * N个数作为[0，N ^ 2]，给出2d网格中数字的位置。它输出所需的最小移动次数和实际移动次数。 0表示拼图中的空位。
The following code in Java implements the algorithm. The function Solver takes as input N, the size of the NxN board and then the corresponding N*N numbers ranging from [0,N^2] giving the locations of the numbers in the 2d grid. It outputs the minimum number of moves that are required and the actual moves. 0 indicates the empty position in the puzzle.
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() ;
}
}
所以对于输入
3
7 8 5
4 0 2
3 6 1
该算法生成输出
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-by-N滑块拼图的最短解决方案是 NP -Hard ，因此不太可能存在有效的解决方案。
- 如果您不是在寻找最短路径解决方案，而是在输入中快速运行的任何解决方案，那么这篇论文描述了一种算法，可以保证最多执行N ^ 3次移动。
- Finding a shortest solution to an N-by-N slider puzzle is NP-Hard, so it's unlikely that an efficient solution exists.
- If you are not looking for a shortest path solution but any solution that runs fast in the input then this paper describes an algorithm that guarantees to perform at most N^3 moves.
因此，尽管我给出的解决方案在大多数输入上运行速度很快，但在其他困难的输入上可能会失败。
Thus although the solution I have given runs fast on most of the inputs, it may fail on other difficult inputs.
另请注意，并非所有谜题都可以解决。对于无法解决的谜题，算法会打印拼图无法解决。
Also note that not all puzzles are solvable. For the puzzles that cannot be solved, the algorithm prints that the puzzle cannot be solved.
PS。上面实现的算法遵循此编程任务的指导原则。 a>。
PS. The algorithm implemented above follows the guidelines of this programming assignment.
这篇关于哪个是提供解决15个谜题的最佳算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
