最佳調(diào)度問題(回溯算法)

1、算法設(shè)計(jì)與分析上機(jī)報(bào)告姓名：學(xué)號(hào)：姓名：學(xué)號(hào)：日期：上機(jī)題目：最佳調(diào)度問題(回溯算法)實(shí)驗(yàn)環(huán)境：CPU:2.10GHz;內(nèi)存:6G;操作系統(tǒng)：Win764位;軟件平臺(tái):VisualStudio2008;一、算法設(shè)計(jì)與分析：題目最佳調(diào)度問題回溯算法設(shè)有個(gè)任務(wù)由個(gè)可并行工作的機(jī)器來完成，完成任務(wù)需要時(shí)間為。試設(shè)計(jì)一個(gè)算法找出完成這個(gè)任務(wù)的最佳調(diào)度，使完成全部任務(wù)的時(shí)間最早。算法思想：解空間的表示：一個(gè)深度為的叉樹。第個(gè)任務(wù)的時(shí)間當(dāng)前輸出結(jié)果表示第個(gè)任務(wù)要運(yùn)行在第臺(tái)機(jī)器上第個(gè)機(jī)器上的運(yùn)行時(shí)間基本思路：、搜索從開始結(jié)點(diǎn)(根結(jié)點(diǎn))出發(fā)，以搜索整個(gè)解空間。2每搜索完一條路徑則記錄下time_min和序列，

2、開始結(jié)點(diǎn)就成為一個(gè)活結(jié)點(diǎn),同時(shí)也成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)。在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處向縱深方向移至一個(gè)新結(jié)點(diǎn)，并成為一個(gè)新的活結(jié)點(diǎn)，也成為當(dāng)前擴(kuò)展結(jié)點(diǎn)。、如果在當(dāng)前的擴(kuò)展結(jié)點(diǎn)處不能再向縱深方向擴(kuò)展，則當(dāng)前擴(kuò)展結(jié)點(diǎn)就成為死結(jié)點(diǎn)。此時(shí)，應(yīng)往回移動(dòng)(回溯)至最近的一個(gè)活結(jié)點(diǎn)處，并使這個(gè)活結(jié)點(diǎn)成為當(dāng)前的擴(kuò)展結(jié)點(diǎn)；直至找到一個(gè)解或全部解。二、核心代碼：boolplacetest(intk)inttime_max_K=time_machine1;for(inti=2;i=K;i+)if(timemachineitimemaxK)if(timeKtime_min)elseif(timeKtime_min)elseretu

3、rntrue;voidBacktrack(intk,intt,intx口)if(kN)inttime_max_K=time_machine1;for(inti=2;i=K;i+)if(time_machineitime_max_K)timemaxK=timemachinei;if(timemaxKtimemin)time_min=time_max_K;for(inti=1;i=N;i+)Resi=xi;elsefor(inti=1;i=K;i+)xk=i;if(placetest(k)time_machinei+=tk;Backtrack(k+1,t,x);time_machinei-=tk;算法源代碼（描述）最佳調(diào)度問題回溯算法設(shè)有個(gè)任務(wù)由個(gè)可并行工作的機(jī)器來完成，完成任務(wù)需要時(shí)間為。試設(shè)計(jì)一個(gè)算法找出完成這個(gè)任務(wù)的最佳調(diào)度，使完成全部任務(wù)的時(shí)間最早。附錄（源代碼）請(qǐng)輸入任務(wù)個(gè)數(shù)和機(jī)