算法優(yōu)化策略ppt課件(編輯修改稿)
2025-05-26 02:45 本頁面
【文章內(nèi)容簡介】 ramming所需的計算時間為 ? ?)()),1(),(()1,(),1(12101010 1nOnOrsnrnsrnOriisriisOnrnrnrrni?????????????????????????????????? ?????????13 問題的算法特征 14 貪心策略 ?采用每次合并集裝箱數(shù)最少的相鄰 2堆貨物的貪心策略，并不能得到最優(yōu)解。 ?適當(dāng)放松相鄰性約束，引入相容結(jié)點對概念。如圖，原始結(jié)點用方形結(jié)點表示，合并生成的結(jié)點用圓形結(jié)點表示。 ?最小相容結(jié)點對 a[i]和 a[j] 是滿足下面條件的結(jié)點對： （ 1）結(jié)點 a[i]和 a[j] 之間沒有方形結(jié)點； （ 2）在所有滿足條件（ 1）的結(jié)點中 a[i]+a[j]的值最??； （ 3）在所有滿足條件（ 1）和（ 2）的結(jié)點中下標(biāo) i 最小； （ 4）在所有滿足條件（ 1）（ 2）和（ 3）的結(jié)點中下標(biāo) j 最小。 ?相應(yīng)的最小相容合并樹，如圖所示。 15 相同層序定理 相同層序定理 ：存在貨物儲運問題的最優(yōu)合并樹，其各原始結(jié)點在最優(yōu)合并樹中所處的層序與相應(yīng)的原始結(jié)點在相容合并樹中所處的層序相同。 根據(jù)上述定理，容易從各原始結(jié)點在相容合并樹中所處的層序構(gòu)造出相應(yīng)的最優(yōu)合并樹，如圖所示。 16 算 法 1. 組合階段 : 將給定的 n個數(shù)作為方形結(jié)點依序從左到右排列，a[1]， a[2]， … ， a[n]。反復(fù)刪除序列中最小相容結(jié)點對 a[i]和 a[j]，(ij)，并在位置 i處插入值為 a[i]+a[j]的圓形結(jié)點，直至序列中只剩下 1個結(jié)點。 O(nlogn) 2. 標(biāo)記層序階段 : 將第一階段結(jié)束后留下的惟一結(jié)點標(biāo)記為第 0層結(jié)點。然后以與第一階段相反的組合順序標(biāo)記其余結(jié)點的層序。 O(n) 3. 重組階段 : 根據(jù)標(biāo)記層序階段計算出的各結(jié)點的層序，按下述規(guī)則重組。 O(n) 結(jié)點 a[i]和 a[j]重組為新結(jié)點應(yīng)滿足： （ 1） a[i]和 a[j]在當(dāng)前序列中相鄰； （ 2） a[i]和 a[j]均為當(dāng)前序列中最大層序結(jié)點； （ 3）在所有滿足條件（ 1）和（ 2）的結(jié)點中，下標(biāo) i 最小。 17 優(yōu)化數(shù)據(jù)結(jié)構(gòu) 18 帶權(quán)區(qū)間最短路問題 S是直線上 n個帶權(quán)區(qū)間的集合。從區(qū)間 I?S到區(qū)間 J?S的一條路是 S的一個區(qū)間序列 J(1)， J(2)， … ， J(k)，其中 J(1) = I， J(k) = J，且對所有 1? i ? k1, J(i)與 J(i+1)相交。這條路的長度定義為路上各區(qū)間權(quán)之和。在所有從 I到 J的路中，路長最短的路稱為從 I到 J的最短路。 帶權(quán)區(qū)間圖的單源最短路問題要求計算從 S中一個特定的源區(qū)間到 S中所有其他區(qū)間之間的最短路。 區(qū)間集 S(i)的擴展 定義為： S(i)?T，其中 T是滿足下面條件的另一區(qū)間集。 T中任意區(qū)間 I=[a,b]均有 bb(i)。 設(shè)區(qū)間 I(k)( k?i )是區(qū)間集 S(i)中的一個區(qū)間， 1? i ? n。如果對于S(i)的任意擴展 S(i)?T，當(dāng)區(qū)間 J?T且在 S(i)?T中有從 I(1)到 J的路時，在 S(i)?T中從 I(1)到 J的任一最短路都不含區(qū)間 I(k)，則稱區(qū)間 I(k)是 S(i)中的 無效區(qū)間 。若 S(i)中的區(qū)間 I(k)不是無效區(qū)間則稱其為 S(i)中的 有效區(qū)間 。 19 帶權(quán)區(qū)間最短路問題 性質(zhì) 1： 區(qū)間 I(k)是 S(i)中的有效區(qū)間，則對任意 k?j?i，區(qū)間 I(k)是 S(j)中的有效區(qū)間。另一方面，若區(qū)間 I(k)是 S(i)中的無效區(qū)間，則對任意 ji，區(qū)間 I(k)是 S(j)中的無效區(qū)間。 性質(zhì) 2： 集合 S(i)中所有有效區(qū)間的并覆蓋從 a(1)到 b(j)的線段，其中 b(j)是 S(i)的最右有效區(qū)間的右端點。 性質(zhì) 3： 區(qū)間 I(i)是集合 S(i)中的有效區(qū)間當(dāng)且僅當(dāng)在 S(i)中有一條從 I(1)到 I(i)的路。 性質(zhì) 4： 當(dāng) ik且 dist(i,i)dist(k,i)時， I(k)是 S(i)中的無效區(qū)間。 性質(zhì) 5： 設(shè) I(j(1))， I(j(2))， … ， I(j(k))是 S(i)中
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1