#include
#include
#include
#define?SIZE?10000
int?start[3][3]={0};
int?end[3][3]={0};
struct?node?
{
	int?index;//結點序號
????int?p_index;//父結點序號?
????int?matrix[3][3];//?八數碼狀態
????int?h_function;//啟發式函數值
};
node?open[SIZE];?//存放已經生成的未考察的節點
int?openlength=0;
int?openlast=0;//open表最后一個數據的位置
node?closed[SIZE];?//存放已經考察過得節點
int?closedlength=0;
int?closedlast=0;//closed表最后一個數據的位置
int?fail=0;//失敗標記，fail=1則搜索失敗
int?n_index=0;//節點標記序號
int?extend[3][3]={0};
int?n_root=0;
struct?Root{
	node?resultRoot[SIZE];
	int?length;
};
void?init（Root?&r）{
	r.length=0;
};
void?read（）{
	printf（“輸入初始節點：\n“）;
	int?ij;
	for（i=0;i<3;i++）{
		for（j=0;j<3;j++）{
			scanf（“%d“&start[i][j]）;
		}
	}
	printf（“輸入目標節點：\n“）;
	for（i=0;i<3;i++）{
		for（j=0;j<3;j++）{
			scanf（“%d“&end[i][j]）;
		}
	}
	printf（“\n“）;
}
int?isEqual（int?a[][3]int?b[][3]）{//判斷節點是否與目標節點相同
	int?ij;
	for（i=0;i<3;i++）{
		for（j=0;j<3;j++）{
			if（a[i][j]!=b[i][j]）{
				return?0;
			}
		}
	}
	return?1;
}
int?arouse（int?a[][3]）{//用曼哈頓路徑求啟發函數
	int?distance=0;
	int?ij;
	int?locate（int?m[][3]int?n）;
	for（i=0;i<3;i++）{
		for（j=0;j<3;j++）{
			int?location=locate（enda[i][j]）;
			int?i1=location/3;
			int?j1=location%3;
			distance+=（int）fabs（i1-i）+（int）fabs（j1-j）;
		}
	}
	return?distance;
}
void?copy_matrix（int?a[][3]int?b[][3]）{
	int?ij;
	for（i=0;i<3;i++）{
		for（j=0;j<3;j++）{
			a[i][j]=b[i][j];
		}
	}
}
void?inopen（int?a[][3]）{//節點進入open表，同時節點編號置0，配以指向父節點的指針，同時openlength和openlast加一
	copy_matrix（open[openlast].matrixextend）;//將第二個參數矩陣copy到第一個
	open[openlast].index=0;//放入open表中，序號為0
	open[openlast].p_index=n_index;
	open[openlast].h_function=arouse（extend）;
	openlength++;
	openlast++;
}
void?cut（）{//將open[0]放入closed表中
	closed[closedlast].index=n_index;
	closed[closedlast].p_index=open[0].p_index;
	closed[closedlast].h_function=open[0].h_function;
	copy_matrix（closed[closedlast].matrixopen[0].matrix）;
	open[0].index=-1;
	openlength--;
	closedlength++;
	closedlast++;
}
int?locate（int?a[][3]int?b）{//返回0所在位置
	int?ij;
	for（i=0;i<3;i++）{
		for（j=0;j<3;j++）{
			if（a[i][j]==b）
				return?i*3+j;
		}
	}
	return?-1;
}
void?exchange（int?*aint?*b）{
	int?t;
	t=*a;
	*a=*b;
	*b=t;
}
void?copy（node?&anode?&b）{
	a.index=b.index;
	a.p_index=b.p_index;
	a.h_function=b.h_function;
	copy_matrix（a.matrixb.matrix）;
}
void?adjust（）{//調整open表和closed表
	int?i;
	for（i=0;i		if（open[i].index==-1）{
			copy（open[i]open[openlast-1]）;
			openlast--;
		}
	}
	for（i=0;i		if（closed[i].index==-1）{
			copy（closed[i]closed[closedlast]）;
			closedlast--;
		}
	}
}
void?exchangeNode（int?iint?j）{
	node?a;
	copy（aopen[i]）;
	copy（open[i]open[j]）;
	copy（open[j]a）;
}
void?sort（）{//對open表中元素以升序排列
	int?ij;
	for（i=openlength-1;i>0;i--）{
		for（j=0;j			if（open[j].h_function>open[j+1].h_function）{
				exchangeNode（jj+1）;
			}
		}
	}
}
int?seek

?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????文件????????6146??2010-11-28?00:34??八數碼.cpp
?????文件?????????240??2010-11-28?00:36??啟發函數.txt