算法設計與分析實驗報告

1、聲明：此文檔只作為學習參考，不得用作它途！ 算法設計與分析實驗教學大綱 實驗學時：32 實驗個數(shù)：7 實驗學分：1 課程性質(zhì)： 適用專業(yè)：計算機科學與技術、軟件工程 教材及參考書： 1. 計算機算法設計與分析，王曉東，北京：電子工業(yè)出版社，2012 2. 算法與數(shù)據(jù)結構，傅清祥等著，北京：電子工業(yè)出版社，2003 3. 計算機算法導引設計與分析，盧開澄著，北京：清華大學出版社，2001 大綱執(zhí)筆人：劉芳 大綱審定人： 郭濤 一、 實驗課的性質(zhì)與任務 算法的設計與分析是計算機科學的核心問題之一，也是計算機科學與技術專業(yè)本科及研究生的一門重要的專業(yè)基礎課，其內(nèi)容是研究計算機領域及其有關領域中的一些

2、非數(shù)值計算的常用算法。課程將覆蓋計算機軟件實現(xiàn)中常用的、有代表性的算法，并具有一定的深度和廣度，通過實驗，使學生理解并掌握算法設計的基本技術，讓學生具有針對所給的問題設計和實現(xiàn)高效算法的基本能力。 二、實驗課程目的與要求 計算機科學的一個核心問題是算法理論，本課程介紹非數(shù)值算法設計的策略與技 術，同時介紹算法的復雜性的概念通過對一些代表性算法的使用達到了解掌握與運用的 目的。 通過完成課程實驗，使學生達到如下要求： 1. 熟悉各種基本常用算法的基本思想、適用范圍，初步掌握算法分析的基本技巧以及如何根據(jù)實際問題設計一個有效的算法。 2. 能對給定問題分析出恰當?shù)臄?shù)學模型，并設計出解決方案，將算法

3、用高級語言 （C，VC+等）編程實現(xiàn)。 三、實驗項目及內(nèi)容提要 算法設計與分析實驗課程 序 實 實驗名稱 學 必 選 學 實驗類型 內(nèi)容提要 號 驗項 目 編號 時 做 做 分 數(shù) 基 本 操 作 驗 證 綜合 設 計 1 1 算法設計 基礎 4 通過本次實驗，程序 設計語言基礎知識， 熟悉文件操作等 2 2 遞歸與分 治策略及 其應用 6 掌握遞歸算法的設 計思想，提高應用分 治法設計算法的技 能 3 3 動態(tài)規(guī)劃 及其應用 6 掌握設計動態(tài)規(guī)劃 算法的步驟，并編程 實現(xiàn)有關算法。 4 4 貪心算法 及其應用 6 通過本次實驗，掌握 設計貪心算法的步 驟，并編程實現(xiàn)有關 問題的求解 54 5

4、 回溯法及 其應用 6 通過本實驗，理解回 溯法的深度搜索策 略，掌握用回溯法解 題的算法框架。 6 6 分支限界 法及其應 用 4 通過本實驗，理解分 支限界法的剪枝搜 索策略，掌握用分支 限界法算法框架 7 7 線性規(guī)劃 問題的求 解 4 理解線性規(guī)劃的算 法模型，了解求解線 性規(guī)劃的單純形算 法，學會使用 Excel 求解線性規(guī)劃問題。 三、實驗內(nèi)容安排： 實驗一 算法設計基礎 （驗證型實驗 4 學時） 1.實驗目的 （1） 鞏固程序設計語言基礎知識，熟悉文件操作等。 （2） 對給定問題，能設計算法并編程實現(xiàn)問題的求解，并分析算法的時間復雜性。 2.實驗要求 （1） 認真填寫實驗報告，附

5、加源代碼（主要代碼）和運行記錄； （2） 對設計好的算法，測試運行實驗數(shù)據(jù)，檢查輸出是否正確。并對算法的時間和空間復雜度進行分析。 3.實驗內(nèi)容： （1） 統(tǒng)計數(shù)字問題（P8） #include "iostream" #include <stdlib.h> #include <fstream.h> ifstream fin("input.txt"); ofstream fout("output.txt"); using namespace std; int i,n,m; int page;/page 是書的總頁

6、數(shù) int number10=0; void main() fin>>page; for (int j=1;j<=page;j+) n=j; while(n) m=n%10; +numberm; n=n/10; for ( i=0;i<=9;i+) fout<<numberi<<endl; fin.close(); fout.close(); return; （2） 字典序問題（P8） （3） 最多約數(shù)問題（P9） #include "iostream" #include <stdlib.h> #include &

7、lt;fstream.h> ifstream fin("input.txt"); ofstream fout("output.txt"); using namespace std; void main() int a,b,i,j,max; fin>>a>>b; int number100=0;/約數(shù)個數(shù) for ( i=a;i<=b;i+) for (j=1;j<=i;j+) if( i%j=0) numberi+;/若能被整除則約數(shù)個數(shù)加 1 for( i=a;i<b;i+) if(numberi>

8、numberi+1) max=numberi; else max=numberi+1; fout<<max<<endl; fin.close(); fout.close(); （4） 最大間隙問題（P10） （5） 設計算法求解 fibonacci 數(shù)列的第 110 項的值。 （6） 設計算法求解盡可能多的完美數(shù)（完全數(shù)） 。 注：至少選擇其中 2 題完成 實驗二 遞歸與分治策略及其應用 （驗證型、設計型實驗 6 學時） 1.實驗目的 （1） 進一步掌握遞歸算法的設計思想以及遞歸程序的調(diào)試技術。 （2） 提高應用分治法設計算法的技能 （3） 理解這樣一個觀點：分治和遞歸

9、經(jīng)常同時應用在算法設計中。 2.實驗要求 （1） 認真填寫實驗報告，附加源代碼（主要代碼）和運行記錄； （2） 對設計好的算法，要分析算法的時間和空間復雜度。 3.實驗內(nèi)容： （1） 設計算法求解整數(shù)的劃分問題，對給定的整數(shù)，輸出劃分數(shù)。 （P14）并思考如何實現(xiàn)輸出每個具體的劃分。 #include "iostream" #include <stdlib.h> using namespace std; int q(int m,int n) if (n<1)|(m<1) return 0; if (n=1)|(m=1)return 1; if (m&

10、lt;n) return q(m,m); if (m=n) return q(m,n-1)+1; return q(m,n-1)+q(m-n,n); void main() int n,m; cout<<"分別輸入 m 和 n 的值(m 為被劃分數(shù)，n 為最大加數(shù))"<<endl; cin>>m>>n; cout<<"劃分數(shù)為："<<endl; cout<<q(m,n)<<endl; system("pause"); （2） 設計算法求解

11、n 個互異元素的全排列的算法并編程實現(xiàn)（P13），并在此基礎上修改程序，使其能解決有重復元素的排列問題（P41算法實現(xiàn)題 2-5）。 #include "iostream" #include <stdlib.h> #include <fstream.h> ifstream fin("input.txt"); ofstream fout("output.txt"); using namespace std; int count=0; int check(char list,int k ,int m ) /判斷是否

12、互異，重復返回 0 if( m > k) for(int i = k ; i< m ; i+) if( listi = listm ) return 0 ; return 1 ; inline void swap(char &a,char &b) char temp; temp=a;a=b;b=temp; void perm(char list,int k,int m) /依次交換第一個元素進行排序 if(k=m) /只剩下一個元素 count+; for(int i=0;i<=m;i+) fout<<listi<<" &qu

13、ot; fout<<endl; else /還有多個元素，遞歸產(chǎn)生排列 for(int i=k;i<=m;i+) if(check(list,k,i) swap(listk,listi); perm(list,k+1,m); swap(listk,listi); return; void main() char number100; int i=0,n=0; /n 是總個數(shù) fin>>number; /number 數(shù)組為待排元素 while(numberi != '0') n+; i+; perm(number,0,n-1); fout<&

14、lt;count; fin.close(); fout.close(); system("pause"); （3） 設計算法求解棋盤的覆蓋問題，并編程實現(xiàn)（P20）。 （4） 設計一個求解 Gray 碼的分治策略，并編程實現(xiàn)（P39 算法分析題 2-14）。 （5） 設計求解半數(shù)集問題的算法，并編程實現(xiàn)。（P40算法實現(xiàn)題 2-3） （6） 設計求解整數(shù)因子分解問題的算法，并編程實現(xiàn)。 （P43 算法實現(xiàn)題 2-11） #include "iostream" #include <stdlib.h> #include <fstream.h

15、> ifstream fin("input.txt"); ofstream fout("output.txt"); using namespace std; void main() int number,result; int count=1; fin>>number;/輸入整數(shù) for(int i=2;i<number;i+) if(number%i=0) result=number/i; /result 是因子 for(int i=2;i<=result;i+) if(result%i=0) count+; fout&l

16、t;<count; fin.close(); fout.close(); （7） 設計求解雙色 hanoi 問題的算法，并編程實現(xiàn)。 （P43 算法實現(xiàn)題 2-11） 注：至少選擇其中 3 題完成 實驗三 動態(tài)規(guī)劃及其應用 （驗證型、設計型實驗 6 學時） 1.目的要求 （1） 理解動態(tài)規(guī)劃算法的概念和基本要素，并能和分治法進行比較。 （2） 掌握設計動態(tài)規(guī)劃算法的步驟，并編程實現(xiàn)有關算法。 （3） 理解這樣一個觀點：同樣的問題可以用不同的方法解決，一個好的算法是反復努力和重新修正的結果。 （4） 對設計好的算法，要分析算法的時間和空間復雜度。 2.實驗內(nèi)容 （1） 編程實現(xiàn)矩陣連乘問題

17、的求解。 （P47） （2） 分別采用分治法和動態(tài)規(guī)劃法求解實現(xiàn)最大子段和問題，并編程實現(xiàn)。（P54） #include "iostream" #include <stdlib.h> using namespace std; int MaxSubSum(int *a,int left,int right) /最大子段和 分治法 int sum=0; if(left=right) sum=aleft>0 ? aleft :0; else int center=(left+right)/2; int leftsum=MaxSubSum(a,left,cente

18、r); int rightsum=MaxSubSum(a,center+1,right); int s1=0; int lefts=0; for(int i=center;i>=left;i-) lefts+=ai; if(lefts>s1) s1=lefts; int s2=0; int rights=0; for( i=center+1;i<right;i+) rights+=ai; if(right>s2)s2=rights; sum=s1+s2; if(sum<leftsum)sum=leftsum; if(sum<rightsum)sum=righ

19、tsum; return sum; int MaxSumDongtai(int n,int *a) /最大子段和 動態(tài)規(guī)劃法 /n 表示前 n 個數(shù)字 int sum=0,b=0; for(int i=1;i<=n;i+) if(b>0) b+=ai; else b=ai; if(b>sum) sum=b; return sum; void main() int a=0,1,2,3,4,5,6,7; int n; cout<<MaxSubSum(a,0,7)<<endl; cout<<MaxSumDongtai(7,a)<<en

20、dl; return; （3） 編程實現(xiàn)最長公共子序列(LCS)問題的求解。 （P52） （4） 編程實現(xiàn) 01 背包問題的求解。 （P71） #include <stdlib.h> #include "iostream" #include <stdio.h> using namespace std; #define max(a,b) (a) > (b) ? (a) : (b) /max(a,b) a,b 中的最大值 #define min(a,b) (a) < (b) ? (a) : (b) /min(a,b) a,b 中的最小值 te

21、mplate <typename Type> void Knapsack(Type* v, int *w, int c, int n, Type *m) /遞歸初始條件 /v 價值,w 重量,c 容量,n 件數(shù),m 價值數(shù) int jMax = min(wn - 1, c); for (int j=0; j<=jMax; j+) /背包的重量 mnj = 0; for (j=wn; j<=c; j+) /背包的價值 mnj = vn; /m(i,j) 背包容量為 j，可選擇物品為 i,i+1n 時 0-1 背包的最優(yōu)值 for (int i=n-1; i>1; i

22、-) jMax = min(wi - 1, c); for (int j=0; j<=jMax; j+) mij = mi+1j; for (j=wi; j<=c; j+) mij = max(mi+1j, mi+1j-wi+vi); m1c = m2c; if (c >= w1) m1c = max(m1c, m2c-w1+v1); cout<<m1c<<endl; template <typename Type> void TraceBack(Type *m, int *w, int c, int n, int* x) /物品裝入 xi

23、為 1，反之為 0；背包容量 c 減少當前裝入物品的重量 for (int i=1; i<n; i+) if(mic = mi+1c) xi = 0; else xi = 1; c -= wi; xn = (mnc)? 1:0; void main(int argc, char* argv) int n = 6,c = 20,x7; /n 個物品，用 x7來記錄每個物品是否裝入，c 背包容量 int w7 = -2, 5, 10, 9, 5, 2, 1; /每個物品的重量 int v7 = -1, 6, 3, -4, 4, 6, 0; /每個物品的價值 int *ppm = new in

24、t*n+1; for (int i=0; i<n+1; i+) ppmi = new intc+1; Knapsack<int>(v, w, c, n, ppm); TraceBack<int>(ppm, w, c, n, x); for ( i=1; i<=n; i+) cout<<xi; return; （5） 設計一個 O(n2)時間的算法，找出由 n 個數(shù)組成的序列的最長單調(diào)遞增子序列。（P87 算法分析題 3-1） （6） 設計算法求解獨立任務最優(yōu)調(diào)度問題，并編程實現(xiàn)。 （P79算法實現(xiàn)題 3-1） （7） 設計算法求解石子合并問題編程

25、實現(xiàn)。（P79 實現(xiàn)題 3-3） （8） 設計算法求解數(shù)字三角形問題，并編程實現(xiàn)。 （P80題 3-4） #include <stdio.h> void main() int a100100; int i,j,n; printf("輸入行數(shù)：") ; scanf("%d",&n) ; for(i = 1 ; i <= n ; i + ) printf("輸入第%d 行數(shù)：n",i); for( j =1 ;j <= i; j+) scanf("%d",&aij ) ; for

26、(i = n-1;i>0;i-) for(j = i;j>0;j-) aij += ai+1j+1 > ai+1j?ai+1j+1 : ai+1j; /aij選 ai+1j+1,ai+1j中最大的 printf("最大路徑和是：%dn",a11 ) ; return; （9） 設計算法求解最小 m 段和問題，并編程實現(xiàn)。 （P81題 3-8） （10） 設計算法求解最少費用購物問題，并編程實現(xiàn)。（P88 算法實現(xiàn)題 3-14） 注：至少選擇其中 3 題完成。 3.主要儀器設備及軟件 （1） PC 機 （2） TC、VC+、Java 等任一編程語言 實驗四

27、貪心算法及其應用 （驗證型、設計型實驗 6 學時） 1.目的要求： （1） 理解貪心算法的概念和基本要素； （2） 掌握設計貪心算法的步驟，并編程實現(xiàn)有關問題的求解。 2.實驗內(nèi)容： （1） 編程實現(xiàn)活動安排問題的求解。 （P91） void sort(int f,int n) /結束時間 f排序 int temp; for(int i=1;i<n;i+) for(int j=0;j<i;j+) if(fj>fj+1) /結束時間按從早到晚排序 temp=fj; fj=fj+1; fj+1=temp; cout<<"排序結果："<<

28、endl; for(int i=0;i<n;i+) cout<<fi<<" " int greedySelector(int s, int f, bool A) /活動安排算法 int n=s.length-1,j=1,count=1; A1=true; for(int i=2;i<=n;i+) if(si>=fj) /若下一活動開始時間晚于上一活動，則下一活動可安排，活動數(shù)count 加 1 Ai=true; j=i; count+; else Ai=false; return count; （2） 設計算法求解會場安排問題，并編

29、程實現(xiàn)。（P108，算法實現(xiàn)題 4-1）。 （3） 編程實現(xiàn)最優(yōu)裝載問題的求解。 （P95） #include "iostream.h" void sort(int *w,int *t,int n) /按照 weight 的升序進行排序 t for(int i=0;i <=n;i+) int minweight=w0;/最小值 for(int j=i;j <=n;j+) int temp=j; for(int k=i;k <=j;k+) if(wk <wtemp) minweight=wk; temp=k; tj=temp; void loadlin

30、g(int x,int w,int c,int n) int *t=new intn+1;/指向物品的序號 sort(w,t,n); for(int i=1;i <=n;i+) xi=0; for(i=1;i<=n&&wti<=c;i+) xti=1; c-=wi; cout<<"輸出所裝載的物品序列號以及它的重量為：" <<ti<<" "<<wi<<endl; void main() int n,c; cout<<"請輸入要裝載物品的數(shù)量

31、"<<endl; cin>>n; int *w=new intn+1;/指向物品的重量 int *x=new intn+1; for(int i=1;i <=n;i+) xi=0; cout<<"請輸入該所能夠裝載的最大重量："<<endl; cin>>c; cout<<"請輸入裝載的物品的重量"<<endl; for( i=1;i<n+1;i+) cin>>wi; loadling(x,w,c,n); return; （4） 編程實現(xiàn)背

32、包問題的求解。 （P94） void Sort(int n,float v,float w) /按單位價值為物品排序 float l = v/w+v%w; void bubblesort(sqlist &l) /冒泡排序 int lastexchangeindex; int i,j; RcdType temp20; i=l.length; while(i>1) lastexchangeindex=1; for(j=1;j<l.length;j+) if(l.rj+1.key<l.rj.key) tempj=l.rj; l.rj=l.rj+1; l.rj+1=tempj

33、; lastexchangeindex=j; i=lastexchangeindex; void Knapsack(int n,float M,float v,float w,float x) Sort(n,v,w); int i; float c = M; for(i = 1;i <= n;i+) xi = 0; /初始化 xi for(i = 1;i <= n;i+) if(wi>c) break; xi = 1; c-=wi; if(i<=n) xi = c/wi; return; （5） 編程實現(xiàn)多機調(diào)度問題的求解。 （P106） （6） 設計算法求解汽車加油問

34、題，并編程實現(xiàn)。（P111，算法實現(xiàn)題 49）； #include <stdio.h> void greedy(int d,int n,int k) int num = 0; /加油次數(shù) for(int i = 0;i <= k;i+) /若加油站距離大于最大行駛距離，則無解 if(di > n) printf("No Solutionn"); return; int s = 0; for(i = 0;i <=k;i+) /若下站與下下站距離之和大于最大行駛數(shù)，則加油，反之不加 s += di; if(s > n) num+; s = d

35、i; printf("%dn",num); void main() int i,n,k,d1000; /最多行駛 n 千米，k 個加油站，每個加油站距離 d; printf("請輸入汽車加滿油最大行駛距離n"); scanf("%d",&n); printf("請輸入加油站個數(shù)n"); scanf("%d",&k); printf("請依次輸入每個加油站距上一站距離n"); for(i = 0;i <= k;i+) scanf("%d"

36、;,&di); greedy(d,n,k); return; （7） 設計算法求解刪數(shù)問題，并編程實現(xiàn)。（P112，算法實現(xiàn)題 4-11）； （8） 設計算法求解數(shù)列級差問題，并編程實現(xiàn)。 注：至少選擇其中 3 題完成。 3.主要儀器設備及軟件 （1） PC 機 （2） TC、VC+、Java 等任一編程語言 實驗五 回溯法及其應用 （驗證型、設計型實驗 6 學時） 1.目的要求： （1） 理解回溯法的深度搜索策略，掌握用回溯法解題的算法框架； （2） 掌握設計回溯算法的基本技巧和實際問題的分析求解。 2.實驗內(nèi)容： （1） 設計算法從前 m 個大寫字母(m26)種取出 n 個字母的所

37、有排列（組合），并編程實現(xiàn)。 （2） 設計算法求解子集合問題，并編程實現(xiàn)。 （P151，算法實現(xiàn)題 5-1） （3） 設計算法求解工作分配問題，并編程實現(xiàn)。（P156，算法實現(xiàn)題 5-13） （4） 設計算法實現(xiàn) 01 背包問題，并編程實現(xiàn)。（P159，算法實現(xiàn)題 5-22） （關鍵代碼） /*0-1 背包改進算法*/ int bestp;/最優(yōu)結果 /*限界函數(shù)*/ int bound(int i,int cw,int cp) cw+=xi*wi; cp+=xi*pi; int cleft=c-cw; int b=cp; for(int j=i+1;j<=n&&wj&l

38、t;=cleft;j+) b+=pj; cleft-=wj; if(j<n) b+=pj*(cleft)/wj; return b; bool check(int i,int cw,int cp) if(cw+xi*wi>c)|(bound(i,cw,cp)<bestp) return false; else return true; void output(int i) cout<<i; /*功能函數(shù)*/ void tryload(int i;int cw;int cp) /cw 當前背包容量,cp 當前背包價值 if(i>n) /輸出一個可行解 outp

39、ut(i); else for(int j=1;j>=0;j-) xi=j; if(check(i,cw,cp) cw+=xi*wi; cp+=xi*pi; tryload(i+1,cw,cp); cw-=xi*wi; cp-=xi*pi; /*主函數(shù)*/ void main() tryload(1,0,0); （5） 設計算法求解旅行售貨員問題，并編程實現(xiàn)。 （P139） 關鍵代碼 #include "iostream.h" #include "stdlib.h" #define noedge 10000 int n,*bestx,*a,best

40、c; /頂點數(shù),最優(yōu)解，G 的鄰接矩陣，最優(yōu)值 /*主函數(shù)*/ void main() getdata(); bestc=noedge; for(int i=1;i<=n;i+) bestxi = xi = i; traveling(2,0); cout<<bestc; for(int i=1;i<=n;i+) cout<<bestxi; /*約束、限界函數(shù)*/ bool check(int i,int cc) if(axi-1xi != noedge && cc+axi-1xi < bestc) return true; else r

41、eturn false; /*功能函數(shù)*/ bool traveling(int i;int cc) if(i>n) else for(int j=i;j<=n;j+) swap(xi,xj); if(check(i,cc) cc+=axi-1xi; traveling(i+1,cc); cc-=axi-1xi; swap(xi,xj); if(axn1!=noedge) for(int k=1;k<=n;k+) cout<<xk; cc+=axnx1; cour<<cc; （6） 設計算法求解 n 后問題，并編程實現(xiàn)。（P129） #include

42、"stdio.h" #include "stdlib.h" #include "math.h" #include "iostream" using namespace std; int n;/皇后個數(shù) int *x; int count=0; bool check(int i) for(int k=1;k<i;k+) if(xk=xi)|fabs(xk-xi)=fabs(k-i) return false; else return true; void output(int i) cout<<i;

43、 int queue(int i) if(i>n) output(i); return 0; else for(int j=1;j<=n;j+) xi=j; if(check(i) i+; count+; return queue(i+1); void main() cout<<"請輸入皇后個數(shù)："<<endl; cin>>n; x=new intn+1; queue(1); cout<<"可行方案有"<<count<<"種"<<endl;

44、 （7） 設計算法完成圖的 m 著色問題，并編程實現(xiàn)。 （P137） 關鍵代碼 #include "iostream.h" #include "stdlib.h" void main() getdata(); count=0; trycolor(1); cout<<endl<<" " void trycolor(int i) if(i>n) output(); else for(int j=1;j<=m;j+) xi = j; if(check(i) trycolor(i+1); bool chec

45、k(int i) for(int k=1;k<=i+1;i+) if(aki) = 1 && (xk = xi) return false; return true; （8） 設計算法用 L 形覆蓋一個正方塊組成的正方形，要求不重不漏(若邊長不剛好，還需要挖掉 1 塊)。 （9） 設計算法求解最佳調(diào)度問題，并編程實現(xiàn)。（P156，算法實現(xiàn)題 5-15） （11） 設計算法求解無優(yōu)先級運算問題，并編程實現(xiàn)。（P156，算法實現(xiàn)題 5-16） 注：至少選擇其中 3 題完成。 3.主要儀器設備及軟件 （1） PC 機 （2） TC、VC+、Java 等任一編程語言 實驗六 分支

46、限界法及其應用 （ 驗證型、設計型實驗 4 學時） 1.目的要求 （1） 理解分支限界法的基本思想和剪枝搜索策略； （2） 掌握設計分支限界法的基本技巧和實際問題的分析求解。 2.實驗內(nèi)容： （1） 編程實現(xiàn) 0/1 背包問題的隊列式/優(yōu)先隊列式分支限界算法； （2） 編程實現(xiàn)隊列式/優(yōu)先隊列式分支限界算法求解旅行商問題的求解。 #include <stdio.h> template<class Type> class Traveling friend void main(void); public: Type BBTSP(int v); private: int n;

47、 /圖 G 的頂點數(shù) Type *a, /圖 G 的鄰接矩陣 NoEdge, /圖 G 的無邊標志 cc, /當前費用 bestc; /當前最小費用 ; template<class Type> class MinHeapNode friend Traveling<Type> public: operator Type()const return lcost; private: Type lcost, /子樹費用的下界 cc, /當前費用 rcost, /xs:n-1中頂點最小出邊費用和 int s, /根結點到當前結點的路徑為 x0:s *x; /需要進一步搜索的頂點

48、是 xs+1:n-1 template<class Type> Type Traveling<Type>:BBTSP(int v) /旅行收貨商問題的優(yōu)先隊列式分支限界法 /定義最小堆的容量為 1000 MinHeap<MinHeapNode<Type>>H(1000); Type *MinOut = new Typen+1; /計算 MinOuti = 頂點 i 的最小出邊費用 Type MinSum = 0;/最小出邊費用和 for(int i=1;i<=n;i+) Type Min = NoEdge; for(int j=1;j<=n;j+) if(aij!=NoEdge && (aij<Mi