《烙餅問(wèn)題》朱瑞勇課件

《烙餅問(wèn)題》朱瑞勇課件xx年xx月xx日目錄contents烙餅問(wèn)題的引入烙餅問(wèn)題的數(shù)學(xué)模型烙餅問(wèn)題的算法設(shè)計(jì)烙餅問(wèn)題的程序?qū)崿F(xiàn)烙餅問(wèn)題的擴(kuò)展烙餅問(wèn)題的應(yīng)用舉例烙餅問(wèn)題的引入01烙餅是人們經(jīng)常遇到的問(wèn)題之一，例如在餐館、食堂和家庭中。烙餅問(wèn)題的研究可以追溯到數(shù)學(xué)文化中的“中國(guó)烙餅問(wèn)題”和“外國(guó)烙餅問(wèn)題”。問(wèn)題背景烙餅問(wèn)題指的是這樣一個(gè)問(wèn)題：給定一定數(shù)量的烙餅，每次烙一張，每烙一次需要一定的時(shí)間，如何烙餅才能使總時(shí)間最短。烙餅問(wèn)題可以簡(jiǎn)化為求解最優(yōu)解問(wèn)題，即尋找最優(yōu)烙餅方案，使得烙餅的總時(shí)間最短。烙餅問(wèn)題的定義烙餅問(wèn)題是一種常見(jiàn)的最優(yōu)決策問(wèn)題，它涉及到在有限的資源約束下做出最優(yōu)的決策。烙餅問(wèn)題的解決方法可以應(yīng)用于其他類(lèi)似的問(wèn)題，如生產(chǎn)計(jì)劃、物流調(diào)度等。通過(guò)對(duì)烙餅問(wèn)題的研究，可以更好地理解這些問(wèn)題的內(nèi)在規(guī)律和最優(yōu)決策方法。烙餅問(wèn)題的重要性烙餅問(wèn)題的數(shù)學(xué)模型02問(wèn)題描述將n個(gè)餅(每次只能烙一個(gè)餅的一面)放入烙鍋中，每面需烙t時(shí)間，求烙完所有餅所需總時(shí)間。假設(shè)每個(gè)餅的兩面都要烙熟模型建立思路：每次烙一個(gè)餅的一面，直到所有餅都烙熟步驟將第1個(gè)餅烙熟將第2個(gè)餅烙熟...n.將第n個(gè)餅烙熟時(shí)間復(fù)雜度：O(nt)模型求解應(yīng)用場(chǎng)景可以用來(lái)求解類(lèi)似問(wèn)題，如排隊(duì)買(mǎi)票、加油站排隊(duì)等注意事項(xiàng)需要考慮每個(gè)餅之間是否有時(shí)間間隔，以及每個(gè)餅的初始狀態(tài)是否一樣模型應(yīng)用烙餅問(wèn)題的算法設(shè)計(jì)03每次烙一張餅，直到所有餅都烙完。為了使烙餅所用的時(shí)間最少，我們總是先烙編號(hào)為奇數(shù)的餅，再烙編號(hào)為偶數(shù)的餅。貪心算法思路貪心算法的時(shí)間復(fù)雜度為O(n)，其中n為烙餅的總數(shù)。時(shí)間復(fù)雜度貪心算法設(shè)計(jì)動(dòng)態(tài)規(guī)劃思路將問(wèn)題劃分為子問(wèn)題，每個(gè)子問(wèn)題都求解最優(yōu)解，最終得到原問(wèn)題的最優(yōu)解。狀態(tài)定義設(shè)f[i][j]表示前i張餅中，前j個(gè)鍋所能烙下的最小時(shí)間。狀態(tài)轉(zhuǎn)移方程如果第i張餅與前j個(gè)鍋都無(wú)法匹配，則f[i][j]=f[i-1][j]；否則，f[i][j]=min(f[i-1][j],f[i-1][j-1]+3)。時(shí)間復(fù)雜度動(dòng)態(tài)規(guī)劃的時(shí)間復(fù)雜度為O(n^2)。動(dòng)態(tài)規(guī)劃算法設(shè)計(jì)01020304分治策略將烙餅問(wèn)題劃分為兩個(gè)子問(wèn)題，分別求解奇數(shù)編號(hào)的餅和偶數(shù)編號(hào)的餅所需的最小時(shí)間，最后取兩個(gè)子問(wèn)題的最小值即為原問(wèn)題的最優(yōu)解。分治算法思路將原問(wèn)題劃分為多個(gè)子問(wèn)題，求解子問(wèn)題的最優(yōu)解，最終得到原問(wèn)題的最優(yōu)解。時(shí)間復(fù)雜度分治算法的時(shí)間復(fù)雜度為O(nlogn)。分治算法設(shè)計(jì)烙餅問(wèn)題的程序?qū)崿F(xiàn)04貪心算法思路：從第一個(gè)餅開(kāi)始烙起，每次烙兩個(gè)餅，每烙一次收取一個(gè)餅的費(fèi)用，直到所有餅都烙完。算法步驟1.將n個(gè)餅放入一個(gè)棧中。2.從棧中取出兩個(gè)相鄰的餅，將它們翻轉(zhuǎn)并放入棧底。3.重復(fù)步驟2，直到棧中只剩下一個(gè)餅。4.計(jì)算烙餅的總次數(shù)和總費(fèi)用。貪心算法程序?qū)崿F(xiàn)動(dòng)態(tài)規(guī)劃思路：將問(wèn)題拆分為多個(gè)子問(wèn)題，每個(gè)子問(wèn)題都是求解烙n-1個(gè)餅的最小費(fèi)用，最終得到烙n個(gè)餅的最小費(fèi)用。算法步驟1.定義dp[i]表示烙i個(gè)餅的最小費(fèi)用。2.初始化dp數(shù)組為正無(wú)窮大，dp[0]=0。3.對(duì)于i=1到n，根據(jù)狀態(tài)轉(zhuǎn)移方程計(jì)算dp[i]的值。4.輸出dp[n]。動(dòng)態(tài)規(guī)劃算法程序?qū)崿F(xiàn)分治算法思路：將原問(wèn)題拆分為多個(gè)子問(wèn)題，每個(gè)子問(wèn)題求解烙m個(gè)餅的最小費(fèi)用，再將子問(wèn)題的解合并得到原問(wèn)題的解。算法步驟1.定義函數(shù)f(n,m)，其中n表示總餅數(shù)，m表示每次烙的餅數(shù)。2.遞歸調(diào)用f(n,m)函數(shù)，其中m從1到n/2。3.在f(n,m)函數(shù)中，分別計(jì)算烙m個(gè)餅和烙(n-m)個(gè)餅的最小費(fèi)用，再將它們相加得到烙n個(gè)餅的最小費(fèi)用。4.將f(n,m)函數(shù)的返回值存儲(chǔ)在一個(gè)二維數(shù)組中，最終得到烙n個(gè)餅的最小費(fèi)用。分治算法程序?qū)崿F(xiàn)烙餅問(wèn)題的擴(kuò)展05問(wèn)題描述假設(shè)有一個(gè)烙餅機(jī)，每次只能烙一個(gè)餅，每烙一次餅需要的時(shí)間為t，現(xiàn)在有n個(gè)餅需要烙制，那么烙制完所有餅需要的最短時(shí)間為多少？解決方案可以采用貪心算法，將所有餅按照需要烙制的時(shí)間從大到小排序，然后依次將每個(gè)餅烙制完成，這樣可以使總時(shí)間最小。多重烙餅問(wèn)題VS現(xiàn)在來(lái)考慮一個(gè)更復(fù)雜的問(wèn)題：烙制不同形狀的餅干。假設(shè)有k種不同形狀的餅干，每種形狀的餅干需要的烙制時(shí)間不同，而且烙制不同形狀的餅干的時(shí)間是相互獨(dú)立的。現(xiàn)在有n個(gè)餅干需要烙制，那么如何安排烙制順序可以使總時(shí)間最??？解決方案可以采用貪心算法，將所有餅干按照需要烙制的時(shí)間從大到小排序，然后依次將每個(gè)餅干烙制完成，這樣可以使總時(shí)間最小。問(wèn)題描述異形烙餅問(wèn)題問(wèn)題描述雖然貪心算法可以解決烙餅問(wèn)題，但是它并不能保證在所有情況下都能得到最優(yōu)解。因此，我們還需要研究其他算法來(lái)解決烙餅問(wèn)題。解決方案可以采用動(dòng)態(tài)規(guī)劃算法來(lái)解決烙餅問(wèn)題。將烙餅問(wèn)題轉(zhuǎn)化為一個(gè)動(dòng)態(tài)規(guī)劃問(wèn)題，通過(guò)計(jì)算最優(yōu)解的狀態(tài)轉(zhuǎn)移方程，得到所有餅的最優(yōu)烙制順序。烙餅問(wèn)題的其他優(yōu)化算法烙餅問(wèn)題的應(yīng)用舉例06在烙餅問(wèn)題中，除了探討最優(yōu)烙餅策略外，還可以進(jìn)一步討論在更復(fù)雜情況下的烙餅問(wèn)題，如烙餅次數(shù)最少、時(shí)間最短等問(wèn)題。烙餅問(wèn)題的引申通過(guò)建立數(shù)學(xué)模型，可以更好地理解和解決烙餅問(wèn)題。例如，將烙餅問(wèn)題轉(zhuǎn)化為“背包問(wèn)題”等優(yōu)化問(wèn)題，進(jìn)而采用動(dòng)態(tài)規(guī)劃、貪心算法等求解方法。數(shù)學(xué)建模應(yīng)用舉例一類(lèi)似問(wèn)題的拓展除了烙餅問(wèn)題外，還有類(lèi)似的最小生成樹(shù)、旅行商問(wèn)題等優(yōu)化問(wèn)題。這些問(wèn)題的求解方法與烙餅問(wèn)題類(lèi)似，可以通過(guò)擴(kuò)展結(jié)點(diǎn)、刪除邊等技巧求解。算法比較對(duì)于類(lèi)似的問(wèn)題，可以比較不同的算法在不同情況下的表現(xiàn)。例如，在求解最小生成樹(shù)時(shí)，可以比較Prim算法和Kruskal算法在不同情況下的優(yōu)劣。應(yīng)用舉例二實(shí)際應(yīng)用烙餅問(wèn)題在實(shí)際生活中有著廣泛的應(yīng)用。例如，在物流領(lǐng)域中，可以應(yīng)用烙餅問(wèn)題的思想來(lái)解決車(chē)輛路徑優(yōu)化問(wèn)題；在金融領(lǐng)