第4章-貪心算法-作業(yè)

課后練習(xí)：算法分析題算法分析題4-6（教材第128頁）：字符a~h出現(xiàn)的頻率恰好是前8個Fibonacci數(shù)，它們的哈夫曼編碼是什么？解答：Fibonacci數(shù)列前8個Fibonacci數(shù)為：1,1,2,3,5,8,13,21,……則a,b,c,d,e,f,g,h這8個字符出現(xiàn)的次數(shù)依次為：1,1,2,3,5,8,13,21次。以此構(gòu)造一顆Huffman樹（不唯一）如右：11224375128132021335400000001111111對應(yīng)的Huffman編碼為：a:0011100b:0011101c:001111d:00110e:0010f:000g:01h:1課后練習(xí)練習(xí)2：假設(shè)有25分、10分、5分和1分四種硬幣，需要找給顧客2元5角錢，請問用貪心算法可以求出何種找零方案？該方案是最優(yōu)的么？為什么？解答：2元5角=250分，按照貪心算法（盡量用面值大的硬幣找零），則需要25分硬幣10個即可。該算法是最優(yōu)的，因為五種硬幣的面值中5分是25分和10分的約數(shù)（因數(shù)）。課后練習(xí)練習(xí)3：活動安排問題。假設(shè)有9個活動申請使用1個會議室，每個活動的開始時間和終止時間如下。用貪心算法設(shè)計一個活動安排表，要求要盡可能的多安排活動。會議室不允許被多個活動同時占用。

活動序號123456789起始時間2125746815結(jié)束時間558101113152224活動序號123456789起始時間2125746815結(jié)束時間558101113152224根據(jù)貪心算法，第1個被安排的活動為1號活動，因為它的結(jié)束時間（時刻5）最早。（貪心選擇性質(zhì)）然后每次都選取起始時間最接近于上一次活動的結(jié)束時間的活動，所以分別依次選擇4號活動（時刻10結(jié)束）、9號活動（時刻24結(jié)束），則最優(yōu)解為：(1,4,9)。顯然，最優(yōu)解不唯一，比如：(2,4,9)。但顯然，用貪心策略求出的可行解是最優(yōu)的。課后練習(xí)練習(xí)4：單源最短路徑問題。求下面連通圖中從源頂點(diǎn)v0到其它各頂點(diǎn)的最短路徑。①列出源頂點(diǎn)到其它頂點(diǎn)的最短路徑長度和路徑中頂點(diǎn)序列。②證明該算法的正確性。迭代Sudist[1]dist[2]dist[3]dist[4]初始{0}-10maxint301001{0,1}11060301002{0,1,3}3105030903{0,1,3,2}2105030604{0,1,3,2,4}410503060算法正確性證明：教材114頁-115頁課后練習(xí)練習(xí)5：最小生成樹問題。①用Prim或者Kruskal算法求出下圖中的最小生成樹。②證明該算法的正確性。（教材116頁）V1V2V4V3V5V66352365154課后練習(xí)Kruskal算法：V1V2V4V3V5V66352365154V1V2V4V3V5V632314Prim算法：V1V2V4V3V5V66352365154V1V3V6V4V5V2練習(xí)6：一隊徒步旅行者要從A地到B地，兩地間距離為L公里。他們每天最多可以走d公里（與地形、天氣條件等無關(guān)），中間需要就地宿營。假定這些潛在的宿營地點(diǎn)位于起點(diǎn)A地的距離為x1,x2,……,xn的地方，顯然它們之間的距離小于等于d，稱這些地點(diǎn)（停止點(diǎn)）是有效的。于是，一組停止點(diǎn)是有效的，如果人們只能在這些地方宿營并且仍舊能順利完成旅行。則必須假設(shè)n個停止點(diǎn)所組成的集合都是有效的；否則就沒法走完整個路程。問題1：假設(shè)兩地距離為100公里，潛在的宿營地點(diǎn)為{6,14,30,37,48,65,73,76,88,90,94}。旅行者每天最多走18公里。給出最優(yōu)（最少）的有效宿營地組合（最少幾天能走完）。問題2：證明該算法的正確性（解的最優(yōu)）。課后練習(xí)問題1：假設(shè)兩地距離為100公里，潛在的宿營地點(diǎn)為{6,14,30,37,48,65,73,76,88,90,94}。旅行者每天最多走18公里。給出最優(yōu)（最少）的有效宿營地組合（最少幾天能走完）。解答：根據(jù)貪心算法，潛在的宿營地點(diǎn)的選取應(yīng)該遵循每天盡量多走（但不多于18公里）的原則，以期用最短的時間走完100公里的行程。143048657694源點(diǎn)A地目的點(diǎn)B地需要7天才能走完，這與[100/18]+1=6結(jié)果符合！課后練習(xí)問題2：證明該算法的正確性（解的最優(yōu)）。解答：這個策略有可能是無效的么？一個想法：該算法能否保證某一天提早停止就使后面一些天的宿營地點(diǎn)同步提前。有沒有可能真存在一個解，它故意落在貪心解的后面，然后突然加速并且越過貪心解？在給出貪心解每天旅行盡可能遠(yuǎn)的條件下，它怎樣越過貪心解？課后練習(xí)設(shè)R={xp1,…,xpk

}表示由貪心算法選擇的停止點(diǎn)的集合，根據(jù)反證法，假設(shè)存在一個更小的停止點(diǎn)的有效集合：把這個較小的集合稱為S={xq1,…,xqm

}，顯然此時m＜k。證明I：貪心算法在每一天到達(dá)的停止點(diǎn)j比在其它解下到達(dá)的停止點(diǎn)更遠(yuǎn)，即：對每個j=1,2,…,m，有xpj≥xqj證明I：貪心算法在每一天到達(dá)的停止點(diǎn)j比在其它解下到達(dá)的停止點(diǎn)更遠(yuǎn)，即：對每個j=1,2,…,m，有xpj≥xqj證：j=1的情況直接從貪心算法的定義得出：旅行者第1天在停止之前走得盡可能遠(yuǎn)?，F(xiàn)在令j>1并且假設(shè)這個斷言對所有的i<j為真，那么xqj

–xqj-1≤d因為S是停止點(diǎn)的有效集合，且根據(jù)歸納假設(shè)，由xpj-1≥xqj-1

有：xqj

–xpj-1≤

xqj

–xqj-1

由此可以推得：xqj

–xpj-1≤d，即旅行者能夠選擇在1天之內(nèi)走完從xpj-1到xqj的所有路程；因此他們最后停留的宿營地xpj只能比xqj更遠(yuǎn)。命題得證!由上述命題（已證明），推出xpm≥xqm

式①?，F(xiàn)在m<k，那么一定有：xpm<L–d式②

，否則旅行者不必停在xpm+1。把兩式組合可得：xqm<L–d

；但這與假設(shè)S是一個有效的停止點(diǎn)集合相矛盾。從而，不可能有m<k，即存在一個更小的停止點(diǎn)的有效集合（較小的集合）S={xq1,…,xqm

}的假設(shè)是不成立的！所以貪心算法產(chǎn)生一個最小的有效停止點(diǎn)集合得