Привет, я использую java для создания программы Solver, которая использует помощь HeapMinPQ и узлов для решения любой доски на основе формата «8 головоломок». Я уже создал тип данных «Доска», который использует двумерный массив для учета тайлов (а «0» — это пустое место). В моих узлах поиска у меня есть целое число с приоритетом, которое учитывает значения «Манхэттен» (и я уверен, что этот метод работает нормально). Проблема в том, что я пытался добиться прогресса, и хотя моя программа компилируется, она просто зависает без вывода соответствующего результата (минимальное количество требуемых ходов). Я предполагаю, что мне трудно обдумать все это, но это мой код, который нужно решить до сих пор...
import java.util.Comparator;
public class Solver {
private SearchNode result;
// Helper search node class.
private class SearchNode {
SearchNode prev;
Board value;
int moves = 0;
int priority;
public SearchNode(Board board, SearchNode previous) {
super();
this.value = board;
prev = previous;
if (null != previous) {
this.moves = previous.moves + 1;
} else {
this.moves = 0;
}
// priority = this.value.hamming() + moves;
priority = this.value.manhattan() + moves;
}
}
/**
* Finds a solution to the initial board (using the A* algorithm).
* @param initial initial board.
*/
public Solver(Board initial) {
SearchNode root = new SearchNode(initial, null);
HeapMinPQ<SearchNode> heap = new HeapMinPQ<SearchNode>(new ManhattanOrder());
heap.insert(root);
Board twin = initial.twin();
SearchNode twinRoot = new SearchNode(twin, null);
HeapMinPQ<SearchNode> twinHeap = new HeapMinPQ<SearchNode>(new ManhattanOrder());
twinHeap.insert(twinRoot);
solve(heap, twinHeap);
}
private void solve(HeapMinPQ<SearchNode> heap, HeapMinPQ<SearchNode> twinHeap) {
while (!heap.isEmpty() && !twinHeap.isEmpty()) {
if (null != perform(heap)) {
return;
}
if (null != perform(twinHeap)) {
result = null;
return;
}
}
}
private SearchNode perform(HeapMinPQ<SearchNode> heap) {
SearchNode n = heap.delMin();
if (n.value.isGoal()) {
result = n;
return result;
}
for (Board board : n.value.neighbors()) {
SearchNode x = new SearchNode(board, n);
if (null != n.prev && n.prev.value.equals(board)) {
// don't add neighbors that are same as previous board
continue;
}
heap.insert(x);
}
return null;
}
А это мой метод "близнец" из типа данных "доска".
public Board twin(){
int dim = this.length;
int[][] copy = this.tiles;
if (this.length <= 1)
return new Board(copy);
// Find zero so that we don't exchange with the blank
// This looks like a O(dim^2) algorithm, but on average it should finish
// in O(1).
int row = 0;
int col = 0;
int value = 0;
int lastValue = tiles[0][0];
zerosearch: for (row = 0; row < dim; row++) {
for (col = 0; col < dim; col++) {
value = tiles[row][col];
// Check col>0 because swap must occur on same row
if (value != 0 && lastValue != 0 && col > 0)
break zerosearch;
lastValue = value;
}
}
copy[row][col] = lastValue;
copy[row][col - 1] = value;
return new Board(copy);
}
Должен быть глубокий просчет, который я здесь делаю, и я почти уверен, что он начинается с решения (куча, двойная куча); метод в общедоступном методе Solver(Board initial). Любая помощь будет принята с благодарностью.
