算法分析與設(shè)計(jì)線下作業(yè)三

1、算法分析與設(shè)計(jì)學(xué)習(xí)中心：專(zhuān) 業(yè)：學(xué) 號(hào)：姓 名：作業(yè)練習(xí)三一、名詞解釋1、多機(jī)調(diào)度問(wèn)題多機(jī)調(diào)度問(wèn)題要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。同時(shí)約定每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。2、優(yōu)先隊(duì)列式分支限界法分支限界法常以廣度優(yōu)先或以最小耗費(fèi)（最大效益）優(yōu)先的方式搜索問(wèn)題的解空間樹(shù)。在分支限界法中，每一個(gè)活結(jié)點(diǎn)只有一次機(jī)會(huì)成為擴(kuò)展結(jié)點(diǎn)?；罱Y(jié)點(diǎn)一旦成為擴(kuò)展結(jié)點(diǎn)， 就一次性產(chǎn)生其所有兒子結(jié)點(diǎn)。在這些兒子結(jié)點(diǎn)中，導(dǎo)致不可行解或?qū)е路亲顑?yōu)解的兒子結(jié)點(diǎn)被舍棄，其余兒子結(jié)點(diǎn)被加入活結(jié)點(diǎn)表中。此后，從活結(jié)點(diǎn)表中

2、取下一結(jié)點(diǎn)成為當(dāng)前擴(kuò)展結(jié)點(diǎn)，并重復(fù)上述結(jié)點(diǎn)擴(kuò)展過(guò)程。這個(gè)過(guò)程一直持續(xù)到找到所需的解或活結(jié)點(diǎn)表為空時(shí) 為止二、簡(jiǎn)答題1、簡(jiǎn)述回溯法的基本思想。答：回溯法的基本做法是搜索，在問(wèn)題的解空間樹(shù)中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹(shù)。算法搜索至解空間樹(shù)的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含問(wèn)題的解。如果肯定不包含，則跳過(guò)對(duì)該結(jié)點(diǎn)為根的子樹(shù)的搜索，逐層向其祖先結(jié)點(diǎn)回溯；否則，進(jìn)入該子樹(shù)， 繼續(xù)按深度優(yōu)先策略搜索。2、簡(jiǎn)要分析分支限界法與回溯法的異同。答：1）求解目標(biāo)：回溯法的求解目標(biāo)是找出解空間樹(shù)中滿(mǎn)足約束條件的所有解，而分支限界法的求解目標(biāo)則是找出滿(mǎn)足約束條件的一個(gè)解，或是在滿(mǎn)足約束條件的解中找出在某

3、種意義下的最優(yōu)解。2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹(shù)，而分支限界法則以廣度優(yōu)先或以最小耗費(fèi)優(yōu)先的方式搜索解空間樹(shù)。3、常見(jiàn)的分支限界法有哪些？簡(jiǎn)述之。答：1）隊(duì)列式（FIFO）分支限界法按照隊(duì)列先進(jìn)先出（FIFO）原則選取下一個(gè)節(jié)點(diǎn)為擴(kuò)展節(jié)點(diǎn)。2）優(yōu)先隊(duì)列式分支限界法按照優(yōu)先隊(duì)列中規(guī)定的優(yōu)先級(jí)選取優(yōu)先級(jí)最高的節(jié)點(diǎn)成為當(dāng)前擴(kuò)展節(jié)點(diǎn)。三、算法編寫(xiě)及算法應(yīng)用分析題1、分派問(wèn)題一般陳述如下：給 n個(gè)人分派n件工作，把工作j分派給第i個(gè)人的代價(jià)是 COST（i,j）（非負(fù)實(shí)數(shù)）。要求設(shè)計(jì)一個(gè)回溯算法，在給每個(gè)人分派一件不同工作的前提下使 得總代價(jià)最小。按照回溯法求解問(wèn)題的基本步驟，請(qǐng)

4、你完成幾個(gè)任務(wù)：給出解的一般形式，寫(xiě)出解空間。以n=4為例畫(huà)出表示解空間的狀態(tài)空間樹(shù)。并指出樹(shù)中哪些結(jié)點(diǎn)是解結(jié)點(diǎn)？提出一個(gè)在深度優(yōu)先搜索狀態(tài)空間樹(shù)時(shí)用于剪枝的剪枝函數(shù)（用文字描述）。2、設(shè)計(jì)一個(gè)回溯算法來(lái)求解 k-著色問(wèn)題：給定無(wú)向圖 G=,要求使用k種顏色來(lái)給圖 中每個(gè)結(jié)點(diǎn)著色（每個(gè)結(jié)點(diǎn)使用k種顏色之一），使得沒(méi)有兩個(gè)相鄰的結(jié)點(diǎn)顏色相同。給出解向量的形式，并畫(huà)出當(dāng) n=3,k=3時(shí)的搜索樹(shù)。給出剪枝操作。最壞情況下你的算法在搜索樹(shù)上會(huì)生成多少個(gè)結(jié)點(diǎn)？分析算法的時(shí)間復(fù)雜度。3、對(duì)于下圖使用 3、對(duì)于下圖使用 Dijkstra算法求由頂點(diǎn)a到其他各個(gè)頂點(diǎn)的最短路徑。并給出求各個(gè)頂點(diǎn)對(duì)之間的最短路徑的算法思想。4、設(shè)計(jì)一個(gè)求解下列最大完全子圖問(wèn)題的回溯算