貪婪算法---二分覆蓋

ID:14287233

大小:40.50 KB

頁數(shù):14頁

時間:2018-07-27

貪婪算法---二分覆蓋_第1頁
貪婪算法---二分覆蓋_第2頁
貪婪算法---二分覆蓋_第3頁
貪婪算法---二分覆蓋_第4頁
貪婪算法---二分覆蓋_第5頁
資源描述:

《貪婪算法---二分覆蓋》由會員上傳分享,免費在線閱讀,更多相關內容在行業(yè)資料-天天文庫。

1、貪婪算法---二分覆蓋二分覆蓋二分圖是一個無向圖,它的n個頂點可二分為集合A和集合B,且同一集合中的任意兩個頂點在圖中無邊相連(即任何一條邊都是一個頂點在集合A中,另一個在集合B中)。當且僅當B中的每個頂點至少與A中一個頂點相連時,A的一個子集A'覆蓋集合B(或簡單地說,A'是一個覆蓋)。覆蓋A'的大小即為A'中的頂點數(shù)目。當且僅當A'是覆蓋B的子集中最小的時,A'為最小覆蓋。例1-10考察如圖1-6所示的具有17個頂點的二分圖,A={1,2,3,16,17}和B={4,5,6,7,8,9,10,11,12,13,14,15},子集A'={1

2、,16,17}是B的最小覆蓋。在二分圖中尋找最小覆蓋的問題為二分覆蓋(bipartite-cover)問題。在例12-3中說明了最小覆蓋是很有用的,因為它能解決“在會議中使用最少的翻譯人員進行翻譯”這一類的問題。二分覆蓋問題類似于集合覆蓋(set-cover)問題。在集合覆蓋問題中給出了k個集合S={S1,S2,.,Sk},每個集合Si中的元素均是全集U中的成員。當且僅當èiS'Si=U時,S的子集S'覆蓋U,S'中的集合數(shù)目即為覆蓋的大小。當且僅當沒有能覆蓋U的更小的集合時,稱S'為最小覆蓋??梢詫⒓细采w問題轉化為二分覆蓋問題(反之亦然)

3、,即用A的頂點來表示S1,.,Sk,B中的頂點代表U中的元素。當且僅當S的相應集合中包含U中的對應元素時,在A與B的頂點之間存在一條邊。例1-11令S={S1,...,S5},U={4,5,...,15},S1={4,6,7,8,9,13},S2={4,5,6,8},S3={8,10,12,14,15},S4={5,6,8,12,14,15},S5={4,9,10,11}。S'={S1,S4,S5}是一個大小為3的覆蓋,沒有更小的覆蓋,S'即為最小覆蓋。這個集合覆蓋問題可映射為圖1-6的二分圖,即用頂點1,2,3,16和17分別表示集合S1,

4、S2,S3,S4和S5,頂點j表示集合中的元素j,4≤j≤15。集合覆蓋問題為NP-復雜問題。由于集合覆蓋與二分覆蓋是同一類問題,二分覆蓋問題也是NP-復雜問題。因此可能無法找到一個快速的算法來解決它,但是可以利用貪婪算法尋找一種快速啟發(fā)式方法。一種可能是分步建立覆蓋A',每一步選擇A中的一個頂點加入覆蓋。頂點的選擇利用貪婪準則:從A中選取能覆蓋B中還未被覆蓋的元素數(shù)目最多的頂點。例1-12考察圖1-6所示的二分圖,初始化A'=且B中沒有頂點被覆蓋,頂點1和16均能覆蓋B中的六個頂點,頂點3覆蓋五個,頂點2和17分別覆蓋四個。因此,在第一步往

5、A'中加入頂點1或16,若加入頂點16,則它覆蓋的頂點為{5,6,8,12,14,15},未覆蓋的頂點為{4,7,9,10,11,13}。頂點1能覆蓋其中四個頂點({4,7,9,13}),頂點2覆蓋一個({4}),頂點3覆蓋一個({10}),頂點16覆蓋零個,頂點17覆蓋四個{4,9,10,11}。下一步可選擇1或17加入A'。若選擇頂點1,則頂點{10,11}仍然未被覆蓋,此時頂點1,2,16不覆蓋其中任意一個,頂點3覆蓋一個,頂點17覆蓋兩個,因此選擇頂點17,至此所有頂點已被覆蓋,得A'={16,1,17}。圖1-7給出了貪婪覆蓋啟發(fā)式

6、方法的偽代碼,可以證明:1)當且僅當初始的二分圖沒有覆蓋時,算法找不到覆蓋;2)啟發(fā)式方法可能找不到二分圖的最小覆蓋。1.數(shù)據(jù)結構的選取及復雜性分析為實現(xiàn)圖13-7的算法,需要選擇A'的描述方法及考慮如何記錄A中節(jié)點所能覆蓋的B中未覆蓋節(jié)點的數(shù)目。由于對集合A'僅使用加法運算,則可用一維整型數(shù)組C來描述A',用m來記錄A'中元素個數(shù)。將A'中的成員記錄在C[0:m-1]中。對于A中頂點i,令Newi為i所能覆蓋的B中未覆蓋的頂點數(shù)目。逐步選擇Newi值最大的頂點。由于一些原來未被覆蓋的頂點現(xiàn)在被覆蓋了,因此還要修改各Newi值。在這種更新中,

7、檢查B中最近一次被V覆蓋的頂點,令j為這樣的一個頂點,則A中所有覆蓋j的頂點的Newi值均減1。例1-13考察圖1-6,初始時(New1,New2,New3,New16,New17)=(6,4,5,6,4)。假設在例1-12中,第一步選擇頂點16,為更新Newi的值檢查B中所有最近被覆蓋的頂點,這些頂點為5,6,8,12,14和15。當檢查頂點5時,將頂點2和16的Newi值分別減1,因為頂點5不再是被頂點2和16覆蓋的未覆蓋節(jié)點;當檢查頂點6時,頂點1,2,和16的相應值分別減1;同樣,檢查頂點8時,1,2,3和16的值分別減1;當檢查完所

8、有最近被覆蓋的頂點,得到的Newi值為(4,1,0,4)。下一步選擇頂點1,最新被覆蓋的頂點為4,7,9和13;檢查頂點4時,New1,New2,和New17的值減

當前文檔最多預覽五頁,下載文檔查看全文

此文檔下載收益歸作者所有

當前文檔最多預覽五頁,下載文檔查看全文
溫馨提示:
1. 部分包含數(shù)學公式或PPT動畫的文件,查看預覽時可能會顯示錯亂或異常,文件下載后無此問題,請放心下載。
2. 本文檔由用戶上傳,版權歸屬用戶,天天文庫負責整理代發(fā)布。如果您對本文檔版權有爭議請及時聯(lián)系客服。
3. 下載前請仔細閱讀文檔內容,確認文檔內容符合您的需求后進行下載,若出現(xiàn)內容與標題不符可向本站投訴處理。
4. 下載文檔時可能由于網絡波動等原因無法下載或下載錯誤,付費完成后未能成功下載的用戶請聯(lián)系客服處理。
关闭