第4章貪心算法1上海金融學院信息管理系

貪婪，我找不到更好的詞來描述，它就是好，它就是對，它就是高效。

——美國電影《華爾街》中的臺詞2上海金融學院信息管理系我們看一個找硬幣的例子。假設有四種硬幣，它們的面值分別為：2角5分，1角，5分，1分?，F(xiàn)在要找給顧客6角3分。怎樣找使得給顧客的硬幣最少。我們下意識地使用了這樣的找硬幣算法：首先選出一個不超過6角3分的最大硬幣，然后，從6角3分中減去，再在剩余的值中選出一個不超過該值的最大硬幣，如此反復，直到找夠為止。這個找硬幣的算法就是貪心選擇算法。如果上述問題改為：要找給顧客1角5分，硬幣的面值分別為：1角1分，5分和1分。這時用貪心算法，給顧客找的情況是：一個1角1分和四個1分。而找三個5分為最優(yōu)找法。故貪心算法不是對所有問題都能得到整體最優(yōu)解。3上海金融學院信息管理系學習要點理解貪心算法的概念。掌握貪心算法的基本要素（1）最優(yōu)子結(jié)構性質(zhì)（2）貪心選擇性質(zhì)理解貪心算法與動態(tài)規(guī)劃算法的差異理解貪心算法的一般理論通過應用范例學習貪心設計策略。（1）活動安排問題；（2）最優(yōu)裝載問題；（3）哈夫曼編碼；（4）單源最短路徑；（5）最小生成樹；（6）多機調(diào)度問題。4上海金融學院信息管理系adcbe15148121310671195上海金融學院信息管理系adcbe1514812131067119ac10e7d8b6a13446上海金融學院信息管理系adcbe1514812131067119ec7a10d11b6e9437上海金融學院信息管理系adcbe1514812131067119ec7a10d11b6e943a8上海金融學院信息管理系

顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。9上海金融學院信息管理系4.1活動安排問題

活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。10上海金融學院信息管理系4.1活動安排問題

設有n個活動的集合E={1,2,…,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi,且si<fi。如果選擇了活動i，則它在半開時間區(qū)間[si,fi)內(nèi)占用資源。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動i與活動j是相容的。也就是說，當si≥fj或sj≥fi時，活動i與活動j相容。11上海金融學院信息管理系4.1活動安排問題template<classType>voidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}下面給出解活動安排問題的貪心算法GreedySelector:各活動的起始時間和結(jié)束時間存儲于數(shù)組s和f中且按結(jié)束時間的非減序排列

12上海金融學院信息管理系4.1活動安排問題

由于輸入的活動以其完成時間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。

算法greedySelector的效率極高。當輸入的活動已按結(jié)束時間的非減序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時間重排。

13上海金融學院信息管理系4.1活動安排問題

例：設待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下：i1234567891011S[i]130535688212f[i]456789101112131414上海金融學院信息管理系4.1活動安排問題

算法greedySelector的計算過程如左圖所示。圖中每行相應于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當前正在檢查相容性的活動。15上海金融學院信息管理系4.1活動安排問題

若被檢查的活動i的開始時間Si小于最近選擇的活動j的結(jié)束時間fi，則不選擇活動i，否則選擇活動i加入集合A中。

貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結(jié)論可以用數(shù)學歸納法證明。16上海金融學院信息管理系4.2貪心算法的基本要素

本節(jié)著重討論可以用貪心算法求解的問題的一般特征。 對于一個具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構性質(zhì)。

17上海金融學院信息管理系4.2貪心算法的基本要素1、貪心選擇性質(zhì)

所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。

對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解。18上海金融學院信息管理系4.2貪心算法的基本要素

當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構性質(zhì)。問題的最優(yōu)子結(jié)構性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。2、最優(yōu)子結(jié)構性質(zhì)19上海金融學院信息管理系4.2貪心算法的基本要素

貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構性質(zhì)，這是2類算法的一個共同點。但是，對于具有最優(yōu)子結(jié)構的問題應該選用貪心算法還是動態(tài)規(guī)劃算法求解?是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解?下面研究2個經(jīng)典的組合優(yōu)化問題，并以此說明貪心算法與動態(tài)規(guī)劃算法的主要差別。3、貪心算法與動態(tài)規(guī)劃算法的差異20上海金融學院信息管理系4.2貪心算法的基本要素0-1背包問題：

給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。應如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?

在選擇裝入背包的物品時，對每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。21上海金融學院信息管理系4.2貪心算法的基本要素背包問題：

與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。

這2類問題都具有最優(yōu)子結(jié)構性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。

22上海金融學院信息管理系4.2貪心算法的基本要素

首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進行下去，直到背包裝滿為止。 具體算法可描述如下頁：

用貪心算法解背包問題的基本步驟：23上海金融學院信息管理系4.2貪心算法的基本要素voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);inti;for(i=1;i<=n;i++)x[i]=0;floatc=M;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}

算法knapsack的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間上界為O（nlogn）。為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì)。24上海金融學院信息管理系4.2貪心算法的基本要素

對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。事實上，在考慮0-1背包問題時，應比較選擇該物品和不選擇該物品所導致的最終方案，然后再作出最好選擇。由此就導出許多互相重疊的子問題。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。 實際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。

25上海金融學院信息管理系4.3最優(yōu)裝載

有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。1、算法描述

最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。具體算法描述如下頁。

26上海金融學院信息管理系4.3最優(yōu)裝載template<classType>voidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);for(inti=1;i<=n;i++)x[i]=0;for(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}}27上海金融學院信息管理系4.3最優(yōu)裝載2、貪心選擇性質(zhì)

可以證明最優(yōu)裝載問題具有貪心選擇性質(zhì)。

3、最優(yōu)子結(jié)構性質(zhì)

最優(yōu)裝載問題具有最優(yōu)子結(jié)構性質(zhì)。 由最優(yōu)裝載問題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構性質(zhì)，容易證明算法loading的正確性。 算法loading的主要計算量在于將集裝箱依其重量從小到大排序，故算法所需的計算時間為O(nlogn)。

28上海金融學院信息管理系4.4哈夫曼編碼

哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。 給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。1、前綴碼

對每一個字符規(guī)定一個0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。29上海金融學院信息管理系4.4哈夫曼編碼

編碼的前綴性質(zhì)可以使譯碼方法非常簡單。 表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹，即樹中任一結(jié)點都有2個兒子結(jié)點。

平均碼長定義為：

使平均碼長達到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。

30上海金融學院信息管理系4.4哈夫曼編碼2、構造哈夫曼編碼

哈夫曼提出構造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。 哈夫曼算法以自底向上的方式構造表示最優(yōu)前綴碼的二叉樹T。 算法以|C|個葉結(jié)點開始，執(zhí)行|C|－1次的“合并”運算后產(chǎn)生最終所要求的樹T。

31上海金融學院信息管理系4.4哈夫曼編碼

在書上給出的算法huffmanTree中，編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊列Q用在貪心選擇時有效地確定算法當前要合并的2棵具有最小頻率的樹。一旦2棵具有最小頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優(yōu)先隊列Q。經(jīng)過n－1次的合并后，優(yōu)先隊列中只剩下一棵樹，即所要求的樹T。

32上海金融學院信息管理系4.4哈夫曼編碼abcdef頻率(千次)4513121695定長碼000001010011100101變長碼010110011111011100定長碼：

3*(45+13+12+16+9+5)=300千位變長碼：

1*45+3*13+3*12+3*16+4*9+4*5＝224千位33上海金融學院信息管理系45a13b12c16d9e5f34上海金融學院信息管理系45a13b12c16d9e5f35上海金融學院信息管理系140145a13b12c16d9e5f36上海金融學院信息管理系45a16d14019e5f13b12c37上海金融學院信息管理系45a16d14019e5f13b12c250138上海金融學院信息管理系45a16d14019e5f13b12c250139上海金融學院信息管理系45a16d14019e5f13b12c2501300140上海金融學院信息管理系45a13b12c250116d14019e5f301041上海金融學院信息管理系45a13b12c250116d14019e5f3001550142上海金融學院信息管理系45a13b12c250116d14019e5f3001550143上海金融學院信息管理系45a13b12c250116d14019e5f300155011001010001011100110111144上海金融學院信息管理系字母abcdef變長碼010110011111011100例:010011101011000111101100111

0

100

111

0

101

100

0

111

101

100

111acdabcadbcd45上海金融學院信息管理系45a13b12c250116d14019e5f3001550110010100010111001101111例:0

100

111

0

101

100

0

111

101

100

111acdabcadbcd46上海金融學院信息管理系#include"stdafx.h"#include<iostream.h>#include<stdio.h>#include"huffmantree.h"intmain(intargc,char*argv[]){intweight,i=1,num;cout<<"num:"<<endl;cin>>num;int*a=newint[num+1];a[0]=0;cout<<"array"<<endl;while(i<=num&&cin>>weight){if(weight==0)break;a[i++]=weight;}cout<<endl;BinaryTree<int>huffman;huffman=HuffmanTree(a,i-1);HuffmanEncode(huffman,i-1);huffman.PreOutput();return0;}47上海金融學院信息管理系/////////////////////////huffmantree.h#include"binarytree.h"#include"MinHeap.h"#definelen10template<classT>classHuffman{friendBinaryTree<int>HuffmanTree(T[],int);public:operatorT()const{returnweight;}private:BinaryTree<int>tree;Tweight;};template<classT>BinaryTree<int>HuffmanTree(Ta[],intn){Huffman<T>*w=newHuffman<T>[n+1];BinaryTree<int>z,zero;for(inti=1;i<=n;i++){z.MakeTree(a[i],zero,zero);w[i].weight=a[i];w[i].tree=z;}MinHeap<Huffman<T>>H(1);H.Initialize(w,n,n);Huffman<T>x,y;for(i=1;i<n;i++){H.DeleteMin(x);H.DeleteMin(y);z.MakeTree(x+y,x.tree,y.tree);x.weight+=y.weight;x.tree=z;H.Insert(x);}H.DeleteMin(x);H.Deactivate();delete[]w;returnx.tree;}voidHuffmanEncode(BinaryTree<int>&t,intn){intcode[len];inti=0,k=0;BinaryTreeNode<int>*node=t.root;code[i++]=0;while(k<n){if(node->LeftChild&&!node->LeftChild->visited){node->LeftChild->visited=true;code[i++]=0;node=node->LeftChild;}elseif(node->RightChild&&!node->RightChild->visited){node->RightChild->visited=true;code[i++]=1;node=node->RightChild;}elseif(!(node->LeftChild||node->RightChild)){cout<<node->data<<"\t:";for(intj=1;j<i;j++)cout<<code[j]<<"";cout<<endl;k++;node=node->Parent;if(i<1)break;i-=1;}else{node=node->Parent;if(i<1)break;i-=1;}}}48上海金融學院信息管理系///////////////////binarytree.htemplate<classT>classBinaryTree;template<classT>classBinaryTreeNode{friendvoidVisit(BinaryTreeNode<T>*);friendvoidInOrder(BinaryTreeNode<T>*);friendvoidPreOrder(BinaryTreeNode<T>*);friendvoidPostOrder(BinaryTreeNode<T>*);friendvoidLevelOrder(BinaryTreeNode<T>*);friendintmain(intargc,char*argv[]);friendclassBinaryTree<T>;friendBinaryTree<int>HuffmanTree(Ta[],intn);friendvoidHuffmanEncode(BinaryTree<int>&t,intn);public:BinaryTreeNode(){LeftChild=RightChild=0;visited=false;Parent=0;}BinaryTreeNode(constT&e){data=e;LeftChild=RightChild=0;Parent=0;visited=false;}BinaryTreeNode(constT&e,BinaryTreeNode*l,BinaryTreeNode*r){data=e;LeftChild=l;RightChild=r;if(l)l->Parent=this;if(r)r->Parent=this;visited=false;}private:Tdata;BinaryTreeNode<T>*Parent,//parent/////////////////////////////*LeftChild,//leftsubtree*RightChild;//rightsubtreeboolvisited;///////////////////////////////////////////////////////};template<classT>classBinaryTree{friendBinaryTree<int>HuffmanTree(Ta[],intn);friendvoidHuffmanEncode(BinaryTree<int>&t,intn);public:BinaryTree(){root=0;};~BinaryTree(){};boolIsEmpty()const{return((root)?false:true);}boolRoot(T&x)const;voidMakeTree(constT&element,BinaryTree<T>&left,BinaryTree<T>&right);voidBreakTree(T&element,BinaryTree<T>&left,BinaryTree<T>&right);voidPreOrder(void(*Visit)(BinaryTreeNode<T>*u)){PreOrder(Visit,root);}voidInOrder(void(*Visit)(BinaryTreeNode<T>*u)){InOrder(Visit,root);}voidPostOrder(void(*Visit)(BinaryTreeNode<T>*u)){PostOrder(Visit,root);}voidPreOutput(){PreOrder(Output,root);cout<<endl;}voidInOutput(){InOrder(Output,root);cout<<endl;}voidPostOutput(){PostOrder(Output,root);cout<<endl;}voidDelete(){PostOrder(Free,root);root=0;}private:BinaryTreeNode<T>*root;voidPreOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);voidInOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);voidPostOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t);staticvoidFree(BinaryTreeNode<T>*t){deletet;}staticvoidOutput(BinaryTreeNode<T>*t){cout<<t->data<<"";}};49上海金融學院信息管理系template<classT>boolBinaryTree<T>::Root(T&x)const{if(root){x=root->data;returntrue;}elsereturnfalse;}template<classT>voidBinaryTree<T>::MakeTree(constT&element,BinaryTree<T>&left,BinaryTree<T>&right){root=newBinaryTreeNode<T>(element,left.root,right.root);left.root=right.root=0;}template<classT>voidBinaryTree<T>::BreakTree(T&element,BinaryTree<T>&left,BinaryTree<T>&right){if(!root)throwBadInput();element=root->data;left.root=root->LeftChild;right.root=root->RightChild;deleteroot;root=0;}template<classT>voidBinaryTree<T>::PreOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t){if(t){Visit(t);PreOrder(Visit,t->LeftChild);PreOrder(Visit,t->RightChild);}}template<classT>voidBinaryTree<T>::InOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t){if(t){InOrder(Visit,t->LeftChild);Visit(t);InOrder(Visit,t->RightChild);}}template<classT>voidBinaryTree<T>::PostOrder(void(*Visit)(BinaryTreeNode<T>*u),BinaryTreeNode<T>*t){if(t){PostOrder(Visit,t->LeftChild);PostOrder(Visit,t->RightChild);Visit(t);}}50上海金融學院信息管理系/////////////////MinHeap.h#include<iostream.h>template<classT>classMinHeap{public:MinHeap(intmaxheapsize=10);~MinHeap(){delete[]heap;}intSize()const{returncurrentsize;}TMax(){if(currentsize)returnheap[1];}MinHeap<T>&Insert(constT&x);MinHeap<T>&DeleteMin(T&x);voidInitialize(Tx[],intsize,intArraySize);voidDeactivate();voidoutput(Ta[],intn);/////////////////////private:intcurrentsize,maxsize;T*heap;};template<classT>voidMinHeap<T>::output(Ta[],intn){for(inti=1;i<=n;i++)cout<<a[i]<<"";cout<<endl;}template<classT>MinHeap<T>::MinHeap(intmaxheapsize){maxsize=maxheapsize;heap=newT[maxsize+1];currentsize=0;}template<classT>MinHeap<T>&MinHeap<T>::Insert(constT&x){if(currentsize==maxsize){return*this;}inti=++currentsize;while(i!=1&&x<heap[i/2]){heap[i]=heap[i/2];i/=2;}heap[i]=x;return*this;}template<classT>MinHeap<T>&MinHeap<T>::DeleteMin(T&x){if(currentsize==0){cout<<"Emptyheap!"<<endl;return*this;}x=heap[1];Ty=heap[currentsize--];inti=1,ci=2;while(ci<=currentsize){if(ci<currentsize&&heap[ci]>heap[ci+1]){ci++;}if(y<=heap[ci]){break;}heap[i]=heap[ci];i=ci;ci*=2;}heap[i]=y;return*this;}template<classT>voidMinHeap<T>::Initialize(Tx[],intsize,intArraySize){delete[]heap;heap=x;currentsize=size;maxsize=ArraySize;for(inti=currentsize/2;i>=1;i--){Ty=heap[i];intc=2*i;while(c<=currentsize){if(c<currentsize&&heap[c]>heap[c+1])c++;if(y<=heap[c])break;heap[c/2]=heap[c];c*=2;}heap[c/2]=y;}}template<classT>voidMinHeap<T>::Deactivate(){heap=0;}51上海金融學院信息管理系4.4哈夫曼編碼

算法huffmanTree用最小堆實現(xiàn)優(yōu)先隊列Q。初始化優(yōu)先隊列需要O(n)計算時間，由于最小堆的removeMin和put運算均需O(logn)時間，n－1次的合并總共需要O(nlogn)計算時間。因此，關于n個字符的哈夫曼算法的計算時間為O(nlogn)。52上海金融學院信息管理系4.4哈夫曼編碼3、哈夫曼算法的正確性

要證明哈夫曼算法的正確性，只要證明最優(yōu)前綴碼問題具有貪心選擇性質(zhì)和最優(yōu)子結(jié)構性質(zhì)。 (1)貪心選擇性質(zhì) (2)最優(yōu)子結(jié)構性質(zhì)53上海金融學院信息管理系4.5單源最短路徑

給定帶權有向圖G=(V,E)，其中每條邊的權是非負實數(shù)。另外，還給定V中的一個頂點，稱為源?，F(xiàn)在要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權之和。這個問題通常稱為單源最短路徑問題。 1、算法基本思想

Dijkstra算法是解單源最短路徑問題的貪心算法。54上海金融學院信息管理系4.5單源最短路徑

其基本思想是，設置頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。 初始時，S中僅含有源。設u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度。55上海金融學院信息管理系4.5單源最短路徑

例如，對右圖中的有向圖，應用Dijkstra算法計算從源頂點1到其它頂點間最短路徑的過程列在下頁的表中。56上海金融學院信息管理系4.5單源最短路徑迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}260301002{1,2,4}450903{1,2,4,3}3604{1,2,4,3,5}5Dijkstra算法的迭代過程：

57上海金融學院信息管理系4.5單源最短路徑2、算法的正確性和計算復雜性(1)貪心選擇性質(zhì)(2)最優(yōu)子結(jié)構性質(zhì)(3)計算復雜性

對于具有n個頂點和e條邊的帶權有向圖，如果用帶權鄰接矩陣表示這個圖，那么Dijkstra算法的主循環(huán)體需要時間。這個循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要時間。算法的其余部分所需要時間不超過。58上海金融學院信息管理系算法描述：Template<classtype>VoidDijkstra(intn,intv,Typedist[],intprev[],Type**c){ bools[maxint]; for(inti=1;i<=n;i++){ dist[i]=c[v][i];s[i]=false; if(dist[i]==maxint)prev[i]=0; elseprev[i]=v;} dist[v]=0;s[v]=true; for(inti=1;i<n;i++){ inttemp=maxint;intu=v; for(intj=1;j<=n;j++) if((!s[j])&&(dist[j]<temp)){u=j;temp=dist[j];} s[u]=true; for(intj=1;j<=n;j++) if((!s[j])&&(c[u][j]<maxint)){ typenewdist=dist[u]+c[u][j]; if(newdist<dist[j]){dist[j]=newdist;prev[j]=u;}}}}59上海金融學院信息管理系#include"stdafx.h"#include<iostream.h>template<classtype>voidDijkstra(intn,intv,intmaxint,typedist[],intprev[],typec[][6]);intmain(intargc,char*argv[]){ intmaxint=30000; intn=5; intv=1; intdist[6]; intprev[6]; intc[6][6]={{0,0,0,0,0,0},{0,0,10,maxint,30,100},{0,maxint,0,50,maxint,maxint},{0,maxint,maxint,0,maxint,10},{0,maxint,maxint,20,0,60},{0,maxint,maxint,maxint,maxint,0}};Dijkstra(n,v,maxint,dist,prev,c);for(inti=1;i<=n;i++)cout<<"prev("<<i<<")="<<prev[i]<<endl; cout<<endl; return0;}60上海金融學院信息管理系template<classtype>voidDijkstra(intn,intv,intmaxint,typedist[],intprev[],typec[][6]){ bools[6]; for(inti=1;i<=n;i++){ dist[i]=c[v][i];s[i]=false; if(dist[i]==maxint)prev[i]=0; elseprev[i]=v; cout<<dist[i]<<"";}cout<<endl; dist[v]=0;s[v]=true; for(i=1;i<n;i++) { inttemp=maxint;intu=v; for(intj=1;j<=n;j++) if((!s[j])&&(dist[j]<temp)){u=j;temp=dist[j];} s[u]=true; for(j=1;j<=n;j++) {if((!s[j])&&(c[u][j]<maxint)) { typenewdist=dist[u]+c[u][j]; if(newdist<dist[j]){dist[j]=newdist;prev[j]=u;} } cout<<dist[j]<<""; } cout<<endl;}}61上海金融學院信息管理系4.6最小生成樹

設G=(V,E)是無向連通帶權圖，即一個網(wǎng)絡。E中每條邊(v,w)的權為c[v][w]。如果G的子圖G’是一棵包含G的所有頂點的樹，則稱G’為G的生成樹。生成樹上各邊權的總和稱為該生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。 網(wǎng)絡的最小生成樹在實際中有廣泛應用。例如，在設計通信網(wǎng)絡時，用圖的頂點表示城市，用邊(v,w)的權c[v][w]表示建立城市v和城市w之間的通信線路所需的費用，則最小生成樹就給出了建立通信網(wǎng)絡的最經(jīng)濟的方案。62上海金融學院信息管理系4.6最小生成樹1、最小生成樹性質(zhì)

用貪心算法設計策略可以設計出構造最小生成樹的有效算法。本節(jié)介紹的構造最小生成樹的Prim算法和Kruskal算法都可以看作是應用貪心算法設計策略的例子。盡管這2個算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹性質(zhì)： 設G=(V,E)是連通帶權圖，U是V的真子集。如果(u,v)

E，且u

U，v

V-U，且在所有這樣的邊中，(u,v)的權c[u][v]最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個性質(zhì)有時也稱為MST性質(zhì)。

63上海金融學院信息管理系4.6最小生成樹2、Prim算法

設G=(V,E)是連通帶權圖，V={1,2,…,n}。 構造G的最小生成樹的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件i

S，j

V-S，且c[i][j]最小的邊，將頂點j添加到S中。這個過程一直進行到S=V時為止。 在這個過程中選取到的所有邊恰好構成G的一棵最小生成樹。

64上海金融學院信息管理系4.6最小生成樹

利用最小生成樹性質(zhì)和數(shù)學歸納法容易證明，上述算法中的邊集合T始終包含G的某棵最小生成樹中的邊。因此，在算法結(jié)束時，T中的所有邊構成G的一棵最小生成樹。

例如，對于右圖中的帶權圖，按Prim算法選取邊的過程如下頁圖所示。65上海金融學院信息管理系4.6最小生成樹66上海金融學院信息管理系4.6最小生成樹

在上述Prim算法中，還應當考慮如何有效地找出滿足條件i

S,j

V-S，且權c[i][j]最小的邊(i,j)。實現(xiàn)這個目的的較簡單的辦法是設置2個數(shù)組closest和lowcost。 在Prim算法執(zhí)行過程中，先找出V-S中使lowcost值最小的頂點j，然后根據(jù)數(shù)組closest選取邊(j,closest[j］)，最后將j添加到S中，并對closest和lowcost作必要的修改。 用這個辦法實現(xiàn)的Prim算法所需的計算時間為

67上海金融學院信息管理系4.6最小生成樹3、Kruskal算法

Kruskal算法構造G的最小生成樹的基本思想是，首先將G的n個頂點看成n個孤立的連通分支。將所有的邊按權從小到大排序。然后從第一條邊開始，依邊權遞增的順序查看每一條邊，并按下述方法連接2個不同的連通分支：當查看到第k條邊(v,w)時，如果端點v和w分別是當前2個不同的連通分支T1和T2中的頂點時，就用邊(v,w)將T1和T2連接成一個連通分支，然后繼續(xù)查看第k+1條邊；如果端點v和w在當前的同一個連通分支中，就直接再查看第k+1條邊。這個過程一直進行到只剩下一個連通分支時為止。

68上海金融學院信息管理系4.6最小生成樹

例如，對前面的連通帶權圖，按Kruskal算法順序得到的最小生成樹上的邊如下圖所示。69上海金融學院信息管理系4.6最小生成樹

關于集合的一些基本運算可用于實現(xiàn)Kruskal算法。 按權的遞增順序查看等價于對優(yōu)先隊列執(zhí)行removeMin運算?？梢杂枚褜崿F(xiàn)這個優(yōu)先隊列。 對一個由連通分支組成的集合不斷進行修改，需要用到抽象數(shù)據(jù)類型并查集UnionFind所支持的基本運算。 當圖的邊數(shù)為e時，Kruskal算法所需的計算時間是。當時，Kruskal算法比Prim算法差，但當時，Kruskal算法卻比Prim算法好得多。70上海金融學院信息管理系4.7多機調(diào)度問題

多機調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個作業(yè)在盡可能短的時間內(nèi)由m臺機器加工處理完成。 這個問題是NP完全問題，到目前為止還沒有有效的解法。對于這一類問題,用貪心選擇策略有時可以設計出較好的近似算法。約定，每個作業(yè)均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。71上海金融學院信息管理系4.7多機調(diào)度問題

采用最長處理時間作業(yè)優(yōu)先的貪心選擇策略可以設計出解多機調(diào)度問題的較好的近似算法。 按此策略，當時，只要將機器i的[0,ti]時間區(qū)間分配給作業(yè)i即可，算法只需要O(1)時間。 當時，首先將n個作業(yè)依其所需的處理時間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機。算法所需的計算時間為O(nlogn)。72上海金融學院信息管理系4.7多機調(diào)度問題

例如，設7個獨立作業(yè){1,2,3,4,5,6,7}由3臺機器M1，M2和M3加工處理。各作業(yè)所需的處理時間分別為{2,14,4,16,6,5,3}。按算法greedy產(chǎn)生的作業(yè)調(diào)度如下圖所示，所需的加工時間為17。

73上海金融學院信息管理系4.8貪心算法的理論基礎

借助于擬陣工具，可建立關于貪心算法的較一般的理論。這個理論對確定何時使用貪心算法可以得到問題的整體最優(yōu)解十分有用。1、擬陣

擬陣M定義為滿足下面3個條件的有序?qū)?S,I)： (1)S是非空有限集。 (2)I是S的一類具有遺傳性質(zhì)的獨立子集族，即若B

I，則B是S的獨立子集，且B的任意子集也都是S的獨立子集?？占?/p>

必為I的成員。 (3)I滿足交換性質(zhì)，即若A

I,B

I且|A|<|B|，則存在某一元素x

B-A，使得A∪{x}

I。74上海金融學院信息管理系4.8貪心算法的理論基礎

例如，設S是一給定矩陣中行向量的集合，I是S的線性獨立子集族，則由線性空間理論容易證明(S,I)是一擬陣。擬陣的另一個例子是無向圖G=(V,E)的圖擬陣。 給定擬陣M=(S,I)，對于I中的獨立子集A

I，若S有一元素x

A，使得將x加入A后仍保持獨立性，即A∪{x}

I,則稱x為A的可擴展元素。 當擬陣M中的獨立子集A沒有可擴展元素時，稱A為極大獨立子集。75上海金融學院信息管理系4.8貪心算法的理論基礎

下面的關于極大獨立子集的性質(zhì)是很有用的。 定理4.1：擬陣M中所有極大獨立子集大小相同。 這個定理可以用反證法證明。 若對擬陣M=(S,I)中的S指定權函數(shù)W，使得對于任意x

S，有W(x)>0，則稱擬陣M為帶權擬陣。依此權函數(shù)，S的任一子集A的權定義

。2、關于帶權擬陣的貪心算法

許多可以用貪心算法求解的問題可以表示為求帶權擬陣的最大權獨立子集問題。

76上海金融學院信息管理系4.8貪心算法的理論基礎

給定帶權擬陣M=(S,I)，確定S的獨立子集A

I使得W(A)達到最大。這種使W(A)最大的獨立子集A稱為擬陣M的最優(yōu)子集。由于S中任一元素x的權W(x)是正的，因此，最優(yōu)子集也一定是極大獨立子集。

例如，在最小生成樹問題可以表示為確定帶權擬陣的最優(yōu)子集問題。求帶權擬陣的最優(yōu)子集A的算法可用于解最小生成樹問題。 下面給出求帶權擬陣最優(yōu)子集的貪心算法。該算法以具有正權函數(shù)W的帶權擬陣M=(S,I)作為輸入，經(jīng)計算后輸出M的最優(yōu)子集A。77上海金融學院信息管理系4.8貪心算法的理論基礎Setgreedy(M,W){A=

;

將S中元素依權值W（大者優(yōu)先）組成優(yōu)先隊列；

while(S!=

){S.removeMax(x);if(A∪{x}

I)A=A∪{x};}returnA}78上海金融學院信息管理系4.8貪心算法的理論基礎

算法greedy的計算時間復雜性為