人工智能8位數(shù)碼難題的問題求解

PAGEPAGE1實驗報告實驗名稱：8位數(shù)碼難題的問題求解實驗?zāi)康暮鸵螅耗康模?.理解和掌握解決實際問題的搜索算法或策略；2.能夠用選定的編程語言實現(xiàn)搜索算法；要求：1.隨機輸入1-8數(shù)字；2.采用所學(xué)過的搜索算法（算法不限，但需要有注釋，采用算法之一，或幾種算法實現(xiàn)）；3.要求輸出算法執(zhí)行的過程結(jié)果；4.按順序輸出1-8數(shù)字；實驗軟硬件要求：網(wǎng)絡(luò)計算機，c++編程環(huán)境實驗內(nèi)容、方法和步驟（可附頁）我們將八數(shù)碼難題分布在3×3方格棋盤上，分別放置了標(biāo)有數(shù)字1,2,3,4,5,6,7,8的八張牌，初始狀態(tài)S0，目標(biāo)狀態(tài)如圖所示，可以使用的操作有:空格上移，空格左移，空格右移，空格下移。我們將是用廣度優(yōu)先搜索算法來解決這一問題。我們先擬定初始數(shù)列為035214876（0表示空位）算法流程圖：初始狀態(tài)3521487612384765結(jié)果數(shù)據(jù)結(jié)構(gòu)：本實驗使用的數(shù)據(jù)結(jié)構(gòu)是隊列，應(yīng)用隊列先進先出的特點來實現(xiàn)對節(jié)點的保存和擴展。首先建立一個隊列，將初始結(jié)點入隊，并設(shè)置隊列頭和尾指，然后取出隊列（頭指針?biāo)福┑慕Y(jié)點進行擴展，從它擴展出子結(jié)點，并將這些結(jié)點按擴展的順序加入隊列，然后判斷擴展出的新結(jié)點與隊列中的結(jié)點是否重復(fù)，如果重復(fù)則，否則記錄其父結(jié)點，并將它加入隊列，更新隊列尾指針，然后判斷擴展出的結(jié)點是否是目標(biāo)結(jié)點，如果是則顯示路徑，程序結(jié)束。否則如果隊列頭的結(jié)點可以擴展，直接返回第二步。否則將隊列頭指針指向下一結(jié)點，再返回第二步，知道擴展出的結(jié)點是目標(biāo)結(jié)點結(jié)束，并顯示路徑。代碼如下：#include<stdio.h>#include<stdlib.h>#include<windows.h>#include<queue>#include<stack>usingnamespacestd;#defineHashTableSize362881#defineNOT!#defineUP0#defineDOWN1#defineLEFT2#defineRIGHT3#defineBitchartypedefstructmaps{Bitdetail[9];intmyindex;//記錄自己節(jié)點在hash表中的位置Bitposition;//記錄空格（0）在序列中的位置}Map,*PMap;Maporg;//初始狀態(tài)intEndIndex;//目標(biāo),上移，下移，左移，右移intconstderection[4]={-3,3,-1,1};//可移動的四個方向intconstFactorial[9]={40320,5040,720,120,24,6,2,1,1};intHashTable[HashTableSize]={0};//hash表,其中記錄的是上一個父節(jié)點對應(yīng)的位置/****八數(shù)碼的輸入（在這里不做任何輸入檢查，均認(rèn)為輸入數(shù)據(jù)是正確的）***/voidinput(){inti,j;intsum,count,index;printf("輸入九個數(shù)：\n");//必須輸入一個0作為空值for(i=0;i<9;i++){scanf("%1d",&org.detail[i]);org.detail[i]||(org.position=i);}for(i=0;i<9;i++)//計算逆序{if(0==org.detail[i])continue;for(j=0;j<i;j++)sum+=(0!=org.detail[j]&&org.detail[j]<org.detail[i]);}for(i=0,index=0;i<9;i++)//計算初始狀態(tài)的hash值{for(j=0,count=0;j<i;j++)count+=org.detail[j]>org.detail[i];index+=Factorial[org.detail[i]]*count;}org.myindex=index+1;EndIndex=sum%2?161328:322561;//目標(biāo)狀態(tài)的hash值return;}/***hash值的計算*Parent:父狀態(tài)的hash值*direct:移動的方向**/inlineintHashValue(Map&Parent,int&direct){inti=Parent.position;intnewindex=Parent.myindex;Bit*p=Parent.detail;switch(direct){caseUP:{newindex-=3*40320;newindex+=(p[i-2]>p[i-3])?(Factorial[p[i-3]]):(-Factorial[p[i-2]]);newindex+=(p[i-1]>p[i-3])?(Factorial[p[i-3]]):(-Factorial[p[i-1]]);break;}caseDOWN:{newindex+=3*40320;newindex-=(p[i+2]>p[i+3])?(Factorial[p[i+3]]):(-Factorial[p[i+2]]);newindex-=(p[i+1]>p[i+3])?(Factorial[p[i+3]]):(-Factorial[p[i+1]]);break;}caseLEFT:returnnewindex-40320;break;caseRIGHT:returnnewindex+40320;break;}returnnewindex;}/****廣度優(yōu)先搜索***/voidBfs(){queue<Map>Queue;Queue.push(org);HashTable[org.myindex]=-1;while(NOTQueue.empty()){Mapnode=Queue.front();Queue.pop();for(intk=0;k<4;k++){Maptmp=node;tmp.position=node.position+derection[k];if(tmp.position<0||tmp.position>8||(k>1&&tmp.position/3!=node.position/3))continue;tmp.myindex=HashValue(node,k);if(0!=HashTable[tmp.myindex])continue;tmp.detail[node.position]=tmp.detail[tmp.position];//移動空格tmp.detail[tmp.position]=0;HashTable[tmp.myindex]=node.myindex;//狀態(tài)記錄到hashtable中if(node.myindex==EndIndex)return;Queue.push(tmp);}}return;}/****通過hash表中記錄的進行查找路徑***/voidFindPath(){intnowindex;intcount=0;intnixu[9],result[9];inti,j,k;stack<int>Stack;Stack.push(EndIndex);nowindex=EndIndex;while(-1!=HashTable[nowindex]){Stack.push(HashTable[nowindex]);nowindex=HashTable[nowindex];}printf("共需：%d步\n",Stack.size()-1);getchar();while(NOTStack.empty()){nowindex=Stack.top()-1;Stack.pop();for(i=0;i<9;i++)//計算出逆序{nixu[i]=nowindex/Factorial[i];nowindex%=Factorial[i];}memset(result,-1,9*sizeof(int));for(i=0;i<9;i++)//根據(jù)逆序計算排列{for(j=0,k=nixu[i];j<9;j++){if(result[j]==-1)k--;if(k<0)break;}result[j]=i;}for(i=0;i<9;i++){printf("%3d",result[i]);if(2==i%3)printf("\n");}if(0!=Stack.size()){printf("\n↓第%d步\n",++count);getchar();}}printf("\nFinish!\n");return;}intmain(){inp