《貪婪算法》ppt課件-文庫吧
2025-04-18 18:24 本頁面
【正文】 ?存在問題： ?； ?； ?。 LOGO 2022/5/31 12 最優(yōu)化問題的幾個概念 ?每個最優(yōu)化問題包含一組 限制條件 和一個優(yōu)化函數(shù) ?可行解 ：符合限制條件的問題求解方案 ?最優(yōu)解 ：使優(yōu)化函數(shù)取得最佳解的可行解 ?例如： Huffman樹，從可用的二叉樹中選取權(quán)重最小的兩棵子樹，進行合并 LOGO 2022/5/31 13 例 131 渴嬰問題 LOGO 2022/5/31 14 求解： 設(shè)各種飲料的滿意度已知。令 Xi為嬰兒將要引用的第i種飲料的量，需要解決的問題是：找到一組實數(shù)Xi（ 1=i=n）使?jié)M足 限制條件： 優(yōu)化函數(shù)： 注意：可行解、優(yōu)化解、無解的情況 iinii axtx ???????01及LOGO 2022/5/31 15 例 132 裝載問題 LOGO 2022/5/31 16 ?裝載問題 求解：找到一組變量 Xi，其可能取值為 0或 1，使它滿足 限制條件： 優(yōu)化函數(shù)： ??niix1LOGO 2022/5/31 17 例 133 最小代價通訊網(wǎng)絡(luò) 最小耗費生成樹 LOGO 2022/5/31 18 ?最小代價生成網(wǎng)絡(luò) 求解：選擇一個無向圖中的邊集合的子集 這個子集必須具備如下： 限制條件：所有的邊構(gòu)成一個生成樹 優(yōu)化函數(shù)：子集中所有邊的權(quán)值之和 LOGO 2022/5/31 19 ?在貪婪算法（ greedy method）中采用逐步構(gòu)造最優(yōu)解的方法。 ?在每個階段，都作出一個看上去最優(yōu)的決策（在一定的標準下）。決策一旦作出，就不再可更改。 ?作出貪婪決策的依據(jù)成為 貪婪準則 貪婪算法思想 LOGO 2022/5/31 20 ?貪心算法的基本思路如下： 1. 建立數(shù)學模型來描述問題 2. 把求解的問題分成若干個子問題 3. 對每一子問題求解，得到子問題的局部最優(yōu)解 4. 把子問題的解局部最優(yōu)解合成原來解問題的一個解 貪婪算法思想（續(xù) 1） LOGO 2022/5/31 21 ?實現(xiàn)該算法的過程： 從問題的某一初始解出發(fā)； while 能朝給定總目標前進一步 do 求出可行解的一個解元素； 由所有解元素組合成問題的一個可行解； 貪婪算法思想（續(xù) 2） LOGO 2022/5/31 22 例 134 找零錢問題 LOGO 2022/5/31 23 ?貪婪算法有一種 直覺 的傾向， ?例如：在找零錢時，直覺告訴我們應(yīng)使找出的硬幣數(shù)目最少（至少是接近最少的數(shù)目） LOGO 2022/5/31 24 例 135 機器調(diào)度問題 使用 7臺機器
教學課件相關(guān)推薦
鄂ICP備17016276號-1