PAGEPAGE6《高級算法設計與分析》期末試卷（試卷2）姓名：___________________學號：___________________要求：所有題目的解答均寫在答題紙上，需寫清楚題目序號。每張答題紙都要寫上姓名和學號一、選擇題（每題3分，共45分）下面問題不能用動態規劃求解的是：A：0-1背包問題B:矩陣連乘問題C:兩點之間最長路徑問題D:最大子數組問題貪心算法能夠獲得最優解的是：A:旅行商問題B:0-1背包問題C:最大團問題D:最小生成樹問題對如圖所示的旅行商問題，用分支限界法求解時，其最優下界為：A:16B:18C:13D:15將下面非標準型的線性規劃轉化為標準型：B.C.D.線性規劃問題如下，其對偶問題為：B.D.對于隨機算法的描述，以下描述錯誤的是:A.算法運算很快B.算法有一定的概率產生錯誤的結果C.算法的輸出是確定的D.隨機快速排序的期望時間復雜度為O(nlogn)在隨機快速排序算法中，設S(i)表示集合S中階為i的元素，下面描述錯誤的是（注：j>i）:只有S(i)和S(j)這兩個元素其一被選為主元素的時候，他們才進行比較當元素S(k)(i<k<j)被選為主元素時，S(i)和S(j)肯定不會進行比較S(i)和S(j)比較的概率為：pij=2/(j-i+1)當元素S(k)(k>j)被選為主元素時，S(i)和S(j)肯定會進行比較以下對規約的描述錯誤的是：，如果B是P問題，則A一定也是P問題，如果A是NPC問題，則B一定也是NPC問題如果A問題可以歸約為B問題，則A問題和B問題必須是一一對應關系規約函數必須是多項式時間復雜度的函數以下問題不是NPC問題的是：A.小數背包問題B.最大團問題C.旅行商問題D.整數規劃問題在團問題的NP難證明過程中,以下說法錯誤的是：3合取范式可以歸約為團問題歸約的過程中，3合取范式會歸約為一個特殊的圖，所以我們只能說明這個特殊的圖的團問題是NP難的，而無法證明所有的圖的團問題都是NP難的在規約的過程中,一個子句對應一組頂點，對于任意兩個在不同組的頂點，如果滿足“這兩個頂點不是‘否’的關系”這一條件，就用一條邊連接如果3合取范式如果有k個子句，則需要證明圖中有規模為k的團針對集合覆蓋問題，設wi為子集Si的權重，xi=0表示沒有選中子集Si，xi=1表示選中子集Si。則集合覆蓋問題建模成整數規劃形式為（注：n為元素的個數，m為子集的個數）：B.C.D.下面對旅行商問題（滿足三角不等式）的近似算法描述錯誤的是：算法的基本思想是：生成最小生成樹，按對樹進行先序遍歷的順序訪問節點。最小生成樹的總代價小于等于旅行商回路的總代價對T進行按先序往返遍歷，其總代價小于等于2倍的旅行商回路的總代價算法的總代價大于等于對T進行按先序往返遍歷的總代價下面對在線算法和離線算法比較，以下描述錯誤的是：即使數據在計算時都已知，也可以采用在線算法來達到更好的結果在線算法通常是近似算法通常通過和離線最優算法的比較來判斷在線算法的好壞，如果在線算法的代價Con和離線算法的代價Coff有關系，則稱在線算法在實例IA上為α競爭度算法最小生成樹在線算法可通過貪心算法實現在租賣問題的在線算法中，b=2為購買價格，l<=3為天數，則所有的確定性算法如下表，其中Ai為第i天購買，Ii為滑雪場最后一天開放為第i天，其中錯誤的是：最好的確定性算法為A2和A?，都是3/2競爭度在線算法中，以1/3的概率執行A1策略，2/3的概率執行A2策略，可以實現競爭度4/3在線算法中，以2/3的概率執行A1策略，1/3的概率執行A2策略，也可以實現競爭度4/3本例子在線算法的最優競爭度為4/3下面對禁忌表搜索（Tabusearch）算法描述錯誤的是：算法的基本思想是標記已經解得的局部最優解或求解過程，并在進一步的迭代中避開這些局部最優解或求解過程那些目前在禁忌表的解或者求解過程是無條件被禁止的進入禁忌表的解或者求解過程在一定的時間后會被解禁禁忌表搜索每次迭代總是在前一次迭代的領域中進行搜索二、計算、建模題（共40分）設某指派問題的費用矩陣為：其中第i行表示第i個人被指派各個任務的費用，而第j列第j個任務被分配到各個人的費用。試用匈牙利法求最優指派，以及在最優指派下的總費用。（10分）已知下面的線性規劃問題，其對偶問題的最優解為y*=(y1,y2)=(4,1)，試用對偶的互補松弛性求原問題的最優解（10分）集合覆蓋的問題如下：X為元素的集合，Si為X的一個子集，F為Si的集合，集合覆蓋就是找到F的一個最小子集C，使得X中的所有元素都C覆蓋。試證明集合覆蓋是NPC問題(10分)簡單描述如何用遺傳算法實現廣義旅行商問題的求解，描述要包含個體（染色體）設置，適應度函數定義，選擇算子，交叉和變異操作（10分）三、算法設計題（共15分）1.0-1背包問題:設有n個