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