Nowusethefirst-fitalgorithmFirst-FitDecreasing演算法 - 副本.pptVIP

裝箱問題的策略：小結 上述策略屬於「貪婪演算法」(greedy method) 根據近期而非長期考量作出選擇 直觀而言，同學可能認為first-fit策略能得到更好的結果，然實際上，它們的效能相當接近 已可證明：FFD解決方案在最壞的情況為最佳解決方案的22% 在實務上，FFD解決方案通常比22%的上界更接近最優 結論：只需一個簡單的經驗法則，即能得到近似最佳解 反思 FFD把物件由大到小排列，可否先把物件從小到大排序，再執行First-fit擺法呢？ http://bit.ly/2qmbNgA * 二維裝箱(2D Bin Packing)問題 問題陳述 Given a set of rectangular objects (wi,hi), 0≤i≤n and finite rectangular bins with width W and height H, the objective of a 2D bin packing problem is to minimize the number of the used bins such that all rectangles can be packed into the used bins (and all the rectangles have a fixed packing direction.) 解題策略？ * * 二維裝箱問題 vs. 充分利用渡輪內空間擺放運送物 * 「裝箱問題」在作業系統內亦有類似的考量 * 目標 剩餘空間越少越好 當程式能被CPU執行之前，作業系統需將其載入記憶體以利CPU存取 隨著之前的程式啟動與結束，原先程式佔用的記憶體空間逐漸形成不連續的片段區塊(破洞，hole) 配置策略: first fit、best fit與next fit Allocating a 16MBblock using … 「裝箱問題」在作業系統內亦有類似的考量 * 哪一種配置策略的效能較佳？ 諾亞的貝果問題Noah’s Bagels Problem 諾亞的貝果問題 原文：http://www.cs.technion.ac.il/~hadas/PUB/fun98.pdf 問題陳述 諾亞是貝果(bagel)商人，擁有多家烘培坊，需決定旗下每家麵包店生產不同風味的貝果數量 貝果的生產受制於店內空間、原料、不同口味受顧客歡迎的程度 目標：找到最大限度地提高收入的解決方案(收入問題)，同時保證他的顧客滿意(平衡問題) 重要結果 為「裝箱問題」的變形 「收入問題」與「平衡問題」均被證明為NP-hard 在某些條件下，每個問題存在多項式時間內可找得最佳解決方案 * 方程式化(Formulation) (1/3) {b1, b2,…, bN}: N家烘培坊 {f1, f2,…, fF}: F種口味 Qi: 烘培坊bi每日生產貝果的最大數目 (最大產量) 每日生產貝果的最大總量 Q = Q1 + Q2 +…+ QN Ci: 烘培坊bi的櫥櫃數(生產貝果所需的原料存量) pi :口味fi受顧客歡迎的程度(比例) 決定每一家烘培坊bi需生產口味fi的貝果數為多少 以二個 矩陣描述：櫥櫃矩陣A、貝果分派矩陣B * 方程式化 (2/3) 以二個 矩陣描述：櫥櫃矩陣A、貝果分配矩陣B 口味fi的原料存於烘培坊bj之中 :口味fi的貝果由烘培坊bj生產的個數 :口味fi的貝果被所有店家生產的總數 矩陣A、B滿足： 收入問題 (Revenue problem) 給定N, F, p1,…, pF, Q1,…,QN及C1,…CN，找到指派矩陣A、B使得 * 最大化 Wj為pi?Q取整數且 方程式化 (3/3) 平衡問題 (Balance problem) 給定N, F, p1,…, pF, Q1,…,QN及C1,…CN，找到指派矩陣A、B使得 找到完美的指派使得收入最大且平衡最佳 (e = 0) MOD (multimedia-on-demand) 中央處理器和N個共享硬碟組成的系統，可依客戶需求同時撥放多個不同串流的影片 F部影片{f1, f2,…,fF}，每個影片的熱門度pi， 磁碟j播送容量限制Qj (同時可撥放的影片數) 磁碟j儲存空間的限制Cj (最多能存放的影片數) 決定哪些影片(副本)放置於哪些磁碟，能滿足熱門度需求且同時播送的個數最大 * 且 e 最小 最大收入 vs. 最大平衡 * C1=2 Q1 =