人工智能技術(shù)課程設(shè)計報告

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

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

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