貪婪算法ppt課件(完整版)
【正文】 2022/5/31 11 算法的基本思路 ?從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。每步分配一件任務(wù)，且按照任務(wù)的 非遞減 順序進(jìn)行分配。 i++) t[i] = i。 IndirectListT::BubbleSort() { for (int i = length。 ? NetWork: 修改有向圖的基類函數(shù) LOGO 2022/5/31 45 bool Network::Topological(int v[]) { int n = Vertices()。 i++) { int u = Begin(i)。 while (!()) { int w。 delete [] InDegree。 while (u) { InDegree[u]。 for (i = 1。 i = n。 i)。 i++) if (*table[i] *table[i+1]) { Swap(table[i], table[i + 1])。 ?例如：機(jī)器調(diào)度算法 ?啟發(fā)式算法具有直覺傾向 ?近似算法：具有限定功能的啟發(fā)式算法 LOGO 2022/5/31 29 應(yīng)用 1：貨箱裝船 LOGO 2022/5/31 30 ?假設(shè) n=8, c=400 ?[w1 , ... w8 ]=[100, 200, 50, 90, 150, 50, 20, 80] ?利用貪婪算法時(shí)，所考察貨箱的順序?yàn)?, 3 , 6 , 8 , 4 , 1 , 5 , 2。令 Xi為嬰兒將要引用的第i種飲料的量，需要解決的問題是：找到一組實(shí)數(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 最小代價(jià)通訊網(wǎng)絡(luò) 最小耗費(fèi)生成樹 LOGO 2022/5/31 18 ?最小代價(jià)生成網(wǎng)絡(luò) 求解：選擇一個(gè)無向圖中的邊集合的子集 這個(gè)子集必須具備如下： 限制條件：所有的邊構(gòu)成一個(gè)生成樹 優(yōu)化函數(shù)：子集中所有邊的權(quán)值之和 LOGO 2022/5/31 19 ?在貪婪算法（ greedy method）中采用逐步構(gòu)造最優(yōu)解的方法。 貪婪算法的基本思路如下： 。 。
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1