資料結構課程實踐系列

題目1：學生成績檔案管理系統（實驗準備）

題目2：隱式圖的搜索問題（A*演算法解決八數碼）

題目3：文本檔案單詞的檢索與計數（實驗準備）

宣告

題目要求

看過這次實驗要求之后

總結：利用A*來解決八數碼問題，狀態很好找，每次移動空格就會形成一種新的狀態，

何為八數碼？

八數碼游戲包括一個3X3的棋盤，棋盤上擺放著8個數字的棋子，留下一個空位，與空位相鄰的棋子可以滑動到空位中，游戲的目的是要達到一個特定的目標狀態，標注的形式化如下（舉例）：

（初始狀態）

（目標狀態）

狀態如何表示

1. 每個狀態都用3*3的陣串列示，但是BFS中需要入隊出隊，比較麻煩而且空間占用較大
2. 狀態壓縮，采用一個整數保存狀態的數字序列，例如狀態1表示為203184765,狀態2表示為123804765

所需知識

優先佇列BFS演算法，因為A*演算法就是帶有估價函式的優先佇列BFS，

匯出所需知識

優先佇列BFS演算法缺陷

該演算法維護了一個優先佇列（二叉堆），不斷從堆中取出“當前代價最小”的狀態（堆頂）去進行擴展，但是它得到只是初態到該狀態的最小代價（并沒有去考慮從該狀態出發到目標狀態的情況）

舉例說明：
如果給定一個“目標狀態”，需要求出從初態到目標狀態的最小代價，優先佇列BFS顯然不行，因為一個狀態的當前代價最小，只能說明從起始狀態到該狀態的代價很小，而在未來的探索中，從該狀態到目標狀態可能會花費很大的代價；另外一些狀態雖然當前代價略大，但是未來到目標狀態的代價可能會很小，于是從起始狀態到目標狀態的總代價反而更優，

A*搜索演算法

于是，我們為了解決上面的問題：可以對未來可能產生的代碼進行預估，詳細地講，我們去設計一個**“估價函式”**，以任意狀態為輸入，計算出從該狀態到目標狀態所需代價的估計值，在搜索之中，仍然維護了一個堆，不斷從堆中取出“當前代價+未來估價”最小的狀態來進行擴展，

為了保證第一次從堆中取出目標狀態時得到的就是最優解，我們設計的估價函式需要滿足一個基本準則：

設當前狀態state到目標狀態所需代價的估計值為f（state）；設在未來的探索中，實際求出的從當前狀態state到目標狀態的最小代價為g（state）
對于任意的state，應該有f（state）<=g（state）

也就是說，估價函式的估值不能大于未來實際代價，估價比實際代價更優，估價函式f(n)=g(n)+h(n)

總結：

這種帶有估價函式的優先佇列BFS就成為A* 演算法，只要保證對于任意狀態state，都有f（state）<=g（state），A* 演算法就一定能在目標狀態第一次從堆中被取出時得到最優解，并且在搜索程序中每個狀態只需要擴展一次（之后再被取出就可以直接忽略 ），估價f（state）越準確，越接近g（state），A*演算法的效率越高，如果估價始終為0，就等于普通的優先佇列BFS，

實際操作

搜索程序描述

A演算法又稱為啟發式搜索演算法，對啟發式搜索演算法，又可根據搜索程序中選擇擴展節點的范圍，將其分為全域擇優搜索演算法和區域擇優搜索演算法，

在全域擇優搜索中，每當需要擴展節點時，總是從 Open 表的所有節點中選擇一個估價函式值最小的節點進行擴展，其搜索程序可能描述如下：

1. 把初始節點 S0 放入 Open 表中， f(S0)=g(S0)+h(S0) ；
2. 如果 Open 表為空，則問題無解，失敗退出；
3. 把 Open 表的第一個節點取出放入 Closed 表，并記該節點為 n ；
4. 考察節點 n 是否為目標節點，若是，則找到了問題的解，成功退出；
5. 若節點 n 不可擴展，則轉到第 (2) 步；
6. 擴展節點 n ，生成子節點 ni ( i =1,2, …… ) ，計算每一個子節點的估價值 f( ni ) ( i =1,2, …… ) ，并為每一個子節點設定指向父節點的指標，然后將這些子節點放入 Open 表中；
7. 根據各節點的估價函式值，對 Open 表中的全部節點按從小到大的順序重新進行排序；
8. 轉第 (2) 步，

這里采用的啟發式策略為：f(n) = g(n) + h(n)，其中g(n)為從初始節點到當前節點的步數(層數)，h(n)為 當前節點 “不在位 ”的方塊數（也就是說不在位的方塊數越少，那么臨目標狀態越近）例如下圖中的h(n)=5，有的講解的是不包含空格，我這里是包含了的，經測驗只要前后標準一致，包不包含空格都一樣，
g(n)為已經消耗的實際代價，即已經走了的步數，
h(n)為預測路徑，即還有幾個數字待走，

h(n)=5

啟發式策略作業工程：紅圈數字表示擴展順序

代碼實作

Map+BFS+A*

#include<cstdio>
#include<queue>
#include<map>
using namespace std;
char arr[10], brr[10] = "123804765";
struct node {
	int num, step, cost, zeroPos;
	bool operator<(const node& a)const {
		return cost > a.cost;
	}
	node(int n, int s, int p) {
		num = n, step = s, zeroPos = p;
		setCost();
	}
	void setCost() {
		char a[10];
		int c = 0;
		sprintf(a, "%09d", num);
		for (int i = 0; i < 9; i++)
			if (a[i] != brr[i])
				c++;
		cost = c + step;
	}
};
int des = 123804765;
int changeId[9][4] = { {-1,-1,3,1},{-1,0,4,2},{-1,1,5,-1},
					{0,-1,6,4},{1,3,7,5},{2,4,8,-1},
					{3,-1,-1,7},{4,6,-1,8},{5,7,-1,-1} };
map<int, bool>mymap;
priority_queue<node> que;//優先級佇列 
void swap(char* ch, int a, int b) { char c = ch[a]; ch[a] = ch[b]; ch[b] = c; }
int bfsHash(int start, int zeroPos) {
	char temp[10];
	node tempN(start, 0, zeroPos);//創建一個節點 
	que.push(tempN);//壓入優先級佇列 
	mymap[start] = 1;//標記開始節點被訪問過 
	while (!que.empty()) {
		tempN = que.top();
		que.pop();//彈出一個節點 
		sprintf(temp, "%09d", tempN.num);
		int pos = tempN.zeroPos, k;
		for (int i = 0; i < 4; i++) {
			if (changeId[pos][i] != -1) {
				swap(temp, pos, changeId[pos][i]);
				sscanf(temp, "%d", &k);
				if (k == des)return tempN.step + 1;
				if (mymap.count(k) == 0) {
					node tempM(k, tempN.step + 1, changeId[pos][i]);
					que.push(tempM);//創建一個新節點并壓入佇列 
					mymap[k] = 1;
				}
				swap(temp, pos, changeId[pos][i]);
			}
		}
	}
}
int main() {
	int n, k, b;
	scanf("%s", arr);
	for (k = 0; k < 9; k++)
		if (arr[k] == '0')break;
	sscanf(arr, "%d", &n);
	b = bfsHash(n, k);
	printf("%d步即可變換完成", b);
	return 0;
}

所得結果跟我們上圖分析結果一樣，

Hash+BFS+A*

#include<cstdio>
#include<queue>
using namespace std;
char arr[10],brr[10]="123804765";
struct node{
	int num,step,cost,zeroPos;
	bool operator<(const node &a)const{
		return cost>a.cost;
	}
	node(int n,int s,int p){
		num=n,step=s,zeroPos=p;
		setCost();
	}
	void setCost(){
		char a[10];
		int c=0;
		sprintf(a,"%09d",num);
		for(int i=0;i<9;i++)
			if(a[i]!=brr[i])
				c++;
		cost=c+step;
	}
};
int changeId[9][4]={{-1,-1,3,1},{-1,0,4,2},{-1,1,5,-1},
					{0,-1,6,4},{1,3,7,5},{2,4,8,-1},
					{3,-1,-1,7},{4,6,-1,8},{5,7,-1,-1}};
const int M=2E+6,N=1000003;//362897;
int hashTable[M];//hashtable中key為hash值，value為被hash的值 
int Next[M],des=123804765;//next表示如果在某個位置沖突，則沖突位置存到hashtable[next[i]] 
priority_queue<node> que;//優先級佇列 
int Hash(int n){
	return n%N; 
}
bool tryInsert(int n){
	int hashValue=Hash(n);
	while(Next[hashValue]){//如果被hash出來的值得next不為0則向下查找 
		if(hashTable[hashValue]==n)//如果發現已經在hashtable中則回傳false 
			return false; 
		hashValue=Next[hashValue];
	}//回圈結束hashValue指向最后一個hash值相同的節點 
	if(hashTable[hashValue]==n)//再判斷一遍 
		return false; 
	int j=N-1;//在N后面找空余空間，避免占用其他hash值得空間造成沖突 
	while(hashTable[++j]);//向后找一個沒用到的空間 
	Next[hashValue]=j;
	hashTable[j]=n;
	return true; 
}
void swap(char* ch,int a,int b){char c=ch[a];ch[a]=ch[b];ch[b]=c;}
 
int bfsHash(int start,int zeroPos){
	char temp[10];
	node tempN(start,0,zeroPos); 
	que.push(tempN);
	while(!que.empty()){
		tempN=que.top();
		que.pop();
		sprintf(temp,"%09d",tempN.num);
		int pos=tempN.zeroPos,k;
		for(int i=0;i<4;i++){
			if(changeId[pos][i]!=-1){
				swap(temp,pos,changeId[pos][i]);
				sscanf(temp,"%d",&k);
				if(k==des)return tempN.step+1;
				if(tryInsert(k)){//插入新狀態成功，則說明新狀態沒有被訪問過 
					node tempM(k,tempN.step+1,changeId[pos][i]);
					que.push(tempM);
				}
				swap(temp,pos,changeId[pos][i]);
			}
		}
	}
}
int main(){
	int n,k,b=0;
	scanf("%s",arr);
	for(k=0;k<9;k++)
		if(arr[k]=='0')break;
	sscanf(arr,"%d",&n);
	if(n!=des)
		b=bfsHash(n,k);
	printf("%d步即可變換完成",b);	
	return 0;
}

GAMEOVER