問答題

【簡(jiǎn)答題】
根據(jù)優(yōu)先隊(duì)列式分支限界法，求下圖中從v1點(diǎn)到v9點(diǎn)的單源最短路徑，請(qǐng)畫出求得最優(yōu)解的解空間樹。要求中間被舍棄的結(jié)點(diǎn)用×標(biāo)記，獲得中間解的結(jié)點(diǎn)用單圓圈○框起（如○v2），最優(yōu)解用雙圓圈◎框起。

答案：

你可能感興趣的試題

【簡(jiǎn)答題】
有8個(gè)作業(yè){1，2，…，8}要在由2臺(tái)機(jī)器M1和M2組成的流水線上完成加工。每個(gè)作業(yè)加工的順序都是先在M1上加工，然后在M2上加工。M1和M2加工作業(yè)i所需的時(shí)間分別為：

給出一個(gè)最優(yōu)調(diào)度方案，使得從第一個(gè)作業(yè)在機(jī)器M1上開始加工，到最后一個(gè)作業(yè)在機(jī)器M2上加工完成所需的時(shí)間最少，并計(jì)算所需的最少時(shí)間。

答案：

最優(yōu)調(diào)度方案為：

所需的最少時(shí)間為：73

【簡(jiǎn)答題】試述回溯法的基本思想及用回溯法解題的步驟。

答案：回溯法在問題的解空間樹中，按深度優(yōu)先策略，從根結(jié)點(diǎn)出發(fā)搜索解空間樹。算法搜索至解空間樹的任意一點(diǎn)時(shí)，先判斷該結(jié)點(diǎn)是否包含...