Java8Puzzle解决方案无限执行
我正在寻找使用A* Algorithm
解决8-puzzle问题的方法。我在互联网上找到了this项目。请查看文件-proj1
和EightPuzzle
。proj1包含程序的入口点(函数main()
),EightPuzzle描述了谜题的特定状态。每个州都是8字谜的一个对象
我觉得逻辑上没有错。但它会为我尝试过的这两个输入永远循环:{8,2,7,5,1,6,3,0,4}
和{3,1,6,8,4,5,7,2,0}
。它们都是有效的输入状态。代码有什么问题
注意
- 为了更好地查看,请将代码复制到记事本++或其他文本中 编辑器(能够识别java源文件) 因为代码中有很多注释李>
- 由于*需要启发式,他们提供了使用
曼哈顿距离和计算
放错地方的瓷砖。并确保执行最佳启发式
首先,他们实施了
PriorityQueue
。这个compareTo()
函数在EightPuzzle
类中实现李> - 可以通过更改
proj1
类的main()
函数中p1d
的值来更改程序的输入李> - 我之所以说上述两个输入存在解决方案,是因为applethere解决了它们。请确保从小程序中的选项中选择8-puzzle。
EDIT1
我给了这个输入{0,5,7,6,8,1,2,4,3}
。它花了大约10 seconds
的时间,并给出了26个动作的结果。但是小程序在0.0001 seconds
和A*
中给出了一个带有24 moves
的结果。
EDIT2
在调试过程中,我注意到随着节点的扩展,新节点在一段时间后都有一个启发式-f_n
as11
或12
。它们似乎从未减少。因此,一段时间之后,{}中的所有状态都有11或12的启发式。因此,没有太多可供选择的节点,可以扩展到哪个节点。因为最小的是11,最高的是12。这正常吗
EDIT3
这是发生无限循环的代码段(在proj1-astar()中)openset是包含未展开节点的优先队列,closedset是包含展开节点的链接列表
while(openset.size()>;0){
EightPuzzle x = openset.peek();
if(x.mapEquals(goal))
{
Stack<EightPuzzle> toDisplay = reconstruct(x);
System.out.println("Printing solution... ");
System.out.println(start.toString());
print(toDisplay);
return;
}
closedset.add(openset.poll());
LinkedList <EightPuzzle> neighbor = x.getChildren();
while(neighbor.size() > 0)
{
EightPuzzle y = neighbor.removeFirst();
if(closedset.contains(y)){
continue;
}
if(!closedset.contains(y)){
openset.add(y);
}
}
}
EDIT4
我已经找到了这个无限循环的原因。看看我的答案。但是执行大约需要25-30秒,这是相当长的时间。A*应该比这快得多。小程序在0.003秒内完成此操作我将奖励改善绩效的奖金强>
对于快速参考,我已粘贴了两个类,没有注释:
八尺
import java.util.*;
public class EightPuzzle implements Comparable <Object> {
int[] puzzle = new int[9];
int h_n= 0;
int hueristic_type = 0;
int g_n = 0;
int f_n = 0;
EightPuzzle parent = null;
public EightPuzzle(int[] p, int h_type, int cost)
{
this.puzzle = p;
this.hueristic_type = h_type;
this.h_n = (h_type == 1) ? h1(p) : h2(p);
this.g_n = cost;
this.f_n = h_n + g_n;
}
public int getF_n()
{
return f_n;
}
public void setParent(EightPuzzle input)
{
this.parent = input;
}
public EightPuzzle getParent()
{
return this.parent;
}
public int inversions()
{
/*
* Definition: For any other configuration besides the goal,
* whenever a tile with a greater number on it precedes a
* tile with a smaller number, the two tiles are said to be inverted
*/
int inversion = 0;
for(int i = 0; i < this.puzzle.length; i++ )
{
for(int j = 0; j < i; j++)
{
if(this.puzzle[i] != 0 && this.puzzle[j] != 0)
{
if(this.puzzle[i] < this.puzzle[j])
inversion++;
}
}
}
return inversion;
}
public int h1(int[] list)
// h1 = the number of misplaced tiles
{
int gn = 0;
for(int i = 0; i < list.length; i++)
{
if(list[i] != i && list[i] != 0)
gn++;
}
return gn;
}
public LinkedList<EightPuzzle> getChildren()
{
LinkedList<EightPuzzle> children = new LinkedList<EightPuzzle>();
int loc = 0;
int temparray[] = new int[this.puzzle.length];
EightPuzzle rightP, upP, downP, leftP;
while(this.puzzle[loc] != 0)
{
loc++;
}
if(loc % 3 == 0){
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc + 1];
temparray[loc + 1] = 0;
rightP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
rightP.setParent(this);
children.add(rightP);
}else if(loc % 3 == 1){
//add one child swaps with right
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc + 1];
temparray[loc + 1] = 0;
rightP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
rightP.setParent(this);
children.add(rightP);
//add one child swaps with left
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc - 1];
temparray[loc - 1] = 0;
leftP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
leftP.setParent(this);
children.add(leftP);
}else if(loc % 3 == 2){
// add one child swaps with left
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc - 1];
temparray[loc - 1] = 0;
leftP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
leftP.setParent(this);
children.add(leftP);
}
if(loc / 3 == 0){
//add one child swaps with lower
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc + 3];
temparray[loc + 3] = 0;
downP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
downP.setParent(this);
children.add(downP);
}else if(loc / 3 == 1 ){
//add one child, swap with upper
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc - 3];
temparray[loc - 3] = 0;
upP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
upP.setParent(this);
children.add(upP);
//add one child, swap with lower
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc + 3];
temparray[loc + 3] = 0;
downP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
downP.setParent(this);
children.add(downP);
}else if (loc / 3 == 2 ){
//add one child, swap with upper
temparray = this.puzzle.clone();
temparray[loc] = temparray[loc - 3];
temparray[loc - 3] = 0;
upP = new EightPuzzle(temparray, this.hueristic_type, this.g_n + 1);
upP.setParent(this);
children.add(upP);
}
return children;
}
public int h2(int[] list)
// h2 = the sum of the distances of the tiles from their goal positions
// for each item find its goal position
// calculate how many positions it needs to move to get into that position
{
int gn = 0;
int row = 0;
int col = 0;
for(int i = 0; i < list.length; i++)
{
if(list[i] != 0)
{
row = list[i] / 3;
col = list[i] % 3;
row = Math.abs(row - (i / 3));
col = Math.abs(col - (i % 3));
gn += row;
gn += col;
}
}
return gn;
}
public String toString()
{
String x = "";
for(int i = 0; i < this.puzzle.length; i++){
x += puzzle[i] + " ";
if((i + 1) % 3 == 0)
x += "\n";
}
return x;
}
public int compareTo(Object input) {
if (this.f_n < ((EightPuzzle) input).getF_n())
return -1;
else if (this.f_n > ((EightPuzzle) input).getF_n())
return 1;
return 0;
}
public boolean equals(EightPuzzle test){
if(this.f_n != test.getF_n())
return false;
for(int i = 0 ; i < this.puzzle.length; i++)
{
if(this.puzzle[i] != test.puzzle[i])
return false;
}
return true;
}
public boolean mapEquals(EightPuzzle test){
for(int i = 0 ; i < this.puzzle.length; i++)
{
if(this.puzzle[i] != test.puzzle[i])
return false;
}
return true;
}
}
proj1
import java.util.*;
public class proj1 {
/**
* @param args
*/
public static void main(String[] args) {
int[] p1d = {1, 4, 2, 3, 0, 5, 6, 7, 8};
int hueristic = 2;
EightPuzzle start = new EightPuzzle(p1d, hueristic, 0);
int[] win = { 0, 1, 2,
3, 4, 5,
6, 7, 8};
EightPuzzle goal = new EightPuzzle(win, hueristic, 0);
astar(start, goal);
}
public static void astar(EightPuzzle start, EightPuzzle goal)
{
if(start.inversions() % 2 == 1)
{
System.out.println("Unsolvable");
return;
}
// function A*(start,goal)
// closedset := the empty set // The set of nodes already evaluated.
LinkedList<EightPuzzle> closedset = new LinkedList<EightPuzzle>();
// openset := set containing the initial node // The set of tentative nodes to be evaluated. priority queue
PriorityQueue<EightPuzzle> openset = new PriorityQueue<EightPuzzle>();
openset.add(start);
while(openset.size() > 0){
// x := the node in openset having the lowest f_score[] value
EightPuzzle x = openset.peek();
// if x = goal
if(x.mapEquals(goal))
{
// return reconstruct_path(came_from, came_from[goal])
Stack<EightPuzzle> toDisplay = reconstruct(x);
System.out.println("Printing solution... ");
System.out.println(start.toString());
print(toDisplay);
return;
}
// remove x from openset
// add x to closedset
closedset.add(openset.poll());
LinkedList <EightPuzzle> neighbor = x.getChildren();
// foreach y in neighbor_nodes(x)
while(neighbor.size() > 0)
{
EightPuzzle y = neighbor.removeFirst();
// if y in closedset
if(closedset.contains(y)){
// continue
continue;
}
// tentative_g_score := g_score[x] + dist_between(x,y)
//
// if y not in openset
if(!closedset.contains(y)){
// add y to openset
openset.add(y);
//
}
//
}
//
}
}
public static void print(Stack<EightPuzzle> x)
{
while(!x.isEmpty())
{
EightPuzzle temp = x.pop();
System.out.println(temp.toString());
}
}
public static Stack<EightPuzzle> reconstruct(EightPuzzle winner)
{
Stack<EightPuzzle> correctOutput = new Stack<EightPuzzle>();
while(winner.getParent() != null)
{
correctOutput.add(winner);
winner = winner.getParent();
}
return correctOutput;
}
}
# 1 楼答案
从另一个论坛获得优化的答案
}和
将
openset.size()
和neightbor.size()
分别更改为
{
neightbor.isEmpty()
size()
遍历整个列表,随着列表变大,它需要越来越多的时间。并更改EightPuzzle x = openset.peek();
调用
EightPuzzle x = openset.poll();
并重用x,而不是调用peek()
和poll()
现在它在^{
# 2 楼答案
发现了问题。这是用于检查closedset中是否存在节点的条件
linkedlist(closedset)通过调用类的equals()执行contains(),在本例中是EightPuzzle。EightPuzzle中的equals函数定义如下
但从未调用此函数,因为如果要重写对象的equals()类,则应使用正确的签名
需要再做一次更改-注释equals()的前两行
我得到了答案。但对于某些输入,代码仍然需要25-30秒。对于*,这是不可能的。小程序在0.003秒内解决了这个难题。如果有人知道如何提高绩效,请告诉我
我将把赏金奖励给那个人
# 3 楼答案
我相信你的代码没有问题,但是,请注意,并非所有的8字谜问题都是可以解决的!所以首先检查{8,2,7,5,1,6,3,0,4}和{3,1,6,8,4,5,7,2,0}是否是可解的8字谜
# 4 楼答案
这里有一个建议。我的计时器为您的示例报告0毫秒。在这里给出的较难的谜题上,需要31个动作才能完成,需要96毫秒
对于闭集,
HashSet
比链表更有意义。它有O(1)时间插入和成员资格测试,其中链接列表需要与列表长度成比例的时间,而列表的长度在不断增长您正在使用额外的数据结构和代码,使您的程序比需要的更复杂、更慢。多思考,少编写代码,学习他人的优秀代码来克服这一问题。我的不是完美的(没有代码是完美的),但这是一个开始
我使用从每个瓷砖的当前位置到其目标的曼哈顿最大距离作为启发。启发式的选择不会影响解决方案中的步骤数,但它将极大地影响运行时间。例如,h=0将生成蛮力宽度优先搜索
请注意,对于A*而言,为了提供最佳解决方案,启发式永远不会超过目标的实际最小步数。如果它这样做了,那么解决方案就是发现可能不是最短的。我不是肯定的“倒转”休里斯特有这个属性