?? abt.java
字號:
import java.util.*;
import java.io.*;
class State//狀態圖的某一個結點
{
//varibles
int numArray[][]=new int[3][3];
int LevelDepth;
Location zerol=new Location();
//
int f_value;//計算的f值的關系
State fatherS;//上層的狀態，記錄路徑
//methods
//計算g函數值
public int g_fuc(State obj)
{
return obj.LevelDepth+1;
}
//計算f函數值
public int f_fuc(State goal)
{
int dif_value=0;
int i,j;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
if(numArray[i][j]!=goal.numArray[i][j])
dif_value=dif_value+1;
return dif_value;
}
public int caculate_f(State obj,State goal)
{
return g_fuc(obj)+f_fuc(goal);
}
public void set_f(int value)
{
f_value=value;
}
//狀態信息打印
public void print()
{
int i,j;
System.out.println();
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
System.out.print(numArray[i][j]+" ");
System.out.println();
}
System.out.println("0的位置是："+zerol.x+" "+zerol.y);
System.out.println("深度是： "+LevelDepth);
System.out.println("f值的關系是：" +f_value);
}
public State(int[][] node,int Depth,State father)//construction method
{
int i,j;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{ if(node[i][j]==0)
{
zerol.x=i;
zerol.y=j;
}
numArray[i][j]=node[i][j];
}
LevelDepth=Depth;
fatherS=father;
}
public boolean LeftMovable()//是否可將空格向上移動
{
if(zerol.y-1>=0)
return true;
else
return false;
}
public boolean RightMovable()//右移
{
if(zerol.y+1<3)
return true;
else
return false;
}
public boolean TopMovable()//上移
{
if(zerol.x-1>=0)
return true;
else
return false;
}
public boolean DownMovable()//下移
{
if(zerol.x+1<3)
return true;
else
return false;
}
public boolean myequal(State obj)//狀態是否重復
{
int i,j;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
if(numArray[i][j]!=obj.numArray[i][j])
return false;
return true;
}
}//end of state
class Location//標志每個格局中0的位置
{
int x;
int y;
public Location()//沒有返回值
{
x = -1;
y = -1;
}
}
class BreadthSearch
{
State startS;
State goalS;
Vector openT = new Vector(10,1);
Vector closeT = new Vector(10,1);
Vector successP =new Vector(10,1);
//methods
public BreadthSearch(State start,State end)//construction method
{
State test_s;
startS=start;
goalS=end;
openT.addElement(startS);//開始結點放在可變數組中
}
public State inVector(Vector v ,State s)
{
int i;
for(i=0;i<v.size();i++)
if(((State)(v.elementAt(i))).myequal(s))
return (State)(v.elementAt(i));
return null;
}
public void expandNode(State s)//擴展一個結點
{
int num[][]=new int[3][3];
int depth,i,j;
int originValue;
Location loc_z=new Location();
State return_open,return_close;
int f_value;
//top expand
if(s.LeftMovable())
{
State s_new;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
num[i][j]=s.numArray[i][j];
loc_z.x=s.zerol.x;
loc_z.y=s.zerol.y-1;
originValue=num[loc_z.x][loc_z.y];
num[loc_z.x][loc_z.y]=0;
num[loc_z.x][loc_z.y+1]=originValue;
depth = s.LevelDepth + 1 ;
s_new=new State(num,depth,s);
//計算其f_value值,并且加入到s_new中
f_value=s_new.caculate_f(s,goalS);
return_open=inVector(openT,s_new);
return_close=inVector(closeT,s_new);
if(return_close==null&&return_open==null)//沒有在open表或是在close表中出現的
{
s_new.set_f(f_value);
openT.addElement(s_new);
}
else if(return_close!=null)
{
if(f_value<return_close.f_value)
{
closeT.removeElement(return_close);
return_close.set_f(f_value);
return_close.fatherS=s;
openT.addElement(return_close);
}
} else if(return_open!=null)
{
if(f_value<return_open.f_value)
{
return_open.set_f(f_value);
return_open.fatherS=s;
}
}
}//end of if top expand
//down expand
if(s.RightMovable())
{
State s_new;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
num[i][j]=s.numArray[i][j];
loc_z.x=s.zerol.x;
loc_z.y=s.zerol.y+1;
originValue=num[loc_z.x][loc_z.y];
num[loc_z.x][loc_z.y]=0;
num[loc_z.x][loc_z.y-1]=originValue;
depth = s.LevelDepth + 1 ;
s_new=new State(num,depth,s);
f_value=s_new.caculate_f(s,goalS);
return_open=inVector(openT,s_new);
return_close=inVector(closeT,s_new);
if(return_close==null&&return_open==null)//沒有在open表或是在close表中出現的
{
s_new.set_f(f_value);
openT.addElement(s_new);
}
else if(return_close!=null)
{
if(f_value<return_close.f_value)
{
closeT.removeElement(return_close);
return_close.set_f(f_value);
return_close.fatherS=s;
openT.addElement(return_close);
}
} else if(return_open!=null)
{
if(f_value<return_open.f_value)
{
return_open.set_f(f_value);
return_open.fatherS=s;
}
}
}//end of if down expand
//left expand
if(s.TopMovable())
{
State s_new;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
num[i][j]=s.numArray[i][j];
loc_z.x=s.zerol.x-1;
loc_z.y=s.zerol.y;
originValue=num[loc_z.x][loc_z.y];
num[loc_z.x][loc_z.y]=0;
num[loc_z.x+1][loc_z.y]=originValue;
depth = s.LevelDepth + 1 ;
s_new=new State(num,depth,s);
f_value=s_new.caculate_f(s,goalS);
return_open=inVector(openT,s_new);
return_close=inVector(closeT,s_new);
if(return_close==null&&return_open==null)//沒有在open表或是在close表中出現的
{
s_new.set_f(f_value);
openT.addElement(s_new);
}
else if(return_close!=null)
{
if(f_value<return_close.f_value)
{
closeT.removeElement(return_close);
return_close.set_f(f_value);
return_close.fatherS=s;
openT.addElement(return_close);
}
} else if(return_open!=null)
{
if(f_value<return_open.f_value)
{
return_open.set_f(f_value);
return_open.fatherS=s;
}
}
}//end of if left expand
//right expand
if(s.DownMovable())
{
State s_new;
for(i=0;i<3;i++)
for(j=0;j<3;j++)
num[i][j]=s.numArray[i][j];
loc_z.x=s.zerol.x+1;
loc_z.y=s.zerol.y;
originValue=num[loc_z.x][loc_z.y];
num[loc_z.x][loc_z.y]=0;
num[loc_z.x-1][loc_z.y]=originValue;
depth = s.LevelDepth + 1 ;
s_new=new State(num,depth,s);
f_value=s_new.caculate_f(s,goalS);
return_open=inVector(openT,s_new);
return_close=inVector(closeT,s_new);
if(return_close==null&&return_open==null)//沒有在open表或是在close表中出現的
{
s_new.set_f(f_value);
openT.addElement(s_new);
}
else if(return_close!=null)
{
if(f_value<return_close.f_value)
{
closeT.removeElement(return_close);
return_close.set_f(f_value);
return_close.fatherS=s;
openT.addElement(return_close);
}
} else if( return_open!=null)
{
if(f_value< return_open.f_value)
{
return_open.set_f(f_value);
return_open.fatherS=s;
}
}
}//end of if right expand
}//end of expanding process
public int getMinInOpen()
{
State temp;
int i;
int i_value=55555,flag=0;
for(i=openT.size()-1;i>=0;i--)
{
temp=(State)(openT.elementAt(i));
if(temp.f_value<i_value)
{
flag = i;
i_value = temp.f_value;
}
}
return flag;
}
public boolean SearchSuccess()
{
State s_first;
State pathState;
int flag_min;
while(!openT.isEmpty())
{
//計算其最小應該提取的元素
flag_min=getMinInOpen();
s_first=(State)(openT.elementAt(flag_min));//取open表中的第一個結點
openT.removeElementAt(flag_min);
closeT.addElement(s_first);
if(s_first.LevelDepth>2000)//人為的界定一個界限防止無解和解路徑很長的情況
return false;
if(s_first.myequal(goalS))//如果是目標結點的話，停止搜索
{
pathState=s_first;
System.out.println("\n結果如下：\n");
while(!pathState.myequal(startS))
{
successP.addElement(pathState);
pathState=pathState.fatherS;
}//end of while
if(pathState!=null)//排除目標狀態和初始狀態相同的情況
successP.addElement(pathState);
return true;
}//end of if ,success 將路徑加入到successPath中
expandNode(s_first);
}//end of while
return false;//not found
}//end of Search
public void getResult()//輸出具體的路徑
{
State s_temp;
int i;
System.out.print("計算過程 :");
for(i=successP.size()-1;i>=0;i--)
{
s_temp = (State)successP.elementAt(i);
s_temp.print();
System.out.println();
System.out.println();
}
} //end of getResult
}
public class ABT
{
public static void ReadFormSI(int[][] a)
{
int i,j;
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
try
{
for(i=0;i<3;i++)
for(j=0;j<3;j++)
{
a[i][j]=(char)br.read()-48;//真是比較笨的方法
}
}//end of try
catch(Exception e)
{
System.out.print("IO 溢出!\n");
}
}//end of ReadFormSI
public static void main(String args[])
{
int input_s[][]=new int[3][3];
int input_d[][]=new int[3][3];
int i,j;
State s;
State e;
System.out.print("請輸入初始狀態：\n");
ReadFormSI(input_s);
System.out.print("請輸入結果狀態：\n");
ReadFormSI(input_d);
s = new State(input_s,0,null);
e= new State(input_d,-1,null);
s.set_f(s.f_fuc(e));
e.set_f(0);
try
{
BreadthSearch testInstance= new BreadthSearch(s,e);
if(testInstance.SearchSuccess())
testInstance.getResult();
else
System.out.print(" 不能達到!\n");
}
catch( Exception em)
{
System.out.println("The ex is "+em);
}
}//end of main
}//end of ABT
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -