根据启发函数解决八数码问题

启发函数suggestFunc计算所有棋子到目标位置的距离，又称为曼哈顿距离。

import Java.Applet.Applet;
import java.awt.*;
import java.awt.Graphics;
import java.util.Vector;
public class EightNumber extends Applet implements Runnable
{
private class State
{
int[] states = new int[9];
int size;
int steps;
public State(int [] s)
{
int i;
for(i=0;i<9;i )
states[i] = s[i];
}
public boolean equals(State st)
{
int[] s=st.getStates();
int i;
for(i=0;i<9;i )
if(s[i] != states[i])
return false;
return true;
}
public int judgeMove(State st)
{
int[] s=st.getStates();
int i;
for(i=0;i<9;i )
{
if(s[i] != states[i] && s[i]!=0)
return i;
}
return -1;
}
public int[] getStates()
{
return states;
}
public int expandSize()
{
if(states[4] == 0)
size = 4;
else if(states[0]==0 || states[2]==0 || states[6]==0 || states[8]==0)
size = 2;
else
size = 3;
return size;
}
public State[] expandState()
{
State[] st;
int [] ex=new int[9];
int i,j,k;
int m=0,n=0;
int a=0,b=0;
st = new State[size];
for(i=0;i<3;i )
{
for(j=0;j<3;j )
{
k = i*3 j;
ex[k] = states[k];
if(states[k] == 0)
{
m = i;
n = j;
}
}
}
i = 0;
a = m*3 n;
if(m-1>=0)
{
b = (m-1)*3 n;
ex[a] = ex[b];
ex[b] = 0;
st[i] = new State(ex);
ex[b] = ex[a];
ex[a] = 0;
i ;
}
if(m 1<=2)
{
b = (m 1)*3 n;
ex[a] = ex[b];
ex[b] = 0;
st[i] = new State(ex);
ex[b] = ex[a];
ex[a] = 0;
i ;
}
if(n-1>=0)
{
b = m*3 (n-1);
ex[a] = ex[b];
ex[b] = 0;
st[i] = new State(ex);
ex[b] = ex[a];
ex[a] = 0;
i ;
}
if(n 1<=2)
{
b = m*3 (n 1);
ex[a] = ex[b];
ex[b] = 0;
st[i] = new State(ex);
ex[b] = ex[a];
ex[a] = 0;
i ;
}
return st;
}
}
Image[] stateImg = new Image[10];
Image[] moveImg = new Image[10];
Image stepsImg;
Vector vecClose = new Vector();//记录下已经扩展的节点
Vector vecOpen = new Vector();//记录下未扩展的节点
int[] first = {7,2,4,5,0,6,8,3,1};
int[] aim = {0,1,2,3,4,5,6,7,8};
State nowState = null;
State aimState = new State(aim);
int stepX;
int stepY;
int startX;
int startY;
int steps;
int move;
boolean start;
Thread moveTh = null;
public void init()
{
int i;
Integer tmp;
String fileName;
State st = new State(first);
st.steps = 0;

resize(200,300);
startX = 16;
startY = 19;
stepX = 55;
stepY = 55;
steps = 0;
start = false;
move = -1;
for(i=0;i<10;i )
{
tmp = new Integer(i);
fileName = "img/";
fileName = fileName tmp.toString() "_1.gif";
stateImg[i] = getImage(getCodeBase(),fileName);
waitForImage(stateImg[i]);
fileName = "img/";
fileName = fileName tmp.toString() "_2.gif";
moveImg[i] = getImage(getCodeBase(),fileName);
waitForImage(stepsImg);
}
vecOpen.add(st);
fileName = "img/steps.gif";
stepsImg = getImage(getCodeBase(),"img/steps.gif");
waitForImage(stepsImg);

}

public void waitForImage(Image i)
{
MediaTracker tracker = new MediaTracker(this);
try
{
tracker.addImage(i,0);
tracker.waitForID(0);
}
catch(InterruptedException e) {System.err.println("Wait interrupted.");}
}

public void paint(Graphics g)
{
int i,j,k;
int[] state;
Integer tmp;
if(start == false)
return ;
state = nowState.getStates();
g.drawImage(stepsImg,startX 20,startY,this);
tmp = new Integer(steps);
g.drawString(tmp.toString(),startX 80,startY 20);

for(i=0;i<3;i )
{
for(j=0;j<3;j )
{
k = i*3 j;

if(move == k)
{
putNumber(g,state[k],i,j,false);
}
else
{
putNumber(g,state[k],i,j,true);
}
}
}
}
public void update(Graphics g)
{
paint(g);
}
private void putNumber(Graphics g,int number,int i,int j,boolean isState )
{
int x,y;
x = startX j*stepX;
y = startY i*stepY stepY;
if(isState)
{
g.drawImage(stateImg[number],x,y,this);
}
else

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有