典型應(yīng)用:優(yōu)化問題.? 一旦選中,便永遠選定.
缺點:實際中很多問題無法用此算法解決.
Demo 1:找零.
這個我想大家都學過,我就不寫了.
Demo 2: 日程安排.
2種情況,? 1:最小化任務(wù)的執(zhí)行時間
???????????????? 2:最大化收益.
我在這里說說最小化平均時間的算法.思路:每一步,從剩余的顧客中選出時間最少的顧客加到日程安排表里.
前提:顧客數(shù)量固定,每個顧客所需要的時間知道
算法:把顧客按照所需時間的升序排列.
下面證明此算法:?? 這個貪婪算法總是最優(yōu)的.
設(shè)P = p1,p2,p3.....pn 是從1到n的證書的任意一個排列,設(shè)si = tpi 如果顧客按照P 的順序進行排列,則第i個可戶所需的時間為si .顧客所需的總時間為: T(p) = s1 + (s1+s2) +(s1+s2s3)+..........
????????????????????????????????????????????????????????????????????????? =? ns1+(n-1)s2+(n-2)s3+...........
???????????如果P不是按照整數(shù)的升序進行的排列,那么可以找到2個整數(shù)a,b 使Sa?>Sb ,且a<b?
????????? 現(xiàn)在,我調(diào)換P中a,b的順序,則可求出另外一個總時間:T(p') = (n-a+1)Sb? + (n-b+1)Sa? +..........?其他的和T(P)一樣
??????????? T(p) -T(P')?> 0
???????????? 推出:可以改進任何一個日程表,只要其中有某個顧客的服務(wù)順序優(yōu)于另外一個所需要的時間更少的,如果全按照升序,則無法改進,證明的出算法正確.????????????????????????????????????????????????????