人工智能技術課程設計報告

人工智能技術課程設計報告學號：姓名：課程設計題目：貨郎擔（旅行商）問題：設有n個城市，城市之間均有道路，一個旅行商從某城市出發(fā)，經過其余n-1個城市一次且僅一次，最后回到出發(fā)的城市，他如何走才能使他所走的路程最短？用A*算法實現，語言不限算法實現： 本程序使用A*算法實現 A*算法，作為啟發(fā)式算法中很重要的一種，被廣泛應用在最優(yōu)路徑求解和一些策略設計的問題中。而A*算法最為核心的部分，就在于它的一個估值函數的設計上：f(n)=g(n)+h(n) 其中f(n)是每個可能試探點的估值，它有兩部分組成：一部分為g(n)，它表示從起始搜索點到當前點的代價（通常用某結點在搜索樹中的深度來表示）。另一部分，即h(n)，它表示啟發(fā)式搜索中最為重要的一部分，即當前結點到目標結點的估值。一種具有f(n)=g(n)+h(n)策略的啟發(fā)式算法能成為A*算法的充分條件是：1)

搜索樹上存在著從起始點到終了點的最優(yōu)路徑。2)

問題域是有限的。 3） 所有結點的子結點的搜索代價值>0。 4） h(n)=<h*(n)（h*(n)為實際問題的代價值）。 在旅行商問題中 節(jié)點（A...XY）的代價=起始城市到X城的代價+X城到Y城的代價其中的代價可以是距離，費用或者時間等 節(jié)點（A…XY）的啟發(fā)值=（城市總數-已訪問的城市數-1）*min{所有兩城之間的代價} 在程序中的實現： p->gvalue=p_min->gvalue+relation[p_min->num-1][i]; p->hvalue=min*(number-p->level-1); p->fvalue=p->gvalue+p->hvalue;其中gvalue:g(n)hvalue:h(n)fvalue:f(n)p_min->gvalue:起始城市到X城的代價relation[p_min->num-1][i]:一個二維數組，X城到Y城的代價min:min{所有兩城之間的代價}number:城市總數p->level:城市節(jié)點所處于搜索樹的層次，和已訪問的城市數同值 在本程序中定義一個結構體node用于表示城市節(jié)點： structnode{ intnum; intfvalue;//f值 intgvalue;//g值 inthvalue;//h值 intlevel;//層 structnode*parent;//父節(jié)點 structnode*next;//后繼 structnode*front;//前驅};定義一個結構體final_path表示Open表和Bestpath表structfinal_path{ structnode*head; structnode*tail;}Open,Bestpath;其中Open表用于存放擴展出來的節(jié)點Bestpath表用于在程序的末尾存放最佳路徑測試數據的輸入使用鄰接矩陣表示完全圖使用二維數組relation[100][100]存放程序流程：將path數組中元素值置下標值：path[i]=i+1按要求輸入鄰接矩陣默認從第一個點開始搜索，并將path[0]=-1，表示該點已被納入路徑擴展剛剛被納入路徑的節(jié)點，擴展的方法為在path數組中搜索值不為-1的元素，為之創(chuàng)建節(jié)點寫入數據（包括g值,h值,f值,parent節(jié)點）并納入Open表中在Open表中搜索f值最小的節(jié)點確定為當前的最優(yōu)路徑點p_min,并且將上一次的最優(yōu)路徑點所在的路徑上所有節(jié)點的path表中的元素值改為其下標值，表示刪除原路徑，同時將p_min所在的路徑上所有節(jié)點的path表中元素值改為-1，表示創(chuàng)建新路徑?；氐?步循環(huán)，直至path表中所有的元素值均為-1退出循環(huán)由此獲得最后一次的最優(yōu)路徑點，利用結構體中的parent指針得到最佳路徑，并將路徑存放在Bestpath表中輸出最佳路徑程序退出。程序缺陷： 由于專注于算法的實現，沒有設置輸入不合法的報錯。 所以若要獲得正確的結果，在輸入路徑點個數和鄰接矩陣時要正確輸入程序截圖：（以5個路徑點為例） 測試用例： 提供四組測試用例（鄰接矩陣表示完全圖），路徑點個數分別是4，5，5，6 第一組：0213204114013110路徑如下:A-->C-->D-->B-->A第二組：0127510443240127410353230路徑如下:A-->B-->E-->C-->D-->A第三組：0534450354330544550344430路徑如下:A-->C-->B-->E-->D-->A第四組：011111101111110111111011111101111110路徑如下:A-->B-->C-->D-->E-->F-->A心得體會： 在這次課程設計中，我第一次使用A*算法，遇到的問題還是不少的 旅行商問題在以前接觸過，當時解決的時候使用的是另外一種算法。 A*算法中最讓我頭疼的地方就是h(n)的設計，要滿足h(n)<h*(n),在最初，我使用了H(n)=max*(number-p->level-1),出來的結果并不一定是最優(yōu)路徑，后來我發(fā)現問題處在max上面，使用max使得算法變得很簡單，但也不完善，使得搜索樹是一路往下走，沒有了回溯的可能性，我將max換成了min，這樣就可以滿足h(n)<h*(n)，使之得到正確的結果。 在寫程序中，定義的Bestpath表本來目的是存放每次搜索出來的當前最優(yōu)路徑點，后來發(fā)現因為不可避免出現算出的最優(yōu)路徑點與前一個路徑點不在同一分支上，造成回溯，所以放棄使用Bestpath實時存放最優(yōu)路徑點，而是在結構體node中增加了parent指針，利用該指針構成鏈表存放路徑，并且在每次找到新節(jié)點的時候刪除原路徑，同時創(chuàng)建新路徑。最終只要得到最優(yōu)路徑即可。核心代碼：structnode{ intnum; intfvalue;//f值 intgvalue;//g值 inthvalue;//h值 intlevel;//層 structnode*parent;//父節(jié)點 structnode*next;//后繼 structnode*front;//前驅};structfinal_path{ structnode*head; structnode*tail;}Open,Bestpath;voidmain(){ intrelation[100][100];//鄰接矩陣 intpath[100];//路徑點集合 inti,j,number;//number路徑點的數目 intmax=0; //存放最大值,用于計算h值 intmin;//存放最小值,用于計算h值 intcount;//用于計數 cout<<"輸入路徑點的數目："; cin>>number; for(i=0;i<number;i++) { path[i]=i+1;//用1，2，3，4.....來表示路徑點 } for(i=0;i<number;i++) {//輸入鄰接矩陣 for(j=0;j<number;j++) { cin>>relation[i][j]; if(relation[i][j]>max)max=relation[i][j]; } } min=max;//初始化min，使其為所有路徑中的最大值 for(i=0;i<number;i++) { for(j=0;j<number;j++) { if(relation[i][j]==0)continue; else { if(min>relation[i][j]) min=relation[i][j]; } } }//設置min為所有路徑中的最小值 structnode*p0=newstructnode; p0->level=0; p0->num=1;//A點 p0->parent=NULL; path[0]=-1;//默認從第一個路徑點開始搜索 Open.head=newstructnode; Open.tail=newstructnode; Open.head->next=Open.tail; Open.tail->front=Open.head;//初始化Open表 structnode*p1,*p2; structnode*p_min; structnode*p_temp; p1=Open.head; p2=Open.tail; //p1,p2用于確定節(jié)點插入Open表的位置 for(i=1;i<number;i++)//對A節(jié)點進行擴展，建立搜索樹的第一層 {//插入節(jié)點 structnode*p; p=newstructnode; p->num=path[i]; p->level=1;//第一層 p->gvalue=relation[0][i];//A點到其他點的距離 p->hvalue=min*(number-p->level-1); p->fvalue=p->gvalue+p->hvalue; p->parent=p0; p1->next=p; p->front=p1; p->next=p2; p2->front=p; p1=p; if(i==1)p_min=p1; else {//尋找最優(yōu)路徑點 if(p_min->fvalue>p1->fvalue)p_min=p1; } } p_temp=p_min; //在Open中刪除找到的路徑點，因為下面將要對它進行擴展 p_min->front->next=p_min->next; p_min->next->front=p_min->front; path[p_min->num-1]=-1;//path中不為-1的個數為未到達路徑點 //擴展找到的路徑點（從第二層level=2開始進入循環(huán)） while(1) { for(i=0,count=0;i<number;i++) { if(path[i]==-1) { count++; } } if(count==number)break;//path數組中所有元素均為-1,則退出 else { p1=Open.tail->front; p2=Open.tail; for(i=0;i<number;i++) { if(path[i]!=-1) { structnode*p; p=newstructnode; p->num=path[i]; p->level=p_min->level+1;//由最優(yōu)路徑點的level確定子節(jié)點的level p->gvalue=p_min->gvalue+relation[p_min->num-1][i]; p->hvalue=min*(number-p->level-1); p->fvalue=p->gvalue+p->hvalue; p->parent=p_min; p1->next=p; p->front=p1; p->next=p2; p2->front=p; p1=p; } } } structnode*p=Open.head->next; i=1; while(p!=Open.tail) {//從Open表中尋找 if(i==1)p_min=p; else {//尋找最優(yōu)路徑點 if(p_min->fvalue>p->fvalue)p_min=p; } i++; p=p->next; }//找到最優(yōu)路徑點 p=p_temp;//上一次的最優(yōu)路徑點 while(p!=NULL) {//撤銷上一次路徑 path[p->num-1]=p->num; p=p->parent; } p=p_min;//新找到的最優(yōu)路徑點 while(p!=NULL) {//重配置新路徑 path[p->num-1]=-1; p=p->parent; } p_temp=p_min;//再次使得p_temp指向最優(yōu)路徑點，為下一次所用 //在Open中刪除找到的路徑點 p_min->front->next=p_min->next; p_min->next->front=p_min->front; } //循環(huán)結束 //初始化Bestpath表 Bestpath.head=newstructnod