アルゴリズム

コーセラプリンストン大学アルゴリズム第4週：8パズルパズル



Coursera Princeton University Algorithm Week4



タスクリンク： http://coursera.cs.princeton.edu/algs4/assignments/8puzzle.html

タスクの難しさは、妥当な内部変数、特にソルバークラス変数を作成することです。その後、プロンプトに従って、行を段階的に解決します。



ソルバークラス変数は次のとおりです。

private SearchNode currentNode private SearchNode currentTwinNode private Stack stackBoard

ここで、スタックメモリstackBoardプロセスを使用した結果セット。結果セットは、そのプリカーサーノードを前方に見つけるためにターゲットの最終結果に基づいているため、スタックを使用するだけで、結果セットの順序を逆にすることができます。



SearchNodeを使用してノードクラスを検索します。内部クラスには、次の要素が含まれています。

private final Board board // current board case private final int moves // current board mobile steps private SearchNode preSearcchNode = null // Current board precursor private final int priority // current state priority

currentNode元のパネルは現在ノードを探しています。currentTwinNode交換パネルは現在ノードを探しています。確かな数学的、解決策がない場合は、元のパネルパネルの少なくとも1つの解決策を交換します。その交換は次のとおりです。

public Board twin () // exchange plate by any pair of blocks is obtained. { int i1 = 0, j1 = 0, i2 = 1, j2 = 1 if (blocks[i1][j1] == BLANK) { i1 = 1 j1 = 0 } if (blocks[i2][j2] == BLANK) { i2 = 1 j2 = 0 } Board newBoard = swap(i1, j1, i2, j2) return newBoard }

配列a [i1] [j1]と値[i2] [j2]で、スイッチがグローバルである場合のスワップスワップは、最初のスイッチングアレイ、元のアレイのコピーの値、および交換操作。



さらに、この記事コードは標準に保存されていないため、改善する必要があります。

import java.util.ArrayList public class Board { private final int [][]blocks private static final int BLANK = 0 private final int N public Board (int [] [] blocks) // create n * n board { if (blocks == null) throw new java.lang.IllegalArgumentException('the blocks is null') N = blocks.length this.blocks = new int[N][N] for (int i = 0 i 0) { Board upBoard = swap(i, j, i-1, j) boards.add(upBoard) } // next if (i 0) { Board leftBoard = swap(i, j, i, j-1) boards.add(leftBoard) } // Right if (j import edu.princeton.cs.algs4.MinPQ import edu.princeton.cs.algs4.Stack public class Solver { private SearchNode currentNode private SearchNode currentTwinNode private Stack stackBoard private class SearchNode implements Comparable { private final Board board // current board case private final int moves // current board mobile steps private SearchNode preSearcchNode = null // predecessor of the current board private final int priority // current state priority public SearchNode(Board board, SearchNode pNode) { this.board = board this.preSearcchNode = pNode if (preSearcchNode == null) moves = 0 else moves = preSearcchNode.getMoves() + 1 priority = board.manhattan() + getMoves() } public int compareTo(SearchNode otherNode) { return Integer.compare(this.getPriority(), otherNode.getPriority()) } public int getPriority() { return priority } public Board getBoard() { return board } public int getMoves() { return moves } public SearchNode getPreNode() { return preSearcchNode } } public Solver (Board initial) // find a solution to the initial board (using the A * algorithm) { if (initial == null) throw new java.lang.IllegalArgumentException('The intial Board is null') currentNode = new SearchNode (initial, null) // Initial MinPQ minInitialPQ = new MinPQ() minInitialPQ.insert(currentNode) currentTwinNode = new SearchNode (initial.twin (), null) // two positions after the exchange MinPQ minTwinNode = new MinPQ() minTwinNode.insert(currentTwinNode) boolean flag = false while (flag != true) { // to operate on the original board currentNode = minInitialPQ.delMin () // get the minimum priority value of the tree if (currentNode.getBoard (). isGoal ()) // solvable flag = true else putNeighborsBoardToPQ (currentNode, minInitialPQ) // step into a neighbor tree // adjust the order of the board to operate currentTwinNode = minTwinNode.delMin () // get the smallest tree in the tree priority if (currentTwinNode.getBoard().isGoal()) flag = true else putNeighborsBoardToPQ (currentTwinNode, minTwinNode) // step into a neighbor tree } } // neighbor circumstances inserted into tree private void putNeighborsBoardToPQ(SearchNode currentNode, MinPQ pMinPQ) { Iterable boards = currentNode.getBoard () neighbors (). // all neighbor situation for (Board neighborsBoard : boards) } public boolean isSolvable () // initial board is solvable it? { return currentNode.getBoard().isGoal() } public int moves () // solving the minimum number of movements of the original plate if unsolvable, -1 { if (isSolvable()) return currentNode.getMoves() else return -1 } public Iterable solution () // Solution of the shortest sequence plate null if unsolvable { if (isSolvable() != true) return null stackBoard = new Stack() SearchNode nowNode = currentNode while (nowNode != null) { stackBoard.push(nowNode.getBoard()) nowNode = nowNode.getPreNode() } return stackBoard } public static void main(String[] args) // solve a slider puzzle (given below) { int [][]blocks = new int[3][3] blocks[0][0] = 8 blocks[0][1] = 1 blocks[0][2] = 3 blocks[1][0] = 4 blocks[1][1] = 0 blocks[1][2] = 2 blocks[2][0] = 7 blocks[2][1] = 6 blocks[2][2] = 5 Board board = new Board(blocks) Solver solver = new Solver(board) System.out.println(solver.currentNode.getPreNode() == null) System.out.println(solver.currentNode.getPreNode()) if (solver.isSolvable() != false) { System.out.println('this board is can't resolve') } Iterable bIterable = solver.solution() System.out.println(bIterable.toString()) System.out.println('444') for (Board it : bIterable) { System.out.println(it.toString()) } } }