Coursera 프 린스 턴 대학 알고리즘 Week 4: 8 퍼 즐 해독
이번 작업 의 난점 은 합 리 적 인 내부 변 수 를 구축 하 는 것 입 니 다. 특히 Solver 류 의 변 수 를 제시 에 따라 한 걸음 한 걸음 풀 면 됩 니 다.
Solver 클래스 의 변 수 는 다음 과 같 습 니 다.
private SearchNode currentNode;
private SearchNode currentTwinNode;
private Stack stackBoard; 그 중에서 stackBoard 는 스 택 저장 소 를 이용 하여 처리 한 결과 집합 입 니 다.이 결과 집 은 마지막 목표 결과 에 따라 순서대로 전구 노드 를 찾 는 것 이기 때문에 스 택 을 이용 하여 결과 집의 순 서 를 바 꿀 수 있다.
SearchNode 는 노드 클래스 를 찾기 위해 서 입 니 다.이 내부 클래스 는 다음 과 같은 요 소 를 포함 합 니 다.
private final Board board; //
private final int moves; //
private SearchNode preSearcchNode = null; //
private final int priority; // currentNode 는 원본 패 널 의 현재 노드 를 찾 습 니 다. currentTwinNode 는 교환 패 널 의 현재 노드 를 찾 습 니 다.수학 적 으로 증명 할 수 있 으 며, 원본 패 널 이 풀 리 지 않 으 면 패 널 을 교환 합 니 다. 해 가 있 을 거 야.그 교환 방법 은 다음 과 같다.
public Board twin() // 。
{
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;
}그 중에서 swap 는 교환 배열 에서 a [21] [j1] 과 a [22] [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) // n*n
{
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 < N; i++) {
for (int j = 0; j < N; j++) {
this.blocks[i][j] = blocks[i][j];
}
}
}
public int dimension() // n
{
return N; //
}
private int getIndex(int i, int j) //
{
return i * N + j + 1;
}
private int getRow(int value) // ，
{
return (value - 1) / N;
}
private int getCol(int value) // ，
{
return (value -1) % N;
}
public int hamming() // hamming = +
{
int wrongNum = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (blocks[i][j] != BLANK && blocks[i][j] != getIndex(i, j)) // blocks[i][j]
wrongNum++;
return wrongNum;
}
public int manhattan() // manhattan = +
{
int wrongNum = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
if (blocks[i][j] != BLANK && blocks[i][j] != getIndex(i, j)) // blocks[i][j]
{
int righti = getRow(blocks[i][j]); // blocks[i][j] i
int rightj = getCol(blocks[i][j]); // blocks[i][j] j
wrongNum = wrongNum + Math.abs(righti - i) + Math.abs(rightj -j);
}
}
return wrongNum;
}
public boolean isGoal() //
{
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (blocks[i][j] != BLANK && blocks[i][j] != getIndex(i, j)) // blocks[i][j]
return false;
return true;
}
private int[][] copy() //
{
int [][]newblocks = new int[N][N];
for (int i1 = 0; i1 < N; i1++)
for (int j1 = 0; j1 < N; j1++)
newblocks[i1][j1] = this.blocks[i1][j1];
return newblocks;
}
private Board swap(int i1, int j1, int i2, int j2) //
{
int [][]newblocks = copy();
int temp = newblocks[i1][j1];
newblocks[i1][j1] = newblocks[i2][j2];
newblocks[i2][j2] = temp;
return new Board(newblocks);
}
public Board twin() // 。
{
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;
}
public boolean equals(Object y) //
{
if (y == null)
return false;
if (y == this)
return true;
if (y.getClass().isInstance(this)) // y this
{
Board boardY = (Board) y;
if (boardY.N != this.N)
return false;
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
if (this.blocks[i][j] != boardY.blocks[i][j])
return false;
}
else // y this
{
return false;
}
return true;
}
public Iterable neighbors() //
{
ArrayList boards = new ArrayList<>();
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (blocks[i][j] == BLANK) //
{
//
if (i > 0)
{
Board upBoard = swap(i, j, i-1, j);
boards.add(upBoard);
}
//
if (i < N-1)
{
Board lowBoard = swap(i, j, i+1, j);
boards.add(lowBoard);
}
//
if (j > 0)
{
Board leftBoard = swap(i, j, i, j-1);
boards.add(leftBoard);
}
//
if (j < N-1)
{
Board rightBoard = swap(i, j, i, j+1);
boards.add(rightBoard);
}
}
}
}
return boards;
}
public String toString() // （ ）
{
StringBuilder sBuilder = new StringBuilder();
sBuilder.append(N + "
");
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
sBuilder.append(blocks[i][j] +"\t");
}
sBuilder.append("
");
}
String string = sBuilder.toString();
return string;
}
public static void main(String[] args) // unit tests (not graded)
{
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);
System.out.println(board.manhattan());
System.out.println(board.toString());
for (Board it : board.neighbors()) {
System.out.println(it.toString());
}
System.out.println(board.twin().toString());
}
}
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; //
private final int moves; //
private SearchNode preSearcchNode = null; //
private final int 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) // （ A* ）
{
if (initial == null)
throw new java.lang.IllegalArgumentException("The intial Board is null");
currentNode = new SearchNode(initial, null); //
MinPQ minInitialPQ = new MinPQ<>();
minInitialPQ.insert(currentNode);
currentTwinNode = new SearchNode(initial.twin(), null); //
MinPQ minTwinNode = new MinPQ<>();
minTwinNode.insert(currentTwinNode);
boolean flag = false;
while (flag != true)
{
//
currentNode = minInitialPQ.delMin(); //
if (currentNode.getBoard().isGoal()) //
flag = true;
else
putNeighborsBoardToPQ(currentNode, minInitialPQ); //
//
currentTwinNode = minTwinNode.delMin(); //
if (currentTwinNode.getBoard().isGoal())
flag = true;
else
putNeighborsBoardToPQ(currentTwinNode, minTwinNode); //
}
}
//
private void putNeighborsBoardToPQ(SearchNode currentNode, MinPQ pMinPQ)
{
Iterable boards = currentNode.getBoard().neighbors(); //
for (Board neighborsBoard : boards) {
if (currentNode.getPreNode() == null ||
neighborsBoard.equals(currentNode.getPreNode().getBoard()) != true) //
pMinPQ.insert(new SearchNode(neighborsBoard, currentNode)); //
}
}
public boolean isSolvable() // ？
{
return currentNode.getBoard().isGoal();
}
public int moves() // ； ， -1
{
if (isSolvable())
return currentNode.getMoves();
else
return -1;
}
public Iterable solution() // ；
{
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());
}
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
JPA + QueryDSL 계층형 댓글, 대댓글 구현(2)이번엔 전편에 이어서 계층형 댓글, 대댓글을 다시 리팩토링해볼 예정이다. 이전 게시글에서는 계층형 댓글, 대댓글을 구현은 되었지만 N+1 문제가 있었다. 이번에는 그 N+1 문제를 해결해 볼 것이다. 위의 로직은 이...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
