实施 A* 解决难题
Implementing A* for solve a puzzle
我正在尝试实施 A* 算法来解决滑动拼图，但我无法使该算法正常工作，过去几天我一直在研究此问题，但老实说我不知道发生了什么现在。我一直在关注维基百科和 "RedBlobGame" 博客中的伪代码，但现在我完全迷路了。
这是 de A* 算法
ArrayList<Node> open = new ArrayList<Node>();
ArrayList<Node> closed = new ArrayList<Node>();
Node goal = new Node(myBoard.getGoalBoard());
Node start = new Node(mb);
start.setH(this.heuristic.calculate(start, goal));
start.setG(0);
start.setDepth(0);
open.add(start);
Node current = null;
while(!open.isEmpty() && !myBoard.stopAlgorithm){
current = getLowest(open);
if(current.isGoal()){
System.out.println("done");
return finalise(current.getBoard(), displaySearch, current.getDepth());
}
open.remove(current);
closed.add(current);
int depth = current.getDepth() + 1;
ArrayList<Node> succesors = current.getSuccessors(depth);
for(Node node: succesors){
node.setH(this.heuristic.calculate(node, goal));
node.setG(current.getG() + 1);
node.setParent(current);
if(!closed.contains(node)){
if(!open.contains(node)){
open.add(node);
}else{
Node openN = open.get(open.indexOf(node));
if(node.getG() < openN.getG()){
openN.setG(node.getG());
openN.setParent(node.getParent());
}
}
}
}
}
System.out.println("path not finded");
return null;
有时他们找到了解决方案，有时他们只是继续寻找并扩展更多可能的状态，我看不出问题在哪里。有什么帮助吗？
这是来自节点的代码class http://pastie.org/10521788
以及启发式算法（在本例中为曼哈顿）http://pastie.org/10521789
这只是一个猜测。我编码 A* 已经有一段时间了，我看不出你是如何实现节点 class 的。我不认为你应该用 node.setG(current.getG()+1) 设置 G 或如果节点已经添加到打开列表，则将父级设置为当前。
尝试：
int depth = current.getDepth() + 1;
ArrayList<Node> succesors = current.getSuccessors(depth);
for (Node node : succesors) {
if (!closed.contains(node) && !open.contains(node)) {
node.setH(this.heuristic.calculate(node, goal));
node.setG(current.getG() + 1);
node.setParent(current);
open.add(node);
}
}
这是一个更完整的版本，似乎对我有用（仅测试了 3 x 3。大部分代码只是设置状态。需要注意的事项：为了提高效率，您不必搜索列表以查看其中是否包含状态。最好使用 HashSet，但这需要始终如一地实施 hashCode() 和 equals()。您的 IDE 可能会生成它们。
public static class BoardState {
int positions[];
private int priority;
/**
* Get the value of priority
*
* @return the value of priority
*/
public int getPriority() {
return priority;
}
/**
* Set the value of priority
*
* @param priority new value of priority
*/
public void setPriority(int priority) {
this.priority = priority;
}
private int distFromGoal;
/**
* Get the value of distFromGoal
*
* @return the value of distFromGoal
*/
public int getDistFromGoal() {
return distFromGoal;
}
/**
* Set the value of distFromGoal
*
* @param distFromGoal new value of distFromGoal
*/
public void setDistFromGoal(int distFromGoal) {
this.distFromGoal = distFromGoal;
}
private BoardState goal;
/**
* Get the value of goal
*
* @return the value of goal
*/
public BoardState getGoal() {
return goal;
}
/**
* Set the value of goal
*
* @param goal new value of goal
*/
public void setGoal(BoardState goal) {
this.goal = goal;
}
private int depth;
/**
* Get the value of depth
*
* @return the value of depth
*/
public int getDepth() {
return depth;
}
/**
* Set the value of depth
*
* @param depth new value of depth
*/
public void setDepth(int depth) {
this.depth = depth;
}
private BoardState prev;
/**
* Get the value of prev
*
* @return the value of prev
*/
public BoardState getPrev() {
return prev;
}
/**
* Set the value of prev
*
* @param prev new value of prev
*/
public void setPrev(BoardState prev) {
this.prev = prev;
}
public BoardState(BoardState other) {
this.positions = new int[9];
System.arraycopy(other.positions, 0, this.positions, 0, positions.length);
this.depth = other.depth + 1;
this.goal = other.goal;
this.prev = other;
}
private BoardState() {
}
public static BoardState goal() {
List<Integer> l = new ArrayList<Integer>();
IntStream.range(0, 9).forEach(i -> l.add(i));
BoardState r = new BoardState();
r.positions = new int[9];
Arrays.setAll(r.positions, i -> l.get(i).intValue());
return r;
}
public static BoardState random() {
List<Integer> l = new ArrayList<Integer>();
IntStream.range(0, 9).forEach(i -> l.add(i));
Collections.shuffle(l);
BoardState r = new BoardState();
r.positions = new int[9];
Arrays.setAll(r.positions, i -> l.get(i).intValue());
return r;
}
@Override
public int hashCode() {
int hash = 7;
hash = 83 * hash + Arrays.hashCode(this.positions);
return hash;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final BoardState other = (BoardState) obj;
if (!Arrays.equals(this.positions, other.positions)) {
return false;
}
return true;
}
int valueAt(int r, int c) {
int pos = r * 3 + c;
for (int i = 0; i < positions.length; i++) {
if (pos == positions[i]) {
return i;
}
}
throw new RuntimeException("invalid board or position");
}
void print() {
System.out.println("depth = " + depth);
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
System.out.print(this.valueAt(r, c) + "\t");
}
System.out.println("");
}
}
int distance(BoardState other) {
int dist = 0;
for (int i = 0; i < positions.length; i++) {
int c0 = this.positions[i] % 3;
int r0 = this.positions[i] / 3;
int c1 = other.positions[i] % 3;
int r1 = other.positions[i] / 3;
dist += Math.abs(r0 - r1) + Math.abs(c0 - c1);
}
return dist;
}
public List<BoardState> moves() {
List<BoardState> newList = new ArrayList<>();
int r0 = this.positions[0] / 3;
int c0 = this.positions[0] % 3;
if (r0 > 0) {
BoardState up = new BoardState(this);
up.positions[0] = (r0 - 1) * 3 + c0;
for (int i = 1; i < 9; i++) {
if (this.positions[i] == up.positions[0]) {
up.positions[i] = this.positions[0];
break;
}
}
newList.add(up);
}
if (r0 < 2) {
BoardState down = new BoardState(this);
down.positions[0] = (r0 + 1) * 3 + c0;
for (int i = 1; i < 9; i++) {
if (this.positions[i] == down.positions[0]) {
down.positions[i] = this.positions[0];
break;
}
}
newList.add(down);
}
if (c0 > 0) {
BoardState left = new BoardState(this);
left.positions[0] = r0 * 3 + (c0 - 1);
for (int i = 1; i < 9; i++) {
if (this.positions[i] == left.positions[0]) {
left.positions[i] = this.positions[0];
break;
}
}
newList.add(left);
}
if (c0 < 2) {
BoardState right = new BoardState(this);
right.positions[0] = r0 * 3 + (c0 + 1);
for (int i = 1; i < 9; i++) {
if (this.positions[i] == right.positions[0]) {
right.positions[i] = this.positions[0];
break;
}
}
newList.add(right);
}
for (BoardState move : newList) {
move.setDistFromGoal(move.distance(goal));
move.setPriority(move.distFromGoal + move.depth);
}
return newList;
}
}
实际A*比较短：
BoardState goal = BoardState.goal();
System.out.println("goal");
goal.print();
BoardState start = BoardState.random();
System.out.println("start");
start.print();
start.setGoal(goal);
start.setDistFromGoal(start.distance(goal));
start.setPriority(start.distFromGoal + start.depth);
PriorityQueue<BoardState> open = new PriorityQueue<>(Comparator.comparing(b -> b.getPriority()));
open.offer(start);
Set<BoardState> set = new HashSet<>();
set.add(start);
int round = 0;
while (!open.isEmpty()) {
BoardState cur = open.poll();
round++;
if (cur.equals(goal)) {
System.out.println("goal found after " + round + " rounds");
System.out.println("printing boards in reverse order");
do {
cur.print();
} while (null != (cur = cur.getPrev()));
break;
}
for (BoardState move : cur.moves()) {
if (!set.contains(move)) {
set.add(move);
open.offer(move);
}
}
}
我正在尝试实施 A* 算法来解决滑动拼图，但我无法使该算法正常工作，过去几天我一直在研究此问题，但老实说我不知道发生了什么现在。我一直在关注维基百科和 "RedBlobGame" 博客中的伪代码，但现在我完全迷路了。
这是 de A* 算法
ArrayList<Node> open = new ArrayList<Node>();
ArrayList<Node> closed = new ArrayList<Node>();
Node goal = new Node(myBoard.getGoalBoard());
Node start = new Node(mb);
start.setH(this.heuristic.calculate(start, goal));
start.setG(0);
start.setDepth(0);
open.add(start);
Node current = null;
while(!open.isEmpty() && !myBoard.stopAlgorithm){
current = getLowest(open);
if(current.isGoal()){
System.out.println("done");
return finalise(current.getBoard(), displaySearch, current.getDepth());
}
open.remove(current);
closed.add(current);
int depth = current.getDepth() + 1;
ArrayList<Node> succesors = current.getSuccessors(depth);
for(Node node: succesors){
node.setH(this.heuristic.calculate(node, goal));
node.setG(current.getG() + 1);
node.setParent(current);
if(!closed.contains(node)){
if(!open.contains(node)){
open.add(node);
}else{
Node openN = open.get(open.indexOf(node));
if(node.getG() < openN.getG()){
openN.setG(node.getG());
openN.setParent(node.getParent());
}
}
}
}
}
System.out.println("path not finded");
return null;
有时他们找到了解决方案，有时他们只是继续寻找并扩展更多可能的状态，我看不出问题在哪里。有什么帮助吗？
这是来自节点的代码class http://pastie.org/10521788 以及启发式算法（在本例中为曼哈顿）http://pastie.org/10521789
这只是一个猜测。我编码 A* 已经有一段时间了，我看不出你是如何实现节点 class 的。我不认为你应该用 node.setG(current.getG()+1) 设置 G 或如果节点已经添加到打开列表，则将父级设置为当前。
尝试：
int depth = current.getDepth() + 1;
ArrayList<Node> succesors = current.getSuccessors(depth);
for (Node node : succesors) {
if (!closed.contains(node) && !open.contains(node)) {
node.setH(this.heuristic.calculate(node, goal));
node.setG(current.getG() + 1);
node.setParent(current);
open.add(node);
}
}
这是一个更完整的版本，似乎对我有用（仅测试了 3 x 3。大部分代码只是设置状态。需要注意的事项：为了提高效率，您不必搜索列表以查看其中是否包含状态。最好使用 HashSet，但这需要始终如一地实施 hashCode() 和 equals()。您的 IDE 可能会生成它们。
public static class BoardState {
int positions[];
private int priority;
/**
* Get the value of priority
*
* @return the value of priority
*/
public int getPriority() {
return priority;
}
/**
* Set the value of priority
*
* @param priority new value of priority
*/
public void setPriority(int priority) {
this.priority = priority;
}
private int distFromGoal;
/**
* Get the value of distFromGoal
*
* @return the value of distFromGoal
*/
public int getDistFromGoal() {
return distFromGoal;
}
/**
* Set the value of distFromGoal
*
* @param distFromGoal new value of distFromGoal
*/
public void setDistFromGoal(int distFromGoal) {
this.distFromGoal = distFromGoal;
}
private BoardState goal;
/**
* Get the value of goal
*
* @return the value of goal
*/
public BoardState getGoal() {
return goal;
}
/**
* Set the value of goal
*
* @param goal new value of goal
*/
public void setGoal(BoardState goal) {
this.goal = goal;
}
private int depth;
/**
* Get the value of depth
*
* @return the value of depth
*/
public int getDepth() {
return depth;
}
/**
* Set the value of depth
*
* @param depth new value of depth
*/
public void setDepth(int depth) {
this.depth = depth;
}
private BoardState prev;
/**
* Get the value of prev
*
* @return the value of prev
*/
public BoardState getPrev() {
return prev;
}
/**
* Set the value of prev
*
* @param prev new value of prev
*/
public void setPrev(BoardState prev) {
this.prev = prev;
}
public BoardState(BoardState other) {
this.positions = new int[9];
System.arraycopy(other.positions, 0, this.positions, 0, positions.length);
this.depth = other.depth + 1;
this.goal = other.goal;
this.prev = other;
}
private BoardState() {
}
public static BoardState goal() {
List<Integer> l = new ArrayList<Integer>();
IntStream.range(0, 9).forEach(i -> l.add(i));
BoardState r = new BoardState();
r.positions = new int[9];
Arrays.setAll(r.positions, i -> l.get(i).intValue());
return r;
}
public static BoardState random() {
List<Integer> l = new ArrayList<Integer>();
IntStream.range(0, 9).forEach(i -> l.add(i));
Collections.shuffle(l);
BoardState r = new BoardState();
r.positions = new int[9];
Arrays.setAll(r.positions, i -> l.get(i).intValue());
return r;
}
@Override
public int hashCode() {
int hash = 7;
hash = 83 * hash + Arrays.hashCode(this.positions);
return hash;
}
@Override
public boolean equals(Object obj) {
if (this == obj) {
return true;
}
if (obj == null) {
return false;
}
if (getClass() != obj.getClass()) {
return false;
}
final BoardState other = (BoardState) obj;
if (!Arrays.equals(this.positions, other.positions)) {
return false;
}
return true;
}
int valueAt(int r, int c) {
int pos = r * 3 + c;
for (int i = 0; i < positions.length; i++) {
if (pos == positions[i]) {
return i;
}
}
throw new RuntimeException("invalid board or position");
}
void print() {
System.out.println("depth = " + depth);
for (int r = 0; r < 3; r++) {
for (int c = 0; c < 3; c++) {
System.out.print(this.valueAt(r, c) + "\t");
}
System.out.println("");
}
}
int distance(BoardState other) {
int dist = 0;
for (int i = 0; i < positions.length; i++) {
int c0 = this.positions[i] % 3;
int r0 = this.positions[i] / 3;
int c1 = other.positions[i] % 3;
int r1 = other.positions[i] / 3;
dist += Math.abs(r0 - r1) + Math.abs(c0 - c1);
}
return dist;
}
public List<BoardState> moves() {
List<BoardState> newList = new ArrayList<>();
int r0 = this.positions[0] / 3;
int c0 = this.positions[0] % 3;
if (r0 > 0) {
BoardState up = new BoardState(this);
up.positions[0] = (r0 - 1) * 3 + c0;
for (int i = 1; i < 9; i++) {
if (this.positions[i] == up.positions[0]) {
up.positions[i] = this.positions[0];
break;
}
}
newList.add(up);
}
if (r0 < 2) {
BoardState down = new BoardState(this);
down.positions[0] = (r0 + 1) * 3 + c0;
for (int i = 1; i < 9; i++) {
if (this.positions[i] == down.positions[0]) {
down.positions[i] = this.positions[0];
break;
}
}
newList.add(down);
}
if (c0 > 0) {
BoardState left = new BoardState(this);
left.positions[0] = r0 * 3 + (c0 - 1);
for (int i = 1; i < 9; i++) {
if (this.positions[i] == left.positions[0]) {
left.positions[i] = this.positions[0];
break;
}
}
newList.add(left);
}
if (c0 < 2) {
BoardState right = new BoardState(this);
right.positions[0] = r0 * 3 + (c0 + 1);
for (int i = 1; i < 9; i++) {
if (this.positions[i] == right.positions[0]) {
right.positions[i] = this.positions[0];
break;
}
}
newList.add(right);
}
for (BoardState move : newList) {
move.setDistFromGoal(move.distance(goal));
move.setPriority(move.distFromGoal + move.depth);
}
return newList;
}
}
实际A*比较短：
BoardState goal = BoardState.goal();
System.out.println("goal");
goal.print();
BoardState start = BoardState.random();
System.out.println("start");
start.print();
start.setGoal(goal);
start.setDistFromGoal(start.distance(goal));
start.setPriority(start.distFromGoal + start.depth);
PriorityQueue<BoardState> open = new PriorityQueue<>(Comparator.comparing(b -> b.getPriority()));
open.offer(start);
Set<BoardState> set = new HashSet<>();
set.add(start);
int round = 0;
while (!open.isEmpty()) {
BoardState cur = open.poll();
round++;
if (cur.equals(goal)) {
System.out.println("goal found after " + round + " rounds");
System.out.println("printing boards in reverse order");
do {
cur.print();
} while (null != (cur = cur.getPrev()));
break;
}
for (BoardState move : cur.moves()) {
if (!set.contains(move)) {
set.add(move);
open.offer(move);
}
}
}