計算機算法設(shè)計與分析(第6版)-課件 ch0305多邊形游戲算法_第1頁
計算機算法設(shè)計與分析(第6版)-課件 ch0305多邊形游戲算法_第2頁
計算機算法設(shè)計與分析(第6版)-課件 ch0305多邊形游戲算法_第3頁
計算機算法設(shè)計與分析(第6版)-課件 ch0305多邊形游戲算法_第4頁
計算機算法設(shè)計與分析(第6版)-課件 ch0305多邊形游戲算法_第5頁
已閱讀5頁,還剩14頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

多邊形游戲算法LET'SEMBARKONTODAY'SSHARINGJOURNEYTOGETHER01問題定義與背景

Let'sembarkontoday'sjourneyofsharingandcommunicationtogether多邊形游戲的規(guī)則與目標(biāo)游戲基本設(shè)定多邊形游戲是一個單人游戲,初始時有一個由n個頂點構(gòu)成的多邊形。每個頂點被賦予一個整數(shù)值,每條邊被賦予一個運算符“+”或“*”。游戲的目標(biāo)是通過一系列操作,最終得到一個頂點,其數(shù)值即為游戲得分。操作步驟游戲開始時刪除一條邊,隨后在n?1步中,每次選擇一條邊及其連接的兩個頂點,用新頂點取代它們,并將這兩個頂點的值通過邊上的運算符計算后賦予新頂點。游戲目標(biāo)游戲的最終目標(biāo)是最大化剩余頂點的數(shù)值。這需要在所有可能的邊刪除順序中,找到使最終得分最高的策略。問題建模與關(guān)鍵難點問題建模將多邊形游戲抽象為數(shù)學(xué)模型,頂點序列v[i]與運算符序列op[i]交替排列,形成環(huán)形結(jié)構(gòu)。游戲的目標(biāo)轉(zhuǎn)化為在所有可能的合并順序中,找到使最終得分最大的策略。關(guān)鍵難點難點在于環(huán)形結(jié)構(gòu)帶來的邊界處理問題,以及運算符“*”對負(fù)數(shù)的非單調(diào)性。此外,為了求解最大值,還需要同時記錄最小值,這增加了問題的復(fù)雜性。02最優(yōu)子結(jié)構(gòu)剖析Let'sembarkontoday'sjourneyofsharingandcommunicationtogether鏈?zhǔn)椒指钆c最優(yōu)性傳遞鏈?zhǔn)椒指钭顑?yōu)性傳遞定義順時針鏈p(i,j),表示從頂點i開始、包含j個頂點的連續(xù)段。若最后一次合并發(fā)生在op[i+s],則鏈被分割為子鏈p(i,s)與p(i+s,j-s)。通過分析“+”與“*”兩種運算對極值的影響,論證主鏈的最優(yōu)性依賴于子鏈的最優(yōu)性。無論運算符為何種類型,主鏈的極值均可由子鏈的極值得到。當(dāng)op[i+s]為“+”時,主鏈的極值等于子鏈極值之和。即最小值為兩個子鏈最小值之和,最大值為兩個子鏈最大值之和。加法運算規(guī)律當(dāng)op[i+s]為“*”時,主鏈的極值由子鏈極值的四種乘積(ac,ad,bc,bd)中的最小值和最大值決定。乘法運算規(guī)律由于頂點值可能為負(fù),乘法運算下最小乘積可能成為全局最大值。因此,必須同時存儲子鏈的最大值和最小值,以確保正確計算主鏈的極值。負(fù)值的影響03動態(tài)規(guī)劃狀態(tài)設(shè)計Let'sembarkontoday'sjourneyofsharingandcommunicationtogether三維狀態(tài)定義與含義01定義狀態(tài)m[i,j,0]表示鏈p(i,j)合并后的最小值,m[i,j,1]表示最大值。其中i為起始頂點編號,j為鏈長度,第三維區(qū)分極值類型。狀態(tài)定義02狀態(tài)覆蓋所有可能的子鏈,通過環(huán)形取模處理i+s>n的邊界情況,確保狀態(tài)定義的完整性和一致性。狀態(tài)覆蓋范圍03狀態(tài)設(shè)計同時記錄最小值和最大值,確保后續(xù)遞推的正確性與完備性,為動態(tài)規(guī)劃算法的實現(xiàn)提供基礎(chǔ)。狀態(tài)設(shè)計的必要性邊界條件與初始化初始狀態(tài)當(dāng)鏈長度j=1時,無合并發(fā)生,m[i,1,0]=m[i,1,1]=v[i]。即每個頂點的初始值為其自身的數(shù)值。邊界處理在環(huán)形結(jié)構(gòu)中,當(dāng)i+s>n時,通過取模操作將頂點編號正確映射回1~n范圍,避免數(shù)組越界或邏輯錯誤。04遞推關(guān)系與算法實現(xiàn)Let'sembarkontoday'sjourneyofsharingandcommunicationtogetherMinMax函數(shù):單點合并計算010203函數(shù)職責(zé)運算符處理子鏈定位MinMax函數(shù)用于計算在op[i+s]處合并后的極值。根據(jù)給定的i、s、j,確定合并后的最小值和最大值。函數(shù)內(nèi)部根據(jù)運算符類型執(zhí)行不同的邏輯。若為加法,直接計算和;若為乘法,枚舉四種乘積并取極值。先定位右子鏈的起始頂點r,再根據(jù)運算符類型進(jìn)行計算。乘法情形下,通過比較四種乘積確定最終的極值。三重循環(huán)遞推框架PolyMax函數(shù)采用三重循環(huán)結(jié)構(gòu)。外層j從2到n遞增鏈長度,中層i從1到n枚舉起始頂點,內(nèi)層s從1到j(luò)-1枚舉分割點。01每次調(diào)用MinMax函數(shù)后,根據(jù)計算結(jié)果更新m[i,j,0]與m[i,j,1],確保每個狀態(tài)的值為所有可能分割中的最小值和最大值。

02狀態(tài)更新循環(huán)結(jié)構(gòu)環(huán)形枚舉與結(jié)果匯總環(huán)形枚舉由于多邊形為環(huán)形,需要枚舉首次刪除的邊。刪除第k條邊等價于將環(huán)拆成鏈p(k+1,n)。結(jié)果匯總算法通過計算m[i,n,1]對所有i取最大值,隱式覆蓋所有可能的首次刪除。最終結(jié)果存儲在變量temp中。全局最優(yōu)通過遍歷1~n,確保捕獲全局最優(yōu)解。這種枚舉方式保證了算法的完整性和正確性。01020305復(fù)雜度與拓展Let'sembarkontoday'sjourneyofsharingandcommunicationtogether時間復(fù)雜度算法的時間復(fù)雜度為O(n3)。狀態(tài)數(shù)為O(n2),每個狀態(tài)需O(n)次分割枚舉,總時間復(fù)雜度為O(n3)??臻g復(fù)雜度算法的空間復(fù)雜度為O(n2),需要存儲三維數(shù)組m,其中前兩維分別為頂點編號和鏈長度。效率優(yōu)勢與暴力枚舉的指數(shù)級復(fù)雜度相比,動態(tài)規(guī)劃算法顯著提高了效率。雖然常數(shù)優(yōu)化和滾動數(shù)組可以進(jìn)一步優(yōu)化,但三維狀態(tài)難以壓縮。時間復(fù)雜度與空間復(fù)雜度與凸多邊形三角剖分對比01相似之處多邊形游戲和凸多邊形最優(yōu)三角剖分問題都使用動態(tài)規(guī)劃求解,但子結(jié)構(gòu)不同。三角剖分僅求最大權(quán)值和,而游戲需同時維護(hù)最大與最小值。02不同之處三角剖分的運算固定為“+”,而游戲包含“*”運算,帶來非單調(diào)性。游戲問題的子結(jié)構(gòu)更具一般性,對負(fù)值和乘法運算的魯棒性要求更高。延伸應(yīng)用與開放問題若頂點值改為實數(shù)、運算符擴(kuò)展至“-”“/”或自定義二元函數(shù),狀態(tài)設(shè)計需調(diào)整。若多邊形帶權(quán)邊,可引入額外維度。算法

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論