算法合集之對擬陣的初步研究(編輯修改稿)
2024-11-12 03:11 本頁面
【文章內(nèi)容簡介】 貪心算法 Greedy(M,w) A := 空集 根據(jù) w按遞減順序對 S排序 for 每個 Sx? 根據(jù)權 ? ?xw 的遞減順序 do if ( ? ? LxA ?? ) then ? ?xAA ??:return A 時間復雜度 排序 ? ?nn lo g?若判斷需 ? ?? ?nf?總復雜度 ? ?? ?nfnnn ??? lo g貪心 ? ?n? 次判斷 正確性證明 ? 只需證明在算法的每一步 A都是某個最優(yōu)解的子集，那么當算法結束時 A就是一個最優(yōu)解 ? 運用歸納思想 ? 歸納基礎 :初始時 A為空 ,滿足要求 ? 歸納 :只需證明一個最優(yōu)解的子集 A經(jīng)過一次循環(huán)后仍滿足要求 . T A T A =A∪ {x} X 能使 A擴展 的最大元素 y T =T{y}+{x} w(y) ≤w(x) w(T ) ≥w(T) T ′ ′ ′ ′ ′ 第三部分 任務調(diào)度問題 問題提出 S: 調(diào)度 : 0 1 2 3 4 5 ?給定一個單
教學課件相關推薦
鄂ICP備17016276號-1