西安郵電大學(xué)學(xué)算法設(shè)計(jì)工作分配問題實(shí)驗(yàn)報(bào)告

曲美郭皆大學(xué)《算法設(shè)計(jì)與分析》上機(jī)實(shí)驗(yàn)報(bào)告專業(yè)軟件工程班級(jí)1101學(xué)號(hào)學(xué)生姓名完成日期2013-11-28上機(jī)題目及實(shí)驗(yàn)環(huán)境1.1上機(jī)題目：工作分配問題1.2實(shí)驗(yàn)環(huán)境：CPU：2.40GHz內(nèi)存：2.00GB（1.89GB可用）操作系統(tǒng)：Windows7旗艦版軟件平臺(tái)：MicrosoftVisualC++算法設(shè)計(jì)與分析（1）用c[i][j]存儲(chǔ)將工作i分配給第j個(gè)人所需的費(fèi)用，用v[j]標(biāo)記第j個(gè)人是否已分配工作；（2）用遞歸函數(shù)backtrack（i，total）來實(shí)現(xiàn)回溯法搜索排列樹（形式參數(shù)i表示遞歸深度，n用來控制遞歸深度，形式參數(shù)total表示當(dāng)前總費(fèi)用，s表示當(dāng)前最優(yōu)總費(fèi)用）：若total>=s，則不是最優(yōu)解，剪去相應(yīng)子樹，返回到i-1層繼續(xù)執(zhí)行；若i>n，則算法搜索到一個(gè)葉結(jié)點(diǎn)，用s對(duì)最優(yōu)解進(jìn)行記錄，返回到i-1層繼續(xù)執(zhí)行；采用for循環(huán)針對(duì)n個(gè)人對(duì)工作i進(jìn)行分配（1WjWn）：若v[j]==1，則第j個(gè)人已分配了工作，找第j+1個(gè)人進(jìn)行分配；若v[j]=0，則將工作i分配給第j個(gè)人（即v[j]=1），對(duì)工作i+1調(diào)用遞歸函數(shù)backtrack（i+1，total+c[i][j]）繼續(xù)進(jìn)行分配；函數(shù)backtrack（i+1，total+c[i][j]）調(diào)用結(jié)束后則返回v[j]=0，將工作i對(duì)第j+1個(gè)人進(jìn)行分配；當(dāng)j>n時(shí)，for循環(huán)結(jié)束；當(dāng)i=1時(shí)，若已測(cè)試完c[i][j]的所有可選值，外層調(diào)用就全部結(jié)束；（3）主函數(shù)調(diào)用一次backtrack（1，0）即可完成整個(gè)回溯搜索過程，最終得到的s即為所求最小總費(fèi)用。核心代碼voidbacktrack（inti,inttotal）//i表示遞歸深度{if(total>=s)return;if(i>n){s=total;return;}elsefor(intj=1;j<=n;j++)//n用來控制遞歸深度{if(v[j]==1)continue;if(v[j]==0){v[j]=1;backtrack(i+1,total+c[i][j]);v[j]=0;}}}4.運(yùn)行與調(diào)試

-■vt三I算法設(shè)計(jì)與分■析\桎序H作分配問筑.11=1I回工作數(shù)量’即人數(shù)為，3用用用費(fèi)費(fèi)費(fèi)工工工AAA122第第第2*234工Pressanykeytocontinue最小忌費(fèi)用為、23工作數(shù)量,'巳認(rèn)三\管法設(shè)計(jì)與分■析\程序\工作分配問題\口日況g\X作分配問虱“仁圖201-8一一一一S8079用用用費(fèi)費(fèi)費(fèi)工工工AAA122第第第2*234工Pressanykeytocontinue最小忌費(fèi)用為、23工作數(shù)量,'巳認(rèn)三\管法設(shè)計(jì)與分■析\程序\工作分配問題\口日況g\X作分配問虱“仁圖201-8一一一一S8079068155E495作S工1口工工工工Ln,DM,rTT,j~tttTttTtAAAAA用用用用用費(fèi)費(fèi)費(fèi)費(fèi)費(fèi)Efia124作工&5.結(jié)果分析和小結(jié)(1)對(duì)結(jié)果的分析。分析結(jié)果可以采用圖或者表的形式給出。圖3input.txt圖4output.txt

圖6output.txt圖5input.txt(圖3input.txt圖4output.txt圖6output.txt通過本次試驗(yàn)，我很好的掌握了回溯算法的基本知識(shí)，理解了回溯算法的思想。知道了什么情況該用回溯算法，很大地提高了編程效率，可謂是收獲良多。現(xiàn)在的我，無論是編程能力還是編程效率，相較于從前，都有了很大的提高，對(duì)此我感到十分開心。附錄(C/C++源代碼)#include<iostream.h>#include<fstream.h>#defineN1000intn;〃工作數(shù)，即人數(shù)intc[N][N];//存儲(chǔ)將工作i分配給第j個(gè)人所需的費(fèi)用intv[N];〃標(biāo)記第i個(gè)人是否已分配工作。1為已分配,0為未分配ints=N;〃當(dāng)前最優(yōu)總費(fèi)用inttotal=0;〃當(dāng)前總費(fèi)用voidbacktrack(inti,inttotal)//i表示遞歸深度{if(total>=s)return;if(i>n)s=total;return;}elsefor(intj=1;j<=n;j++)//n用來控制遞歸深度{if(v[j]==1)continue;if(v[j]==0){v[j]=1;backtrack(i+1,total+c[i][j]);v[j]=0;}}}intmain(){ifstreamin;〃讀文件操作in.open("E:\\大三\\算法設(shè)計(jì)與分析\\程序\\工作分配問題\\input1.txt”);in>>n;//從文件中讀取n的值for(inti=1;i<=n;i++)for(intj=1;j<=n;j++){in>>c[i][j];//從文件中讀取c[i][j]的值v[j]=0;//初始化v[]backtrack(1,0);〃輸出工作數(shù)量，即人數(shù)cout<<”工作數(shù)量，即人數(shù)為："<<n<<endl<<endl;cout<<”工作1";for(i=2;i<=n;i++)cout<<"工作"<<i;cout<<endl;〃輸出每個(gè)人每項(xiàng)工作的費(fèi)用for(i=1;i<=n;i++){TOC\o"1-5"\h\zcout<<"第"<<i<<”個(gè)人的工作費(fèi)用：";for(intj=1;j<=n;j++)if(c[i][j]>9)cout<<c[i][j]<<"";elsecout<<c[i][j]<<"";cout<<endl;}cout<<endl