package?cn.lss;
import?java.util.Stack;

/**?A*搜索類(lèi)
?*?@author?lss
?*
?*/
public?class?AXing{
	final?static?int?MAX?=?Integer.MAX_VALUE;
	int?MaxWeight=MAX;//表示無(wú)窮大
	Stack?stack=new?Stack（）;
	/**A*搜索
	?*?@param?g：圖
	?*?@param?H：?jiǎn)l(fā)式函數(shù)值
	?*?@param?v0：初始值
	?*?@param?end：目標(biāo)值
	?*/
	public?void?A_Search（Graph?gint?H[]int?v0int?end）{
		boolean?flag=true;
		int?x;//表示棧頂元素
		int?vex;//尋找目標(biāo)節(jié)點(diǎn)
		int?MinFMinVex=?v0;//記錄最小的f（n）和對(duì)應(yīng)的節(jié)點(diǎn)
		int[][]GHF=new?int[g.path.length][3];//分別用于存儲(chǔ)g（n）h（n）f（n）
		for（int?i?=0;?i?			GHF[i][0]=0;
			GHF[i][2]=MaxWeight;//對(duì)f（n）初始化1000表示無(wú)窮大
		}
		stack.push（v0）;//v0入棧
		GHF[v0][0]=0;//g（n）
		GHF[v0][1]=H[v0];//h（n）
		GHF[v0][2]=GHF[v0][0]+GHF[v0][1];//f（n）
		g.mark[v0]=1;
		while（flag）{
			MinF=MaxWeight;
			x=（Integer）?stack.peek（）;
			//處理第一個(gè)子節(jié)點(diǎn)
			vex=g.getFirstVex（x）;
			if（vex==end）{//找到目標(biāo)節(jié)點(diǎn)
				stack.push（vex）;
				g.mark[vex]=1;
				break;
			}
			if（vex!=-1）{//子節(jié)點(diǎn)能找到，繼續(xù)
				if（g.mark[vex]==0）{//沒(méi)被訪問(wèn)
					GHF[vex][0]=GHF[x][0]+g.path[x][vex];//節(jié)點(diǎn)vex的g（n）
					GHF[vex][1]=H[vex];//節(jié)點(diǎn)vex的h（n）
					GHF[vex][2]=GHF[vex][0]+GHF[vex][1];
					if（GHF[vex][2]						MinF=GHF[vex][2];
						MinVex=vex;
					}
				}
				//處理剩下的鄰接點(diǎn)（寬度遍歷）
				while（vex!=-1）{
					vex=g.getNextVex（x?vex）;
					if（vex!=-1&&g.mark[vex]==0）{//有鄰節(jié)點(diǎn)
						GHF[vex][0]=GHF[x][0]+g.path[x][vex];//節(jié)點(diǎn)vex的g（n）
						GHF[vex][1]=H[vex];//節(jié)點(diǎn)vex的h（n）
						GHF[vex][2]=GHF[vex][0]+GHF[vex][1];
						if（GHF[vex][2]							MinF=GHF[vex][2];
							MinVex=vex;
						}
					}
					if（vex==-1）{//沒(méi)有鄰接點(diǎn)了，此時(shí)確定最小消耗節(jié)點(diǎn)，并壓棧
						stack.push（MinVex）;
						g.mark[MinVex]=1;
						break;
					}
					if（vex==end）{
						stack.push（vex）;//壓棧目標(biāo)節(jié)點(diǎn)
						g.mark[vex]=1;
						flag=false;
						break;
					}
				}
			}
			else{//沒(méi)有子節(jié)點(diǎn)或者子節(jié)點(diǎn)被訪問(wèn)了，循環(huán)出棧
				while（vex==-1）{
					stack.pop（）;
				}
			}
		}
		new?Main（）.show（g?stack）;
	}
}

?屬性????????????大小?????日期????時(shí)間???名稱(chēng)
-----------?---------??----------?-----??----
?????目錄???????????0??2018-03-20?16:10??Artificial\
?????文件?????????301??2018-03-20?16:10??Artificial\.classpath
?????文件?????????386??2018-03-20?16:10??Artificial\.project
?????目錄???????????0??2018-03-20?16:10??Artificial\.settings\
?????文件?????????598??2018-03-20?16:13??Artificial\.settings\org.eclipse.jdt.core.prefs
?????目錄???????????0??2018-03-25?15:00??Artificial\bin\
?????目錄???????????0??2018-03-25?15:00??Artificial\bin\cn\
?????目錄???????????0??2018-03-25?15:00??Artificial\bin\cn\lss\
?????文件????????1950??2018-03-25?15:00??Artificial\bin\cn\lss\AXing.class
?????文件????????1279??2018-03-25?15:00??Artificial\bin\cn\lss\DFS.class
?????文件????????4081??2018-04-11?19:32??Artificial\bin\cn\lss\Graph.class
?????文件????????1602??2018-03-25?15:00??Artificial\bin\cn\lss\IDS.class
?????文件????????2380??2018-04-11?19:32??Artificial\bin\cn\lss\Main.class
?????文件????????3750??2018-03-25?15:00??Artificial\bin\cn\lss\UCS.class
?????目錄???????????0??2018-03-20?16:14??Artificial\src\
?????目錄???????????0??2018-03-20?16:14??Artificial\src\cn\
?????目錄???????????0??2018-03-20?16:40??Artificial\src\cn\lss\
?????文件????????2297??2018-03-20?16:56??Artificial\src\cn\lss\AXing.java
?????文件?????????989??2018-03-20?16:56??Artificial\src\cn\lss\DFS.java
?????文件????????4776??2018-04-11?19:26??Artificial\src\cn\lss\Graph.java
?????文件????????1580??2018-03-20?16:56??Artificial\src\cn\lss\IDS.java
?????文件????????3293??2018-03-20?16:53??Artificial\src\cn\lss\UCS.java