最優(yōu)二叉樹算法

衡量一個算法的優(yōu)劣有許多因素，效率就是其中之一。而效率指的就是算法的執(zhí)行時間。提高效率是軟件開發(fā)必須注重的問題。對同一個問題往往有多個算法可以解決，在同等條件下，執(zhí)行時間短的算法其效率是最高的。從霍夫曼樹的定義以及霍夫曼算法出發(fā)，介紹如何構造霍夫曼樹以及利用霍夫曼算法優(yōu)化程序設計的原理，重點討論在判定類問題中利用霍夫曼樹可以建立最佳判定算法，提高程序的執(zhí)行速度。

最優(yōu)二叉樹算法基本信息

中文名稱 最優(yōu)二叉樹算法 效率 算法的執(zhí)行時間
算法的思想 進行森林F中的二叉樹的"合并" 別????稱 哈夫曼樹

從上述算法中可以看出，F(xiàn)實際上是森林，該算法的思想是不斷地進行森林F中的二叉樹的"合并"，最終得到哈夫曼樹。

在構造哈夫曼樹時，可以設置一個結構數(shù)組HuffNode保存哈夫曼樹中各結點的信息，根據(jù)二叉樹的性質可知，具有n個葉子結點的哈夫曼樹共有2n-1個結點，所以數(shù)組HuffNode的大小設置為2n-1，數(shù)組元素的結構形式如下:

weight

lchild

rchild

parent

其中，weight域保存結點的權值，lchild和rchild域分別保存該結點的左、右孩子結點在數(shù)組HuffNode中的序號，從而建立起結點之間的關系。為了判定一個結點是否已加入到要建立的哈夫曼樹中，可通過parent域的值來確定。初始時parent的值為-1，當結點加入到樹中時，該結點parent的值為其雙親結點在數(shù)組HuffNode中的序號，就不會是-1了。

構造哈夫曼樹時，首先將由n個字符形成的n個葉結點存放到數(shù)組HuffNode的前n個分量中，然后根據(jù)前面介紹的哈夫曼方法的基本思想，不斷將兩個小子樹合并為一個較大的子樹，每次構成的新子樹的根結點順序放到HuffNode數(shù)組中的前n個分量的后面。

下面給出哈夫曼樹的構造算法。

const maxvalue= 10000; {定義最大權值}

maxleat=30; {定義哈夫曼樹中葉子結點個數(shù)}

maxnode=maxleaf*2-1;

type HnodeType=record

weight: integer;

parent: integer;

lchild: integer;

rchild: integer;

end;

HuffArr:array[0..maxnode] of HnodeType;

var ……

procedure CreatHaffmanTree(var HuffNode: HuffArr); {哈夫曼樹的構造算法}

var i,j,m1,m2,x1,x2,n: integer;

begin

readln(n); {輸入葉子結點個數(shù)}

for i:=0 to 2*n-1 do {數(shù)組HuffNode[ ]初始化}

begin

HuffNode.weight=0;

HuffNode.parent=-1;

HuffNode.lchild=-1;

HuffNode.rchild=-1;

end;

for i:=0 to n-1 do read(HuffNode.weight); {輸入n個葉子結點的權值}

for i:=0 to n-1 do {構造哈夫曼樹}

begin

m1:=MAXVALUE; m2:=MAXVALUE;

x1:=0; x2:=0;

for j:=0 to n i-1 do

if (HuffNode[j].weight

begin m2:=m1; x2:=x1;

m1:=HuffNode[j].weight; x1:=j;

end

else if (HuffNode[j].weight

begin m2:=HuffNode[j].weight; x2:=j; end;

{將找出的兩棵子樹合并為一棵子樹}

HuffNode[x1].parent:=n i; HuffNode[x2].parent:=n i;

HuffNode[n i].weight:= HuffNode[x1].weight HuffNode[x2].weight;

HuffNode[n i].lchild:=x1; HuffNode[n i].rchild:=x2;

end;

end;

最優(yōu)二叉樹算法造價信息

市場價 信息價 詢價
材料名稱 規(guī)格/型號 市場價
（除稅）		 工程建議價
（除稅）		 行情 品牌 單位 稅率 供應商 報價日期
二叉 S-8 查看價格 查看價格

塊 13% 大連東方泰陶建材經(jīng)銷部
瓦二叉 200X120X100mm 查看價格 查看價格

金九方

 塊 13% 佛山市金九方陶瓷有限公司
二叉（四類色） S-8 查看價格 查看價格

比特利

 件 13% 重慶比特利建材有限公司
二叉（二類色） S-8 查看價格 查看價格

比特利

 件 13% 重慶比特利建材有限公司
二叉（一類色（紅胎）） S-8 查看價格 查看價格

比特利

 件 13% 重慶比特利建材有限公司
二叉（三類色） S-8 查看價格 查看價格

比特利

 件 13% 重慶比特利建材有限公司
四叉（二類色） S-四叉 查看價格 查看價格

比特利

 件 13% 重慶比特利建材有限公司
四叉（二類色） T四叉 查看價格 查看價格

比特利

 件 13% 重慶比特利建材有限公司
材料名稱 規(guī)格/型號 除稅
信息價		 含稅
信息價		 行情 品牌 單位 稅率 地區(qū)/時間
日本瓦[J-四叉] 查看價格 查看價格

塊 韶關市2009年11月信息價
日本瓦[J-四叉] 查看價格 查看價格

塊 韶關市2009年7月信息價
日本瓦[J-四叉] 查看價格 查看價格

塊 韶關市2008年9月信息價
日本瓦[J-四叉] 查看價格 查看價格

塊 韶關市2008年8月信息價
日本瓦[J-四叉] 查看價格 查看價格

塊 韶關市2008年1月信息價
日本瓦[J-四叉] 查看價格 查看價格

塊 韶關市2007年10月信息價
日本瓦[J-四叉] 查看價格 查看價格

塊 韶關市2007年8月信息價
日本瓦[J-四叉] 查看價格 查看價格

塊 韶關市2007年7月信息價
材料名稱 規(guī)格/需求量 報價數(shù) 最新報價
（元）		 供應商 報價地區(qū) 最新報價時間
二叉 S-8|3645塊 1 查看價格 大連東方泰陶建材經(jīng)銷部 遼寧  大連市 2015-11-24
二叉噴頭 DN15|6779個 1 查看價格 佛山市天興消防器材有限公司 廣東  佛山市 2015-10-20
三叉、二叉管 -|1臺 1 查看價格 深圳市力德森氣動工具有限公司    2017-06-12
瓦二叉 200X120X100mm|9894塊 1 查看價格 佛山市金九方陶瓷有限公司 廣東  佛山市 2015-12-24
二叉頭路燈 高度5米,功率2×30W,光源LED|4臺 3 查看價格 深圳市奧瑞泰光電科技有限公司 廣東  廣州市 2019-01-28
AI算法訓練 AI算法訓練|25天 3 查看價格 廣州市熹尚科技設備有限公司 廣東   2021-07-16
AI算法訓練 AI算法訓練|60天 3 查看價格 浙江大華技術股份有限公司深圳分公司 廣東   2021-03-31
超五類二叉水晶頭 PL45E-A 水晶頭類|7531盒 1 查看價格 廣州市唯康通信技術有限公司 廣東  廣州市 2015-05-27

在數(shù)據(jù)通訊中，經(jīng)常需要將傳送的文字轉換成由二進制字符0，1組成的二進制串，我們稱之為編碼。例如，假設要傳送的電文為ABACCDA，電文中只含有A，B，C，D四種字符，若這四種字符采用表7.3 (a)所示的編碼，則電文的代碼為000010000100100111 000，長度為21。在傳送電文時，我們總是希望傳送時間盡可能短，這就要求電文代碼盡可能短，顯然，這種編碼方案產(chǎn)生的電文代碼不夠短。表7.3 (b)所示為另一種編碼方案，用此編碼對上述電文進行編碼所建立的代碼為00010010101100，長度為14。在這種編碼方案中，四種字符的編碼均為兩位，是一種等長編碼。如果在編碼時考慮字符出現(xiàn)的頻率，讓出現(xiàn)頻率高的字符采用盡可能短的編碼，出現(xiàn)頻率低的字符采用稍長的編碼，構造一種不等長編碼，則電文的代碼就可能更短。如當字符A，B，C，D采用表7.3 (c)所示的編碼時，上述電文的代碼為0110010101110，長度僅為13。

表a、表b、表c、表d(從下圖的上下順序依次列出)

字符

編碼

A

000

B

010

C

100

D

111

字符

編碼

A

00

B

01

C

10

D

11

字符

編碼

A

0

B

110

C

10

D

111

字符

編碼

A

01

B

010

C

001

D

10

表3 字符的四種不同的編碼方案

哈夫曼樹可用于構造使電文的編碼總長最短的編碼方案。具體做法如下:設需要編碼的字符集合為{d1，d2，…，dn}，它們在電文中出現(xiàn)的次數(shù)或頻率集合為{w1，w2，…，wn}，以d1，d2，…，dn作為葉結點，w1，w2，…，wn作為它們的權值，構造一棵哈夫曼樹，規(guī)定哈夫曼樹中的左分支代表0，右分支代表1，則從根結點到每個葉結點所經(jīng)過的路徑分支組成的0和1的序列便為該結點對應字符的編碼，我們稱之為哈夫曼編碼。

在哈夫曼編碼樹中，樹的帶權路徑長度的含義是各個字符的碼長與其出現(xiàn)次數(shù)的乘積之和，也就是電文的代碼總長，所以采用哈夫曼樹構造的編碼是一種能使電文代碼總長最短的不等長編碼。

在建立不等長編碼時，必須使任何一個字符的編碼都不是另一個字符編碼的前綴，這樣才能保證譯碼的唯一性。例如表7.3 (d)的編碼方案，字符A的編碼01是字符B的編碼010的前綴部分，這樣對于代碼串0101001，既是AAC的代碼，也是ABD和BDA的代碼，因此，這樣的編碼不能保證譯碼的唯一性，我們稱之為具有二義性的譯碼。

然而，采用哈夫曼樹進行編碼，則不會產(chǎn)生上述二義性問題。因為，在哈夫曼樹中，每個字符結點都是葉結點，它們不可能在根結點到其它字符結點的路徑上，所以一個字符的哈夫曼編碼不可能是另一個字符的哈夫曼編碼的前綴，從而保證了譯碼的非二義性。

下面討論實現(xiàn)哈夫曼編碼的算法。實現(xiàn)哈夫曼編碼的算法可分為兩大部分:

(1)構造哈夫曼樹;

(2)在哈夫曼樹上求葉結點的編碼。

求哈夫曼編碼，實質上就是在已建立的哈夫曼樹中，從葉結點開始，沿結點的雙親鏈域回退到根結點，每回退一步，就走過了哈夫曼樹的一個分支，從而得到一位哈夫曼碼值，由于一個字符的哈夫曼編碼是從根結點到相應葉結點所經(jīng)過的路徑上各分支所組成的0，1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求編碼的高位碼。我們可以設置一結構數(shù)組HuffCode用來存放各字符的哈夫曼編碼信息，數(shù)組元素的結構如下:

bit

start

其中，分量bit為一維數(shù)組，用來保存字符的哈夫曼編碼，start表示該編碼在數(shù)組bit中的開始位置。所以，對于第i個字符，它的哈夫曼編碼存放在HuffCode.bit中的從HuffCode.start到n的分量上。

求哈夫曼編碼程序段

const Maxleaf=128; {定義最多葉結點數(shù)}

MaxNode=255; {定義最大結點數(shù)}

MaxBit=10; {定義哈夫曼編碼的最大長度}

type HCodeType =record

bit: array[0..MaxBit] of integer;

start: integer;

end;

……

procedure HaffmanCode ; {生成哈夫曼編碼}

var HuffNode: array[0..MaxNode] of HCodeType;

HuffCode: array[0..MaxLeaf] of HcodeType;

cd : HcodeType ;

i,j, c,p: integer ;

begin

HuffmanTree (HuffNode ); {建立哈夫曼樹}

for i:=0 to n-1 do {求每個葉子結點的哈夫曼編碼}

begin

cd.start:=n-1; c:=i;

p:=HuffNode[c].parent;

while p<>0 do {由葉結點向上直到樹根}

if HuffNode

.lchild=c then cd.bit[cd.start]:=0

else cd.bit[cd.start]:=1;

dec (cd.start); c:=p;

p:=HuffNode[c].parent;

end;

for j:=cd.start 1 to n-1 do {保存求出的每個葉結點的哈夫曼編碼和編碼的起始位}

begin

HuffCode.bit[j]:=cd.bit[j];

HuffCode.start=cd.start;

end;

for i:=0 to n-1 do {輸出每個葉子結點的哈夫曼編碼}

begin

for j:=HuffCode.start 1 to n-1 do write(HuffCode.bit[j]:10);

writeln;

end;

end;

在實際應用中，常常要考慮一個問題:如何設計一棵二叉樹，使得執(zhí)行路徑最短，即算法的效率最高。

例1.快遞包裹的郵資問題

假設郵政局的包裹自動測試系統(tǒng)能夠測出包裹的重量，如何設計一棵二叉樹將包裹根據(jù)重量及運距進行分類從而確定郵資。

國內(nèi)快遞包裹資費 單位:元

(2004年1月1日起執(zhí)行)

運距(公里)

首重1000克

5000克以內(nèi)續(xù)重每500克

5001克以上續(xù)重每500克

<=500

5.00

2.00

1.00

<=1000 >500

6.00

2.50

1.30

<=1500 >1000

7.00

3.00

1.60

<=2000 >1500

8.00

3.50

1.90

<=2500 >2000

9.00

4.00

2.20

<=3000 >2500

10.00

4.50

2.50

<=4000 >3000

12.00

5.50

3.10

<=5000 >4000

14.00

6.50

3.70

<=6000 >5000

16.00

7.50

4.30

>6000

20.00

9.00

6.00

表1 國家郵政局制定的快遞包裹參考標準

根據(jù)表1可以制定出許多種二叉樹，但不同的二叉樹判定的次數(shù)可能不一樣，執(zhí)行的效率也不同。

鐵球分類

現(xiàn)有一批球磨機上的鐵球，需要將它分成四類:直徑不大于20的屬于第一類;直徑大于20而不大于50的屬于第二類;直徑大于50而不大于100的屬于第三類;其余的屬于第四類;假定這批球中屬于第一、二、三、四類鐵球的個數(shù)之比例是1:2:3:4。

我們可以把這個判斷過程表示為 圖1中的兩種方法:

最優(yōu)二叉樹算法

兩種判斷二叉樹示意圖

那么究竟將這個判斷過程表示成哪一個判斷框，才能使其執(zhí)行時間最短呢?讓我們對上述判斷框做一具體的分析。

假設有1000個鐵球，則各類鐵球的個數(shù)分別為:100、200、300、400;

對于圖7.1中的上圖和下圖比較的次數(shù)分別如表所示:

左圖 和下圖

序號

比較式

比較次數(shù)

1

a<20

1000

2

a<50

900

3

a<=100

700

合計

2600

序號

比較式

比較次數(shù)

1

a>100

1000

2

a>50

600

3

a<=20

300

合計

1900

表2 兩種判斷二叉樹比較次數(shù)

過上述分析可知，圖1中右圖所示的判斷框的比較次數(shù)遠遠小于左圖所示的判斷框的比較次數(shù)。為了找出比較次數(shù)最少的判斷框，將涉及到樹的路徑長度問題。

最優(yōu)二叉樹算法常見問題

最優(yōu)二叉樹算法基本概念

最優(yōu)二叉樹，也稱哈夫曼(Haffman)樹，是指對于一組帶有確定權值的葉結點，構造的具有最小帶權路徑長度的二叉樹。

那么什么是二叉樹的帶權路徑長度呢?

在前面我們介紹過路徑和結點的路徑長度的概念，而二叉樹的路徑長度則是指由根結點到所有葉結點的路徑長度之和。如果二叉樹中的葉結點都具有一定的權值，則可將這一概念加以推廣。設二叉樹具有n個帶權值的葉結點，那么從根結點到各個葉結點的路徑長度與相應結點權值的乘積之和叫做二叉樹的帶權路徑長度，記為:

WPL= Wk·Lk

其中Wk為第k個葉結點的權值，Lk 為第k個葉結點的路徑長度。如圖7.2所示的二叉樹，它的帶權路徑長度值WPL=2×2+4×2+5×2+3×2=28。

在給定一組具有確定權值的葉結點，可以構造出不同的帶權二叉樹。例如，給出4個葉結點，設其權值分別為1，3，5，7，我們可以構造出形狀不同的多個二叉樹。這些形狀不同的二叉樹的帶權路徑長度將各不相同。圖7.3給出了其中5個不同形狀的二叉樹。

這五棵樹的帶權路徑長度分別為:

(a)WPL=1×2+3×2+5×2+7×2=32

(b)WPL=1×3+3×3+5×2+7×1=29

(c)WPL=1×2+3×3+5×3+7×1=33

(d)WPL=7×3+5×3+3×2+1×1=43

(e)WPL=7×1+5×2+3×3+1×3=29

最優(yōu)二叉樹算法

最優(yōu)二叉樹算法

由此可見，由相同權值的一組葉子結點所構成的二叉樹有不同的形態(tài)和不同的帶權路徑長度，那么如何找到帶權路徑長度最小的二叉樹(即哈夫曼樹)呢?根據(jù)哈夫曼樹的定義，一棵二叉樹要使其WPL值最小，必須使權值越大的葉結點越靠近根結點，而權值越小的葉結點越遠離根結點。

哈夫曼(Haffman)依據(jù)這一特點于1952年提出了一種方法，這種方法的基本思想是:

(1)由給定的n個權值{W1，W2，…，Wn}構造n棵只有一個葉結點的二叉樹，從而得到一個二叉樹的集合F={T1，T2，…，Tn};

(2)在F中選取根結點的權值最小和次小的兩棵二叉樹作為左、右子樹構造一棵新的二叉樹，這棵新的二叉樹根結點的權值為其左、右子樹根結點權值之和;

(3)在集合F中刪除作為左、右子樹的兩棵二叉樹，并將新建立的二叉樹加入到集合F中;

(4)重復(2)(3)兩步，當F中只剩下一棵二叉樹時，這棵二叉樹便是所要建立的哈夫曼樹。

在本章的引入部分，兩個例子都是判定問題，這兩個判定問題都可以通過構造哈夫曼樹來優(yōu)化判定，以達到總的判定次數(shù)最少。

再如，要編制一個將百分制轉換為五級分制的程序。顯然，此程序很簡單，只要利用條件語句便可完成。

程序段

if a<60 then b:='bad'

else if a<70 then b:='pass'

else if a<80 then b:='general'

else if a<90 then b:='good'

else b:='excellent';

如果上述程序需反復使用，而且每次的輸入量很大，則應考慮上述程序的質量問題，即其操作所需要的時間。因為在實際中，學生的成績在五個等級上的分布是不均勻的，假設其分布規(guī)律如表4所示:

分數(shù)

0-59

60-69

70-79

80-89

90-100

比例數(shù)

0.05

0.15

0.40

0.30

0.10

表4 分數(shù)段的分布頻率

則80%以上的數(shù)據(jù)需進行三次或三次以上的比較才能得出結果。假定以5，15，40，30和10為權構造一棵有五個葉子結點的哈夫曼樹，它可使大部分的數(shù)據(jù)經(jīng)過較少的比較次數(shù)得出結果。但由于每個判定框都有兩次比較，將這兩次比較分開，得到新的判定樹，按此判定樹可寫出相應的程序。請您自己畫出此判定樹。

假設有10000個輸入數(shù)據(jù)，若上程序段的判定過程進行操作，則總共需進行31500次比較;而若新判定樹的判定過程進行操作，則總共僅需進行22000次比較。

最優(yōu)二叉樹算法文獻

支持向量機的二叉樹多分類算法在變壓器故障診斷中的應用 支持向量機的二叉樹多分類算法在變壓器故障診斷中的應用

格式：pdf

大?。?span id="rtrofyp" class="single-tag-height">276KB

頁數(shù)： 2頁

評分： 4.4

支持向量機最初只能用以解決二分類問題,對于多類故障,只能通過組合二分類器間接應用于多類分類問題。本文提出一種基于二叉樹多分類算法對變壓器中常見故障進行了模式識別,并與傳統(tǒng)多分類算法作對比。根據(jù)svm理論結合二叉樹方法建立變壓器故障診斷模型,通過VS2008對其進行了驗證,結果表明該方法能有效地、準確地識別故障模式,具有較高的推廣性。

立即下載
一種基于有序二叉樹的變量池的設計和應用 一種基于有序二叉樹的變量池的設計和應用

格式：pdf

大?。?span id="bnad0z6" class="single-tag-height">276KB

頁數(shù)： 4頁

評分： 4.8

分層模式在軟件開發(fā)中有著廣泛的應用,必然使各層之間產(chǎn)生頻繁的數(shù)據(jù)交互,從而導致軟件性能大大下降。針對上述問題,本文提出一種基于有序二叉樹的變量池的解決方案,軟件的配置信息以及各層之間的交互數(shù)據(jù)保存在變量池中,對變量的所有操作都基于變量池,通過變量池的使用,既方便了各層之間數(shù)據(jù)交互,也簡化了各層之間的接口設計?；谠摲桨?本文最后實現(xiàn)了一個銀行自助終端系統(tǒng)。

立即下載

如果一棵具有n個結點的深度為k的二叉樹，它的每一個結點都與深度為k的滿二叉樹中編號為1~n的結點一一對應，這棵二叉樹稱為完全二叉樹。

可以根據(jù)公式進行推導，假設n0是度為0的結點總數(shù)(即葉子結點數(shù))，n1是度為1的結點總數(shù)，n2是度為2的結點總數(shù)，則 ①n= n0+n1+n2 (其中n為完全二叉樹的結點總數(shù));又因為一個度為2的結點會有2個子結點，一個度為1的結點會有1個子結點，除根結點外其他結點都有父結點，所以②n= 1+n1+2*n2 ;由①、②兩式把n2消去得:n= 2*n0+n1-1，由于完全二叉樹中度為1的結點數(shù)只有兩種可能0或1，由此得到n0=n/2 或 n0=(n+1)/2。

簡便來算，就是 n0=n/2，其中n為奇數(shù)時(n1=0)向上取整;n為偶數(shù)時(n1=1)?？筛鶕?jù)完全二叉樹的結點總數(shù)計算出葉子結點數(shù)。

查看詳情

由于網(wǎng)絡所有可能的劃分數(shù)量是巨大的，假設網(wǎng)絡的結點數(shù)和邊數(shù)分別為n和m，則所有可能的社區(qū)劃分數(shù)是一個以n為指數(shù)的數(shù)。因此，在所有可能的劃分中找出最優(yōu)劃分是一個NP-hard問題。針對這一問題，目前一些相應算法已被提出，其可以在合理的時間內(nèi)找出模塊度最大化的近似最優(yōu)劃分。

經(jīng)典貪心算法

模塊度最大化問題是一個經(jīng)典的最優(yōu)化問題，Mark NewMan 基于貪心思想提出了模塊度最大化的貪心算法FN 。貪心思想的目標是找出目標函數(shù)的整體最優(yōu)值或者近似最優(yōu)值，它將整體最優(yōu)化問題分解為局部最優(yōu)化問題，找出每個局部最優(yōu)值，最終將局部最優(yōu)值整合成整體的近似最優(yōu)值。FN算法將模塊度最優(yōu)化問題分解為模塊度局部最優(yōu)化問題，初始時，算法將網(wǎng)絡中的每個結點都看成獨立的小社區(qū)。然后，考慮所有相連社區(qū)兩兩合并的情況，計算每種合并帶來的模塊度的增量。基于貪心原則，選取使模塊度增長最大或者減小最少的兩個社區(qū)，將它們合并成一個社區(qū)。如此循環(huán)迭代，直到所有結點合并成一個社區(qū)。隨著迭代的進行，網(wǎng)絡總的模塊度是不斷變化的，在模塊度的整個變化過程中，其最大值對應網(wǎng)絡的社區(qū)劃分即為近似的最優(yōu)社區(qū)劃分。

貪心算法FN具體步驟:

去掉網(wǎng)絡中所有的邊，網(wǎng)絡的每個結點都單獨作為一個社區(qū);網(wǎng)絡中的每個連通部分作為一個社區(qū)，將還未加入網(wǎng)絡的邊分別重新加回網(wǎng)絡，每次加入一條邊，如果加入網(wǎng)絡的邊連接了兩個不同的社區(qū)，則合并兩個社區(qū)，并計算形成新社區(qū)劃分的模塊度增量。選擇使模塊度增量最大或者減小最少的兩個社區(qū)進行合并。如果網(wǎng)絡的社區(qū)數(shù)大于1，則返回步驟(2)繼續(xù)迭代，否則轉到步驟(4);遍歷每種社區(qū)劃分對應的模塊度值，選取模塊度最大的社區(qū)劃分作為網(wǎng)絡的最優(yōu)劃分。

該算法中，需要注意的是，每次加入的邊只是影響網(wǎng)絡的社區(qū)劃分，而每次計算網(wǎng)絡劃分的模塊度時，都是在網(wǎng)絡完整的拓撲結構上進行，即網(wǎng)絡所有的邊都存在的拓撲結構上。

快速模塊度優(yōu)化算法

為了降低算法的時間復雜度，Vincent Blondel等人提出了另一種層次貪心算法 。該算法包括兩個階段，第一階段合并社區(qū)，算法將每個結點當作一個社區(qū)，基于模塊度增量最大化標準決定你哪些鄰居社區(qū)應該被合并。經(jīng)過一輪掃描后開始第二階段，算法將第一階段發(fā)現(xiàn)的所有社區(qū)重新看成結點，構建新的網(wǎng)絡，在新網(wǎng)絡上重復進行第一階段，這兩個階段重復運行，直到網(wǎng)絡社區(qū)劃分的模塊度不再增長，得到網(wǎng)絡的社區(qū)近似最優(yōu)劃分。

這個簡單算法具有一下幾個優(yōu)點:首先，算法的步驟比較直觀并且易于實現(xiàn);其次，算法不需要提前設定網(wǎng)絡的社區(qū)數(shù)，并且該算法可以呈現(xiàn)網(wǎng)絡的完整的分層社區(qū)結構，能夠發(fā)現(xiàn)在線社交網(wǎng)絡的分層的虛擬社區(qū)結構，獲得不同分辨率的虛擬社區(qū);再次，計算機模擬實驗顯示，在稀疏網(wǎng)絡上，算法是時間復雜度是線性的，在合理的時間內(nèi)可以處理結點數(shù)超過10^9的網(wǎng)絡，因此十分適合在線社交網(wǎng)絡這樣超大規(guī)模的負責網(wǎng)絡中虛擬社區(qū)的發(fā)現(xiàn)。

查看詳情

是程序算法中的一種算法模式。

在二叉樹中出現(xiàn)空的子樹（包括樹葉）上增加空的樹葉，使其成為滿二叉樹的二叉樹稱之為擴充二叉樹。

查看詳情
最優(yōu)二叉樹算法相關推薦
  • 相關百科
  • 相關知識
  • 相關專欄