ios - 提供解决 15 个谜题的 Action 的最佳算法是哪个？
<p><div>
<aside class="s-notice s-notice__info post-notice js-post-notice mb16"role="status">
<div class="d-flex fd-column fw-nowrap">
<div class="d-flex fw-nowrap">
<div class="flex--item wmn0 fl1 lh-lg">
<div class="flex--item fl1 lh-lg">
<b>关闭</b>。这个问题需要<a href="https://stackoverflow.com/help/closed-questions" rel="noreferrer noopener nofollow">details or clarity</a> .它目前不接受答案。
<br><hr><h1><strong>Best Answer-推荐答案</ strong></h1><br>
<p><p>我假设您正在寻找达到 <a href="http://en.wikipedia.org/wiki/15_puzzle" rel="noreferrer noopener nofollow">this</a> 目标的最短路径。谜。您可以使用 <a href="http://en.wikipedia.org/wiki/A%2a_search_algorithm" rel="noreferrer noopener nofollow">A* algorithm</a>与 <a href="http://en.wiktionary.org/wiki/Manhattan_distance" rel="noreferrer noopener nofollow">manhattan distance</a>在当前棋盘和目标棋盘之间作为成本函数。 </p>
<p><a href="http://ideone.com/DCirVQ" rel="noreferrer noopener nofollow">following code in Java</a>实现算法。函数 Solver 将输入 N、NxN 板的大小，然后是从 范围内的相应 N*N 数字，给出二维网格中数字的位置。它输出所需的最小移动次数和实际移动。 0 表示拼图中的空白位置。</p>
<pre><code>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 ;
int z = 0 ;
for(int i = 0 ; i < N ; i++ ){
for(int j = 0 ; j < N ; j++ ){
correctRow = i ;
}
}
z = 0 ;
correctCol = new int ;
for(int i = 0 ; i < N ; i++ ){
for(int j = 0 ; j < N ; j++ ){
correctCol = 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;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
blocks = 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 ;
reached = true;
for(int i = 0 ; i < N ; i++ ){
for(int j = 0 ; j < N ; j++ ) {
array = blocks ;
if(array == 0){
emptyRow = i;
emptyCol = j;
}
if(array != N*i + j+1){
if(!(i==N-1 && j==N-1)){
reached = false;
}
}
int num = array ;
if(num==0){
continue ;
}
int indManhattan = Math.abs(Solver.correctRow - i)
+ Math.abs(Solver.correctCol-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*N+j+1){
outOfPlace++ ;
}
}
}
return outOfPlace ;
}
public int manhattan(){
return manhattan ;
}
public boolean isGoal(){
return reached ;
}
public Board twin(){
int[][] newArray = new int ;
for(int i = 0 ; i < N ; i++ ){
for(int j = 0 ; j < N ; j++ ){
newArray = array ;
}
}
for(int i = 0 ; i < 2 ; i++ ) {
if(newArray==0 || newArray==0){
continue ;
}
int temp = newArray ;
newArray = newArray ;
newArray = 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 != this.array ){
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 == 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 ;
for(int i = 0 ; i < N ; i++ ) {
for(int j = 0 ; j < N ; j++ ){
copy = array ;
}
}
return copy ;
}
private void exch(int[][] arr, int firstIndex,int secIndex,int firstIndex2,int secIndex2){
int temp = arr ;
arr = arr ;
arr = 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)) ;
}
s.append("\n") ;
}
return s.toString() ;
}
}
</code></pre>
<p>所以对于输入</p>
<pre><code>3
7 8 5
4 0 2
3 6 1
</code></pre>
<p>算法生成输出</p>
<pre><code>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
</code></pre>
<p>我也想提一下</p>
<ul>
<li>找到 N×Nslider 拼图的最短解是 <a href="http://www.aaai.org/Library/AAAI/1986/aaai86-027.php" rel="noreferrer noopener nofollow">NP-Hard</a> ，因此不太可能存在有效的解决方案。</li>
<li>如果您不是在寻找最短路径解决方案，而是在输入中快速运行的解决方案，那么 <a href="http://cseweb.ucsd.edu/~ccalabro/essays/15_puzzle.pdf" rel="noreferrer noopener nofollow">this</a>论文描述了一种保证最多执行 N^3 步的算法。</li>
</ul>
<p>因此，尽管我给出的解决方案在大多数输入上运行得很快，但在其他困难的输入上可能会失败。</p>
<p>另请注意，并非所有谜题都可以解决。对于无法解决的谜题，算法会打印出无法解决的谜题。</p>
<p>PS。上面实现的算法遵循 <a href="http://www.cs.princeton.edu/courses/archive/spr10/cos226/assignments/8puzzle.html" rel="noreferrer noopener nofollow">this programming assignment</a> 的指导方针。 .</p></p>
<p style="font-size: 20px;">关于ios - 提供解决 15 个谜题的 Action 的最佳算法是哪个？，我们在Stack Overflow上找到一个类似的问题：
<a href="https://stackoverflow.com/questions/23630620/" rel="noreferrer noopener nofollow" style="color: red;">
https://stackoverflow.com/questions/23630620/
</a>
</p>
页:
[1]