前一陣子上人工智能實驗課做過八數(shù)碼的題目，在博客中放上自己的實驗過程
代碼地址
實驗環(huán)境
本次實驗的編程語言為C++,運行環(huán)境為Windows10,使用的集成開發(fā)環(huán)境為VS2015
八數(shù)碼游戲問題簡介
九宮排字問題（又稱八數(shù)碼問題）是人工智能當中有名的難題之一。問題是在 3×3方格盤上，放有八個數(shù)碼，剩下第九個為空，每一空格其上下左右的數(shù)碼可移至空格。
問題給定初始位置和目標位置，要求通過一系列的數(shù)碼移動，將初始位置轉化為目標位置。
求解思路
對于八數(shù)碼問題的求解，由于每次只將空格點與上、下、左、右四個位置的值進行交換，所以每個狀態(tài)只需要對這四個點進行判斷。</br>
首先判斷與空格相鄰的點是否存在:</br>
若存在，則根據(jù)啟發(fā)式算法的思路f(x) = g(x) + h(x)</br>
定義g(x)為某一數(shù)值從當前狀態(tài)的坐標（與空格點相鄰）直接到終止狀態(tài)該數(shù)值坐標的移動距離，如圖紅線。</br>
注：g(x)=0表示當前狀態(tài)的點與終止狀態(tài)對應點的值不變，即該值已經到達終止狀態(tài)的目標點。</br>
定義h(x)為某一數(shù)值經過空格點后到達終止狀態(tài)該數(shù)值坐標的移動距離，如圖黑線。</br>
定義f(x) = g(x) – h(x) 若 f(x) < 0 則代表當前狀態(tài)該數(shù)值經過空格點后移動到終點坐標的距離要比直接到達終點坐標的距離要多，這時不對該點進行操作，由于移動的方向只能是上、下、左、右，故不存在f(x) = 0（g(x) = h(x)）的情況，否則（f(x) > 0）該點與空格點進行交換，表明通過該相鄰點空格點的移動后距離終止狀態(tài)該值的坐標更近。</br>
例如：某一時刻狀態(tài)如左圖所示，終止位置如右圖所示，圓圈表示空格相鄰點與終止位置相鄰點所處的位置，下面用圖例來表明解決八數(shù)碼問題的具體思路，對于中間某一狀態(tài)的分析來解決下一次往哪一點移動。
對于中間狀態(tài)左點坐標為（1,0），終止狀態(tài)對應值坐標為（0,0），需移動1-0+0=1步到達，g(x) = 1，而從空格點（1,1）到達（0,0）需移動|1-0|+|1-0|=2步，h(x) = 2，g(x) < h(x)，f(x) = -1<0不滿足條件，表明左點 不與 空格點進行交換移動。（|a-b|表示a-b的絕對值）
對于中間狀態(tài)上點坐標為（0,1），終止狀態(tài)對應值坐標為（1,0），需移動|0-1|+|1-0|=2步到達，g(x) = 2，而從空格點（1,1）到達（1,0）需移動|1-1|+|1-0|=1步，h(x) = 1，f(x) =1> 0，滿足條件，表面上點 可以 與空格點進行交換移動。
對于中間狀態(tài)右點坐標為（1,2），終止狀態(tài)對應值坐標為（1,2），需移動|1-1|+|2-2|=0步到達，g(x) = 0，而從空格點（1,1）到達（1,2）需移動|1-1|+|1-2|=1步，h(x) = 1，f(x) =-1< 0，不滿足條件，表面右點 不與 空格點進行交換移動。
對于中間狀態(tài)下點坐標為（2,1），終止狀態(tài)對應值坐標為（2,1），需移動|2-2|+|1-1|=0步到達，g(x) = 0，而從空格點（1,1）到達（2,1）需移動|1-2|+|1-1|=1步，h(x) = 1，f(x) =-1< 0，不滿足條件，表面下點 不與 空格點進行交換移動。</br>
綜上所述，空格點下一次要移動的位置是（0,1）
數(shù)據(jù)結構的設計
本次實驗采用面向對象的思想，將八數(shù)碼問題封裝成一個模板類(實際上整形的類即可)， 類視圖如下：
</br>
該類的成員變量為：</br>
current_point 當前點的坐標；</br>
final_state 終止狀態(tài)；</br>
initial_state 初始狀態(tài)；</br>
move_point 待移動點坐標；</br>
state 中間狀態(tài)；</br>
成員函數(shù)為：</br>
void solve(); 整合其他函數(shù)，解決八數(shù)碼問題的主函數(shù)；</br>
bool have_answer();判斷是否有解；</br>
bool is_equal();判斷中間狀態(tài)和終止狀態(tài)是否相等；</br>
void exchange_point(int time); 輸入為第幾輪數(shù)，待移動點與當前點進行交換；</br>
void get_next_point();得到待移動點坐標；</br>
int is_close(int );輸入為進行判斷的坐標，對輸入坐標和當前坐標的代價進行判定，f(x)<0，則返回-1，若f(x)>0，則返回h(x)。</br>
思路及代碼
首先重載一個含參的構造函數(shù)</br>
template<typename T>
Eight_figure<T>::Eight_figure(vector<vector<T>> init, vector<vector<T>> fin) {
initial_state = init;
state = init;
final_state = fin;
for (int i = 0; i < 3; i++){
for (int j = 0; j < 3; j++) {
if (initial_state[i][j] == 0)
current_point = i*3 + j;
}
}
cout << "初始狀態(tài)為：" << initial_state << endl;
cout << "終止狀態(tài)為：" << final_state << endl;
cout << "當前空點的坐標為" << "(" << current_point / 3 << "," << current_point % 3 << ")" << endl;
}
輸入為初始狀態(tài)和終止狀態(tài)，在main函數(shù)中定義兩個數(shù)組后，調用構造函數(shù)進行輸入；</br>
接著把解決八數(shù)碼問題的主要步驟表示出來，在solve()函數(shù)中，</br>
首先判斷問題是否有解，若無解，結束程序，</br>
若有解，</br>
1.判斷初始狀態(tài)與終止狀態(tài)是否相等；</br>
2.得到待移動點的坐標；</br>
3.將空格與待移動點進行交換；</br>
4.返回步驟1</br>
同時對計算時間進行計時。</br>
solve核心代碼如下：</br>
template<typename T>
void Eight_figure<T>::solve() {
if (!have_answer()) cout << "該變換無解" << endl;
else {
int time = 0;
clock_t start, finish;
double totaltime;
start = clock();
while (!is_equal()) {
get_next_point();
exchange_point(++time);
}
finish = clock();
totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
cout << "變換結束 用時" << totaltime << "秒！" << endl;
}
}
在have_answer()中，對初始狀態(tài)和終止狀態(tài)數(shù)組分別求解其逆序數(shù)，若前面存在大于該位的值，則計數(shù)值+1，對空格位置不進行計算。
int count1 = 0,count2 = 0;
for (int i = 0; i < 9; i++)//求得初始狀態(tài)逆序數(shù) 用一維數(shù)0-8表示二維坐標 ( i/3,i%3 )
{
if (initial_state[i / 3][i % 3] == 0) continue;
for (int j = 0; j < i; j++) {
if (initial_state[j / 3][j % 3]> initial_state[i / 3][i % 3]) count1++;
}
}
for (int i = 0; i < 9; i++)//求得終止狀態(tài)逆序數(shù)
{
if (final_state[i / 3][i % 3] == 0) continue;
for (int j = 0; j < i; j++) {
if (final_state[j / 3][j % 3]> final_state[i / 3][i % 3]) count2++;
}
}
求得后對兩個逆序數(shù)進行奇偶性的判斷，相同返回true，不同返回false
return count1 % 2 == count2 % 2;
在is_equal()中，判斷中間狀態(tài)state和終止狀態(tài)final_state是否相等，判斷方法為對應位判斷，只要有一位不同，則返回false,否則返回true
bool Eight_figure<T>::is_equal() {
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++) {
if (state[i][j] != final_state[i][j])
return false;
}
}
return true;
}
在is_close(int )中,輸入為進行判斷的坐標,該坐標是與空格點相鄰的一個坐標，首先找到輸入坐標上的值在終止狀態(tài)下的位置，然后分別計算輸入坐標和當前坐標到終止狀態(tài)該值位置所需移動的步數(shù)，記為before和after（即g(x)和h(x)），若變換前所需步數(shù)少，則返回-1，代表不能進行交換，若變換后所需步數(shù)少，則返回變換后的步數(shù)。
template<typename T>
int Eight_figure<T>::is_close(int side) {
int after = 0, before = 0;
for (int i = 0; i < 9; i++)
{
if (final_state[i / 3][i % 3] == state[side / 3][side % 3])
{
before = abs(side / 3 - i / 3) + abs(side % 3 - i % 3);
after = abs(current_point / 3 - i / 3) + abs(current_point % 3 - i % 3);
if (after > before) return -1;
else
return after;
}
}
實現(xiàn)完is_close() 之后就可以實現(xiàn)get_next_point()了，這個函數(shù)依次計算上左右下四個位置的代價，若某一相鄰點存在，調用is_close()對該點計算變換前后所需的步數(shù),若步數(shù)為-1，則對下一個相鄰點做判斷，若步數(shù)為0，說明該空格點坐標在終止位置的值就是該相鄰點位置的值，此時待移動點記為該相鄰點，退出函數(shù)，否則記錄該相鄰點為待移動點后繼續(xù)對其他相鄰點做判斷。
template<typename T>
void Eight_figure<T>::get_next_point() {
int up = current_point - 3, left = current_point - 1, right = current_point + 1, down = current_point + 3,step =0;
if (up >= 0) //判斷上點上否存在
{
step = is_close(up);//取得若與上點進行交換 交換后的上點的數(shù)值到達終止狀態(tài)目標點的步數(shù)
if (step != -1)//若交換后需要移動的步數(shù)變少
{
move_point = up;//移動點改為上點
if(step == 0)//若空點當前位置的值恰好是上點的值則返回上點
return;
}
}
if ((left+1) % 3 != 0) //對于左點
{
step = is_close(left);
if (step != -1){
move_point = left;
if(step == 0)
return;
}
}
if (right%3!= 0) //對于右點
{
step = is_close(right);
if (step != -1)
{
move_point = right;
if (step == 0)
return;
}
}
if (down <= 8) //對于下點
{ step = is_close(down);
if (step != -1)
{
move_point = down;
if (step == 0)
return;
}
}
}
在得到待移動點后，在中間狀態(tài)的數(shù)組中將帶移動狀態(tài)與當前狀態(tài)位置上的值交換，并將當前位置的坐標置為待移動點坐標，待移動點坐標變?yōu)?1，exchange_point(time)函數(shù)如下，輸入為第幾輪的輪數(shù)。
template<typename T>
void Eight_figure<T>::solve() {
if (!have_answer()) cout << "該變換無解" << endl;
else {
int time = 0;
clock_t start, finish;
double totaltime;
start = clock();
while (!is_equal()) {
get_next_point();
exchange_point(time);
time++;
}
finish = clock();
totaltime = (double)(finish - start) / CLOCKS_PER_SEC;
cout << "變換結束 用時" << totaltime << "秒！" << endl;
}
}
最后在main函數(shù)中，定義一個該模板類的對象，將初始狀態(tài)和終止狀態(tài)作為構造函數(shù)的輸入，調用該類的solve()函數(shù)即可。
int main(){
vector<vector<int>>init = { { 6,7,8 },{ 3,4,5 },{ 1,0,2 } };
vector<vector<int>>fin={ { 3,6,7 },{ 1,4,8 },{ 0,2,5 } };
Eight_figure<int>ef(init, fin);
ef.solve();
return 0;
}
實驗結果
測試1：初始狀態(tài)和終止狀態(tài)如下圖所示：</br>
</br>
經過5輪變換即可完成從初始狀態(tài)到終止狀態(tài)的變換，分別是：</br>
</br>
測試2：初始狀態(tài)和終止狀態(tài)如下圖所示：該終止狀態(tài)是由初始狀態(tài)的外圈進行一次順時針旋轉形成的。</br>
</br>
經過7輪變換即可完成從初始狀態(tài)到終止狀態(tài)的變換，分別是：</br>
