[工學(xué)]算法設(shè)計隨機算法np問題-資料下載頁
2025-10-04 18:48本頁面
【正文】 以多項式時間求解的問題 NP類問題：在非確定性圖靈機（尚未實現(xiàn)的計算機模型）上可以多項式時間內(nèi)求解的問題 2021/11/10 40 of 158 ?P類問題是 NP類問題的一個子集合 尚無法證明： P=NP還是 P是 NP的真子集？ NP完全問題：除非 P=NP，否則不可能找到多項式時間的確定性算法的一類問題 2021/11/10 41 of 158 ?盡管理論上沒有證明，但大量研究表明，P似乎不等于 NP，所以，一旦一個問題被證明是 NP完全的，則基本可以斷定，它不可能在多項式時間內(nèi)求解 NP P NP完全 2021/11/10 42 of 158 計算復(fù)雜性理論基礎(chǔ) ? P類問題和 NP問題 ? NP完全問題舉例 ? SAT問題 （ Boolean Satisfiability Problem） ? 旅行商問題 （ Traveling Salesman Problem） ? 01背包問題 （ 01 Knapsack Problem） ? 最大團問題 （ Maximum Clique Problem） ? 頂點覆蓋問題 （ Vertex Cover Problem） ? 子集和問題 （ Sum of Subset Problem） ? 哈密頓回路問題 （ Hamiltonian Cycle Problem） 2021/11/10 43 of 158 計算復(fù)雜性理論基礎(chǔ) ? P類問題和 NP問題 ? 大規(guī)模 NP完全 問題解決方法 ? 近似算法，隨機算法 …… ? 量子計算機， DNA計算機 2021/11/10 44 of 158 作業(yè)安排問題 ?設(shè)有 q個完全相同的處理器： m1,m2,,mq, 處理 n個彼此無關(guān)的作業(yè)： j1,j2,,jn,所需時間分別為： t1,t2,,tn,要求最后全部結(jié)束的時間最短。 ?近似算法 A1:對時間序列進行排序，假定 t1 ≥ t2≥ ≥ tn 此順序也就是處理的先后順序。即當某個處理器空閑時，立即處理剩下需要處理的時間最長的作業(yè)。 2021/11/10 45 of 158 作業(yè)安排問題續(xù) ?例：設(shè)q=3 ,n=6 ,t1=10 ,t2=9 ,t3=8 t4=7 ,t5=6 ,t6=5 m1 m2 m3 10 9 8 15 15 15 處理順序： Q=( j1,j2, j3, j4, j5, j6) 2021/11/10 46 of 158 ? 例：設(shè) q=2 ,n=5 ,t1=3 ,t2=3 ,t3=2 t4=2 ,t5=2 m1 m2 5 3 7 5 3 m1 m2 6 2 6 4 3 即 T1=7,處理順序： Q1= ( j1,j2,j3,j4,j5 ) T2=6,處理順序： Q2= ( j1,j3,j4,j2,j5 ) 2021/11/10 47 of 158 改進算法 A2: ?假定已經(jīng)排序的 t1 ≥ t2≥ ≥ tn ,確定整數(shù) k,先對前 k個作業(yè)求最優(yōu)安排，然后對后nk個作業(yè)應(yīng)用算法 A1 2021/11/10 48 of 158 頂點覆蓋問題 ?設(shè)有圖 G=V,E,V39。是 V的子集，若 G中任意一條邊都至少有一個頂點在 V39。中，則稱 V39。是 G的一個頂點覆蓋集即：任給圖 G=V,E及正整數(shù) k≤|V|,是否存在 k個頂點的頂點覆蓋集。 1 2 4 3 6 5 7 2021/11/10 49 of 158 對同學(xué)們的期望 不碰 NP 少拍 MP
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1