便宜算法實(shí)驗(yàn)報(bào)告

實(shí)驗(yàn)報(bào)告實(shí)驗(yàn)?zāi)康模赫莆請(qǐng)D論算法的設(shè)計(jì)與實(shí)現(xiàn)實(shí)驗(yàn)內(nèi)容：用便宜算法求解旅行商問(wèn)題實(shí)驗(yàn)環(huán)境VC++實(shí)驗(yàn)過(guò)程與結(jié)果：便宜算法與旅行商問(wèn)題簡(jiǎn)介：①、旅行商問(wèn)題簡(jiǎn)介：在哈密頓回路中（每條邊都有它的權(quán)）挑選一條總長(zhǎng)最短（或總花費(fèi)最省，旅途時(shí)間最少）的一條哈密頓回路②、便宜算法描述：置點(diǎn)的集合S={2，3，、、、n}，w(1,1)0,k1,序列T=（1，1），w(i,k)=w(i,1),i∈S。在S中，令w(j,t)=minw(i,k)i∈S,k∈T對(duì)回路T中的邊（t,t1）,(t,t2),若w(j,t1)-w(t,t1)<=w(j,t2)-w(t,t2),則j插入到T的t,t1之間，否則j插入到T的t,t2之間，SSj,若S=?，結(jié)束。否則轉(zhuǎn)C。對(duì)全部i∈S,置w(i,k)min(w(i,k),w(i,j)),轉(zhuǎn)到B。算法框圖：3、數(shù)據(jù)結(jié)構(gòu)：ADTList{數(shù)據(jù)對(duì)象：D=（ai|ai∈ElemSet,i=1,2,、、、，n,n>=0）數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=1,2，、、、，n}}4、運(yùn)行結(jié)果：分析與總結(jié)：本程序主要用循環(huán)鏈表實(shí)現(xiàn)，路線的矩陣數(shù)據(jù)存儲(chǔ)在二維數(shù)組中，然后將找到的最短路線所對(duì)應(yīng)得城市放在循環(huán)鏈表中，程序中總共定義了兩個(gè)一樣的數(shù)組，一個(gè)用于操作（將用過(guò)的路線全部置為0）一個(gè)用于調(diào)用其中的路程距離用于最后的總路程的計(jì)算，最后輸出最短路線中的城市和總路程長(zhǎng)度。此程序共用了5個(gè)多小時(shí)，因?yàn)橹袄蠋熤v解得比較清楚，所以程序編起來(lái)思路比較清楚，主要就是把算法實(shí)現(xiàn)，及調(diào)試程序，沒(méi)有遇到太麻煩的問(wèn)題。五、源程序：#include"iostream.h"#include"stdlib.h"#include"iomanip.h"typedefstructLNode{ intdata; structLNode*next;}LNode,*LinkList;voidCreatroute(intCitynum,intRoute[100][100])//創(chuàng)建路線{for(intj=0;j<Citynum;j++){for(inti=0;i<j;i++) {cout<<"請(qǐng)輸入一個(gè)城市距離:"; cin>>Route[i][j]; } Route[i][j]=0;}cout<<endl;cout<<"輸入完畢,下面將數(shù)組填滿";for(j=0;j<Citynum;j++){for(inti=0;i<Citynum;i++) {Route[i][j]=Route[j][i];} } cout<<endl;cout<<"全部設(shè)定好"<<endl;for(j=0;j<Citynum;j++){for(inti=0;i<Citynum;i++) {cout<<setw(5)<<Route[i][j]; cout<<endl;}}}voidCopy(intRoute[100][100],intRRoute[100][100],intCitynum){for(inti=0;i<Citynum;i++) {for(intj=0;j<Citynum;j++) {RRoute[i][j]=Route[i][j];} }}voidVisitList(LinkList&L)//遍歷{LNode*p;p=L->next; while(p->next!=L->next){ cout<<p->data; p=p->next;} cout<<p->data; cout<<endl;}voidcreast(LinkList&Lc)//創(chuàng)建一個(gè)空的循環(huán)鏈表{ Lc=newLNode; Lc->next=NULL;}LNode*findlast(LinkList&L)//找出最后一個(gè)結(jié)點(diǎn){LNode*p; p=L->next; while(p->next!=L->next) {p=p->next;} returnp;}voidthrust(LinkList&Lc,inte)//將e插入一個(gè)新的鏈表中{LNode*p,*q;if(Lc->next==NULL) {q=Lc; p=newLNode; p->data=e; q->next=p; q=p;} else{ q=findlast(Lc); p=newLNode; p->data=e; p->next=q->next; q->next=p; q=p;} q->next=Lc->next;}intCompare(intRoute[100][100],inti,intCitynum)//比較一個(gè)城市與其他城市的距離并返回此城市的號(hào)碼{intj=0;intk;intmin=Route[i][j]; for(j=0;j<Citynum;) {if(Route[i][j]==0) {j++;} else{ min=Route[i][j]; k=j; break;} }j=0; while(j<Citynum) {while(j!=i&&Route[i][j]!=0) {if(Route[i][j]>=min) {j++;} else{min=Route[i][j];k=j; j++;} if(j==Citynum) {break;} } if(j==i||Route[i][j]==0) {j++; if(j==Citynum){break;} } } returnk+1;}voidDelete(intRoute[100][100],LNode*Prior,LNode*Cur)//刪除已經(jīng)比較過(guò)的城市距離{Route[Prior->data-1][Cur->data-1]=0; Route[Cur->data-1][Prior->data-1]=0; Route[Cur->next->data-1][Cur->data-1]=0; Route[Cur->data-1][Cur->next->data-1]=0;}voidInsert(LinkList&TR,LNode*p,intcity)//將某個(gè)城市插入指定指針后邊{LNode*q; q=newLNode; q->data=city; q->next=p->next; p->next=q;}intTotalroute(LinkList&T,intRRoute[100][100]){ LNode*p=T->next;inttotal=0; while(p->next!=T->next) {LNode*q=p->next;total+=RRoute[p->data-1][q->data-1]; p=q; q=q->next;} returntotal;}voidmain(){ LinkListTR;//定義一個(gè)循環(huán)鏈表 creast(TR); intCitynum;//定義城市的總數(shù) intRoute[100][100];//定義距離矩陣 cout<<"請(qǐng)輸入城市的數(shù)目:"; cin>>Citynum; cout<<"構(gòu)造一個(gè)路線數(shù)組:"; cout<<endl; Creatroute(Citynum,Route);//創(chuàng)建各城市間的距離 intRRoute[100][100];//定義相同的距離矩陣 Copy(Route,RRoute,Citynum);//將Route復(fù)制到RRoute LNode*Cur=TR;//定義當(dāng)前指針（一直指向新插入到鏈表中的城市） intCur_City=1; thrust(TR,Cur_City);//先在循環(huán)鏈表中插入兩個(gè)代表第一個(gè)城市的節(jié)點(diǎn) LNode*Prior=Cur;//定義當(dāng)前指針的前一個(gè)指針，用于插入操作 Cur=Cur->next; thrust(TR,Cur_City);//先在循環(huán)鏈表中插入兩個(gè)代表第一個(gè)城市的節(jié)點(diǎn)intk=1;//操作符，標(biāo)志已經(jīng)處理過(guò)幾個(gè)城市intshort_City=Compare(Route,Cur_City-1,Citynum);//通過(guò)調(diào)用函數(shù)找出與當(dāng)前城市最近的城市 Insert(TR,Cur,short_City);//將該城市插入鏈表中 Prior=Cur; Cur=Cur->next; Delete(Route,Prior,Cur);//在Route數(shù)組中將處理過(guò)的城市間的距離變?yōu)? Cur_City=short_City; k++; while(k!=Citynum)//算法描述中已介紹其下操作的含義 {intFront,Back; short_City=Compare(Route,Cur_City-1,Citynum); if(Front=(RRoute[Prior->data-1][short_City-1]-RRoute[Prior->data-1][Cur->data-1])<0) {Front=RRoute[Prior->data-1][Cur->data-1]-RRoute[Prior->data-1][short_City-1];} else {Front=RRoute[Prior->data-1][short_City-1]-RRoute[Prior->data-1][Cur->data-1];}//Front和Back為距離的差 if(Back=(RRoute[Cur->next->data-1][short_City-1]-RRoute[Cur->data-1][Cur->next->data-1])<0) {Back=RRoute[Cur->data-1][Cur->next->data-1]-RRoute[Cur->next->data-1][short_City-1];} else {Back=RRoute[Cur->next->data-1][short_City-1]-RRoute[Cur->data-1][Cur->next->data-1];}if(Front>=Back) {Insert(TR,Cur,short_City); Prior=Cur; Cur=Cur->next; Delete(Route,Prior,Cur); Cur_City=short_City; } else {In