熊小華，寧愛兵

（1. 上海第二工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院, 上海 201209；2. 上海理工大學(xué)管理學(xué)院, 上海 200093）

度約束最小生成樹的元胞競爭決策算法

熊小華1，寧愛兵2

（1. 上海第二工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院, 上海 201209；2. 上海理工大學(xué)管理學(xué)院, 上海 200093）

度約束最小生成樹(Degree-Constrained Minimum Spanning Tree, 簡記DCMST)是網(wǎng)絡(luò)設(shè)計(jì)和優(yōu)化中的一個(gè)經(jīng)典的組合優(yōu)化難題。競爭決策算法是一種特別適合于求解組合優(yōu)化難題的新型算法。為了提高求解DCMST問題的求解精度，將元胞自動(dòng)機(jī)的鄰居演化原理和競爭決策算法相結(jié)合——元胞競爭決策算法來求解DCMST；為了提高算法的效率，分析了度約束最小生成樹問題的數(shù)學(xué)性質(zhì)并利用這些性質(zhì)對問題實(shí)現(xiàn)降階。降階過程會(huì)有效降低問題處理的規(guī)模。為了驗(yàn)證算法的性能，采用Delphi 7.0實(shí)現(xiàn)算法，經(jīng)過數(shù)據(jù)測試和驗(yàn)證，并與其他算法的結(jié)果進(jìn)行比較，證明了算法的有效性。

競爭決策算法；元胞自動(dòng)機(jī)；度約束最小生成樹；降階

0 引言

最小生成樹(Minimum Spanning Tree，簡記MST)[1-2]問題是一個(gè)經(jīng)典的組合優(yōu)化問題，許多工程問題如管道鋪設(shè)、電路設(shè)計(jì)、交通網(wǎng)絡(luò)等，通常都可轉(zhuǎn)化為最小生成樹問題。最小生成樹是構(gòu)造一個(gè)帶權(quán)圖的最小代價(jià)生成樹，可使用避圈法、破圈法等成熟的方法求解[3]。但如果對樹的各頂點(diǎn)度數(shù)加以限制，即不超過預(yù)先給定的數(shù)值，則問題的性質(zhì)變得截然不同，這就是所謂的度約束最小生成樹(Degree-Constrained Minimum Spanning Tree, 簡記DCMST)，其組合含義就是從所有的生成樹中(數(shù)目可達(dá)nn-2)找出所有頂點(diǎn)符合約束且權(quán)值最小的生成樹?，F(xiàn)實(shí)世界中有許多這樣的例子，如管道鋪設(shè)、電路設(shè)計(jì)等，為了可靠性而要求頂點(diǎn)度數(shù)符合一定的規(guī)定。

DCMST問題的求解難度隨各頂點(diǎn)度約束的不同而不同。設(shè)各個(gè)頂點(diǎn)的度約束為bi(i=1,2,…,n)。當(dāng)bi至少為n-1時(shí)，即為無限制情況下的一般的MST問題；而當(dāng)bi都為2時(shí)，則是著名的TSP問題，TSP問題是NP難題，是否存在有效算法尚不可知。當(dāng)所有頂點(diǎn)的度約束值相同且都為一常數(shù)c時(shí)，度約束最小生成樹問題又稱為d-MST問題。因此，就一般情形而言，DCMST問題是一個(gè)難解難題。曾經(jīng)有一些學(xué)者采用精確算法(如分支定界法、隱枚舉法等)都是指數(shù)級別運(yùn)行時(shí)間，無法求解中型以上規(guī)模的實(shí)際問題。本文利用元胞競爭決策算法，給出求解DCMST問題的一種新思路，經(jīng)過大量的算例測試，效果優(yōu)于目前的常見算法，體現(xiàn)了算法的優(yōu)越性。

1 競爭決策算法簡介

競爭決策算法(Competitive Decision Algorithm，簡記CDA)是近幾年來提出的一種求解組合優(yōu)化難題的新算法[4-10]。通過觀察自然界中的競爭和決策發(fā)現(xiàn)，它們都是在一定競爭規(guī)則下，在競爭者的實(shí)力、競爭者和環(huán)境間的關(guān)系、多個(gè)競爭者實(shí)力的差距和初始競爭狀態(tài)等多種因素的共同作用下，經(jīng)過多次競爭和決策后，使不同的競爭者分別占有一定的資源而達(dá)到一種新的競爭狀態(tài)。只要新的競爭狀態(tài)優(yōu)于初始競爭狀態(tài)，算法就會(huì)達(dá)到優(yōu)化的目的。算法吸收了達(dá)爾文“優(yōu)勝劣汰”的進(jìn)化思想以及演化博弈論中有限理性競爭者的思想，通過構(gòu)造一個(gè)或多個(gè)具有有限理性的競爭者參與到對一個(gè)或多個(gè)資源的競爭過程中，通過優(yōu)勝劣

2 元胞自動(dòng)機(jī)簡介

元胞自動(dòng)機(jī)最早由馮·諾依曼提出。沃爾夫勒姆等[10-11]將動(dòng)力系統(tǒng)方法、計(jì)算理論及形式化語言方法引入元胞自動(dòng)機(jī)的研究中，促進(jìn)其廣泛應(yīng)用。

元胞自動(dòng)機(jī)是一個(gè)時(shí)間和空間都離散的動(dòng)力學(xué)系統(tǒng)，由元胞、狀態(tài)、鄰居和規(guī)則四部分組成。用數(shù)學(xué)符號表示，標(biāo)準(zhǔn)的元胞自動(dòng)機(jī)是一個(gè)四元組： A=(Ld, S, N, f), 其中A代表一個(gè)元胞自動(dòng)機(jī)系統(tǒng)；L代表元胞空間，d表示元胞空間的維數(shù)；S表示元胞有限的、離散的狀態(tài)集合；N表示所有領(lǐng)域內(nèi)元胞的組合，記為N=(S1,S2,…,Sn), n是元胞鄰居的個(gè)數(shù)。每個(gè)元胞至少要有一個(gè)鄰居，在一個(gè)固定距離的范圍內(nèi)，鄰居可以直接訪問它，而在范圍之外，對它沒有直接的影響。元胞鄰居的定義有多種方法，如馮·諾依曼(Von Neumann)型、摩爾(Moore)型、擴(kuò)展的摩爾(Moore)型等。f是一個(gè)局部轉(zhuǎn)換函數(shù)，轉(zhuǎn)換規(guī)則定義了系統(tǒng)的動(dòng)力學(xué)行為。

元胞空間內(nèi)的每個(gè)元胞遵循相同的演化規(guī)則，而大量的元胞通過簡單的相互作用而構(gòu)成動(dòng)態(tài)系統(tǒng)的演化。元胞在元胞空間里，按照演化規(guī)則有很多種變化。若元胞的狀態(tài)有k種，狀態(tài)的更新由自身及鄰居n個(gè)元胞的狀態(tài)共同決定，則可能有的狀態(tài)有種，元胞的鄰域能產(chǎn)生很多變化，這將增加群體的多樣性，提高進(jìn)化的收斂速度，也能更加自然地模擬自然進(jìn)化智能。元胞自動(dòng)機(jī)具有重復(fù)簡單的演化規(guī)則導(dǎo)致復(fù)雜的系統(tǒng)行為的能力，通過局部的變化可以實(shí)現(xiàn)全局計(jì)算。這也是擬將元胞自動(dòng)機(jī)引入競爭決策算法的原因所在。

3 DCMST的元胞競爭決策算法

3.1 問題介紹

考慮一個(gè)連通的無向簡單圖[12-13](無環(huán)無多重邊的圖即為簡單圖) G=(V,E,W)，其中V={1,2,…,n}為頂點(diǎn)集， E={e1, e2,…,em}為邊集，若邊ek的的頂點(diǎn)為i和j，則邊ek可記為(i, j)。各頂點(diǎn)間的權(quán)值wij已知(wij＞0, wii=∞, i, j∈V)，各頂點(diǎn)的度限制為bi(i =1,2,…,n)。

設(shè)

則度約束最小生成樹問題的數(shù)學(xué)模型可以寫成：

這里|S|為集合S中所含圖G的頂點(diǎn)個(gè)數(shù)。前兩個(gè)約束保證所得到的是一棵樹，第三個(gè)約束為頂點(diǎn)度約束。

3.2 DCMST性質(zhì)的分析

不同于其他啟發(fā)式算法，競爭決策算法具有便于結(jié)合問題本身性質(zhì)的特性，這將加快問題的求解速度。為了降低問題的求解難度，在討論DCMST問題的元胞競爭決策算法之前，先討論問題本身的性質(zhì)。

定理1 圖G中所有的懸掛點(diǎn)(即度為1的頂點(diǎn)) 所關(guān)聯(lián)的邊一定在度約束最小生成樹上T*。

證明 因?yàn)槎燃s束最小生成樹T*是連通的，因此，若存在度約束最小生成樹，則懸掛點(diǎn)所關(guān)聯(lián)的邊一定在度約束最小生成樹中。否則，T*必定不是連通的。

由定理1可知，可利用定理1對問題進(jìn)行降階處理。在算法最開始，將所有懸掛點(diǎn)及其關(guān)聯(lián)邊從圖中移除，此時(shí)可能產(chǎn)生新的懸掛點(diǎn)，可以繼續(xù)應(yīng)用定理1降階，直到不存在懸掛點(diǎn)為止。

證明 使用反證法。

假設(shè)有一條E1中的邊(vi, vj)在度約束最小生成樹T*上。由于vi, vj都是度限制為1的頂點(diǎn)，故這兩個(gè)頂點(diǎn)都不能與頂點(diǎn)集V中其他的頂點(diǎn)有邊相連，此時(shí)，與T*是度約束最小生成樹相矛盾。所以假設(shè)錯(cuò)誤，E1中所有的邊一定不在度約束最小生成樹上T*。

應(yīng)用定理2可以快速排除一定不在度約束最小生成樹上的邊。對于關(guān)聯(lián)的兩個(gè)頂點(diǎn)都是度限制為1的邊，由定理2可知，可以快速排除一定不在度約束最小生成樹上，將這些邊從原圖上移除，這將進(jìn)一步降低問題求解的規(guī)模。

定理3 若vk是圖G中的一個(gè)度為2的結(jié)點(diǎn)，且結(jié)點(diǎn)vi, vj是與之相鄰的兩個(gè)結(jié)點(diǎn)，若vi, vj相連的所有路徑都必須通過結(jié)點(diǎn)vk，則邊(vi, vk)和(vk, vj)一定在度約束最小生成樹上T*。

證明 使用反證法。

假設(shè)邊 (vi, vk)和 (vk, vj)不在T*上。由于不存在一條將vi、vj相連的路徑不經(jīng)過結(jié)點(diǎn)vk，而由假設(shè)知道(vi, vk)和(vk, vj)不在T*上，因此，T*此時(shí)一定不連通，這與T*是度約束最小生成樹相矛盾。假設(shè)錯(cuò)誤，邊(vi, vk)和 (vk, vj)一定在度約束最小生成樹上T*。

應(yīng)用定理3可以用來快速判斷一定在度約束最小生成樹上的邊。對于度為2的頂點(diǎn)vk，若其關(guān)聯(lián)的兩個(gè)頂點(diǎn)在與vk斷開的情況下不可達(dá)的話，則可以判斷vk關(guān)聯(lián)的兩條邊一定在度約束最小生成樹上。這又將降低問題求解的規(guī)模與難度。

3.3 算法原理

n個(gè)頂點(diǎn)的度約束最小生成樹共有n-1條邊，只有一個(gè)連通分支，且不存在回路，因此可以把求解度約束最小生成樹問題看作是按照競爭力和決策原則把n-1條邊依次加入到初始無邊且包含n個(gè)頂點(diǎn)的圖中。在邊加入的過程中必須保證不形成任何子回路且不超過頂點(diǎn)的度限制值。本算法只有一個(gè)非虛擬競爭者A，即初始無邊且包含n個(gè)頂點(diǎn)的圖，被競爭的資源為所有邊資源，初始格局是競爭者沒有占有邊資源，為虛擬競爭者N所占用，競爭結(jié)束時(shí)競爭者A應(yīng)占有n-1條邊。

3.4 基本符號及含義

為了方便描述，本文采用如下符號來表示。

n: DCMST問題的頂點(diǎn)個(gè)數(shù)；

w[i, j]: 權(quán)值矩陣，表明頂點(diǎn)i與j連線的的權(quán)值；

b[i]: 第i個(gè)頂點(diǎn)的度數(shù)約束；

dot_num[i]: 第i個(gè)頂點(diǎn)當(dāng)前的度數(shù)；

cur_b[i]: 第i個(gè)頂點(diǎn)當(dāng)前可連的邊數(shù)，cur_b[i]= b[i]- dot_num[i]；

arrive_w[i, j]: 鄰接矩陣，表明頂點(diǎn)i與j是否直接相鄰;

t_arrive_w[i, j]: arrive_w[ ]的傳遞對稱閉包[12]，表明頂點(diǎn)i與j是否能夠到達(dá)(包含通過其它結(jié)點(diǎn)中轉(zhuǎn)到達(dá));

All_line[i]：這是一個(gè)邊的集合，即圖中所有與頂點(diǎn)i關(guān)聯(lián)的邊;

Line[i]：All_line[i]的子集，邊的一個(gè)頂點(diǎn)為i，設(shè)邊的另一個(gè)頂點(diǎn)編號為k，則滿足t_arrive_w[i,k]=0，即結(jié)點(diǎn)k在當(dāng)前圖中不能到達(dá)(含傳遞到達(dá))頂點(diǎn)i;

dw[i,k]: Line[i]中權(quán)值第k小邊的權(quán)值(其中1≤k≤2);

dw_j [i,k]：Line[i]中權(quán)值第k小邊的另一個(gè)頂點(diǎn)的編號(一個(gè)頂點(diǎn)編號為i，其中1≤k≤2);

power[i]：圖對頂點(diǎn)i的競爭力函數(shù)值，即把邊（i, dw_j [i,1]）加入到圖中的能力；

max_power_id：當(dāng)前決策函數(shù)選中頂點(diǎn)的編號，即按照當(dāng)前競爭力和決策函數(shù)，下一次加入到圖中的邊為（max_power_id, dw_j [max_power_id, 1]）；

3.5 初始狀態(tài)、競爭力函數(shù)、決策函數(shù)和元胞及元胞演化規(guī)則

(1) 初始狀態(tài)

反復(fù)應(yīng)用定理1、定理2和定理3后，在原圖上存在的是無法確定是否在度約束最小生成樹上的邊資源。初始狀態(tài)只有一個(gè)。虛擬競爭者N占有所有未確定邊資源。競爭者A占有確定一定在度約束最小生成樹上的邊資源。

(2) 競爭力函數(shù)

本算法所采用的競爭力函數(shù)的基本思想可描述如下：DCMST中與每一頂點(diǎn)相連的邊至少有一條在樹中，因此，把權(quán)值為dw[i,1]的邊稱為基本邊，而把權(quán)值為dw[i, 2]稱為候補(bǔ)邊。為了取得好的效果，應(yīng)該在滿足度約束的條件下，把候補(bǔ)邊與基本邊差距最大的邊優(yōu)先加入到圖中以減少因?yàn)榛具叢荒芗尤氲綀D中而造成較大的損失。

本算法采用以下三個(gè)競爭力函數(shù)：

(i) power[i]=1/ dw[i, 1]，滿足條件的邊中權(quán)值最小的競爭力最大；

(ii) power[i]= dw[i, 2] - dw[i, 1]，候選邊與基本邊權(quán)值差距最大的邊競爭力最大；

(iii) power[i]=( dw[i, 2] - dw[i, 1])-( dw[i, 1]- dw[k, 1]) (k= dw_j [i, 1])，它在競爭力函數(shù)(ii)的基礎(chǔ)上，考慮邊(i, k)加入到圖中對頂點(diǎn)k的基本邊造成的損失值(dw[i,1]- dw[k,1])。

(3) 決策函數(shù)

決策函數(shù)分兩種情況來介紹：

(i) 當(dāng)競爭者占有的資源(即邊的條數(shù))小于n-2

在滿足條件的頂點(diǎn)中選擇power[i]值最大的。若兩個(gè)頂點(diǎn)的power[i]值相同時(shí)，則選擇編號小的頂點(diǎn)。(ii) 當(dāng)競爭者占有的資源(即邊的條數(shù))等于n-2(即此時(shí)僅剩最后一條邊)

當(dāng)目前競爭者手頭已經(jīng)找到了n-2條邊，此時(shí)只剩下一條邊就找到了DCMST的所有邊，因此，從所有能加入到DCMST中且權(quán)值最小的邊給競爭者。

(4) 元胞、鄰居定義及元胞演化規(guī)則

定義2 元胞鄰居采用擴(kuò)展Moore鄰居類型，

其中diff(CellY?CellX)≤r 為兩個(gè)組合取值的差異，若無差異為0，有差異時(shí)，最小為2。r為差異的程度，本文中r為2。

定義3 元胞演化規(guī)則：依據(jù)元胞鄰居的定義計(jì)算其鄰居（與中心元胞相差一條邊的生成樹）的目標(biāo)解，比較中心元胞和其鄰居的差異，選擇最好的目標(biāo)解。

定義4 元胞自動(dòng)機(jī)邊界條件，為了更好的模擬無限空間，采用周期型空間定義。

3.6 算法流程

步驟1 重復(fù)剔除整體上的劣質(zhì)資源或重復(fù)固定整體上的優(yōu)秀資源

按照定理1，2，3確定一定在與一定不在度約束最小生成樹上的邊資源；

設(shè)ini_line_count為固定下來的邊資源；

步驟2 初始化

最大的競爭步數(shù)=n；

p_count=3; d_count=1; la_count=1 //此三項(xiàng)分別為競爭力函數(shù)、決策函數(shù)和初始格局的個(gè)數(shù)

步驟3 競爭、決策及資源交換

for p=1 to p_count //競爭力函數(shù)個(gè)數(shù)循環(huán)

for d=1 to d_count //決策函數(shù)個(gè)數(shù)循環(huán)

for la =1 to la_count //初始格局個(gè)數(shù)循環(huán)

arrive_w和t_arrive_w矩陣全為0；

計(jì)算每個(gè)頂點(diǎn)的dw[i, 1], dw_j[i, 1], dw [i, 2], dw_j[i, 2]；

根據(jù)第p個(gè)競爭力函數(shù)計(jì)算power[i]；

根據(jù)power[i]計(jì)算max_power_id ； （這里的 1≤i≤n）

競爭步數(shù)=0; line_count=ini_line_count； //圖中邊的個(gè)數(shù)

每個(gè)頂點(diǎn)的cur_b[i]=b[i]-在優(yōu)質(zhì)邊資源上的度消耗；

步驟3.1 本輪競爭階段1: 資源分配和爭奪階段

repeat

dot_1=max_power_id; //要加入邊的一個(gè)頂點(diǎn)編號

dot_2= dw _j[dot_1,1]; //要加入邊的另一個(gè)頂點(diǎn)編號

競爭步數(shù)=競爭步數(shù)+1;

line_count= line_count+1;

cur_b[i]= cur_b[i]-1;

arrive_w[dot_1, dot_2]= true; arrive_w[dot_2, dot_1]= true;

for i=1 to n //當(dāng)在圖上添加一條邊(dot_1,dot_2)時(shí)更新t_arrive_w[ ]矩陣

if (t_arrive_w[i,dot_1]=true) or(i=dot_1) then //與結(jié)點(diǎn)dot_1關(guān)連的點(diǎn)i,

for j=1 to n

if (t_arrive_w[j, dot_2]=true) or(j=dot_2) then //與結(jié)點(diǎn)dot_2關(guān)連的點(diǎn)j,

if (i＜＞j) then

{t_arrive_w[i, j]=true; t_arrive_w[j, i]=true}

重新計(jì)算一部分結(jié)點(diǎn)的dw [i, k], dw_j[i, k]（這里只重新計(jì)算因?yàn)檫?dot_1, dot_2)加入到圖中而發(fā)生變化的點(diǎn)，其中1≤k≤2）;

根據(jù)第p個(gè)競爭力函數(shù)重新計(jì)算一部分由于邊(dot_1, dot_2)加入到圖中而發(fā)生變化點(diǎn)的power[i] ;

根據(jù)決策函數(shù)計(jì)算max_power_id;

until (line_count=n-1 or競爭步數(shù)＞=最大的競爭步數(shù))

根據(jù)矩陣arrive_w和矩陣w得到度約束最小生成樹的路徑和總權(quán)值。

將本輪競爭取得的結(jié)果與保存的最優(yōu)解比較其占優(yōu)情況，若優(yōu)于保存的最優(yōu)解，則替換之。

步驟3.2 本輪競爭階段2：元胞演化

按元胞鄰居的定義，以當(dāng)前求得目標(biāo)最好的解為中心元胞，尋找所有的鄰居。在鄰居范圍內(nèi)演化，按照定義的演化規(guī)則，若鄰居的解優(yōu)于目前最好解，并替換最好解。

步驟4 輸出競爭決策得到的結(jié)果解。

4 數(shù)值算例

為了驗(yàn)證算法的有效性，在Windows XP下用Delphi 7.0實(shí)現(xiàn)了該算法，并用來求解了大量的度約束最小生成樹問題，算法求解的效果良好。限于篇幅，這里給出一個(gè)小規(guī)模算例的計(jì)算結(jié)果及邊資源情況。

算例n=9，度約束b={2, 1, 4, 2, 3, 2, 1, 5, 1}，給定圖的權(quán)值矩陣如下：

解

競爭決策算法的求解結(jié)果為2 900。

由定理2降階可知：(2,7), (2,9), (7,9)必定不在度約束最小生成樹上。

用元胞競爭決策算法程序求解得：生成樹權(quán)值為2 890，連線T= {(1,3), (1,6), (2,3), (3,5), (4,6), (4,8), (7,8), (8,9)}。

5 結(jié)束語

競爭決策算法是一種能廣泛應(yīng)用于求解各類組合優(yōu)化難題的新型尋優(yōu)算法，其通用性和實(shí)用性都比較強(qiáng)，在離散空間問題求解中，表現(xiàn)出其優(yōu)越性。將元胞自動(dòng)機(jī)理論局部更新引起全局計(jì)算的特性與競爭決策算法原理相結(jié)合用來求解度約束最小生成樹問題，進(jìn)一步豐富了競爭決策算法的理論基礎(chǔ)。整個(gè)算法操作簡單，具有較好的通用性。試驗(yàn)結(jié)果表明，算法具有較好的效果。

[1] AHUJA R K, MAGNANTI T L, ORLIN J B. Network Flows: Theory, Algorithms, and Applications (English Version) [M]. Beijing: Mechanical Industry Press, 2005.

[2] SYSLO M M, DEO N, KOWALIK J S. Discrete Optimization Algorithms [M]. Englewood Cliffs, New Jersey: Prentice-Hall, Inc., 1983:370-373.

[3] 馬良, 朱剛, 寧愛兵. 蟻群優(yōu)化算法[M]. 北京: 科學(xué)出版社, 2008.

[4] 寧愛兵, 馬良. 競爭決策算法及其在車輛路徑問題中的應(yīng)用[J]. 管理科學(xué)學(xué)報(bào), 2005, 8(6):10-18.

[5] 寧愛兵, 馬良. 度約束最小生成樹(DCMST)的競爭決策算法[J]. 系統(tǒng)工程學(xué)報(bào), 2005, 20(6): 630-634.

[6] 寧愛兵, 馬良, 熊小華. 競爭決策算法原理及其應(yīng)用[J]. 上海理工大學(xué)學(xué)報(bào), 2008, 30(4): 369-373.

[7] 寧愛兵, 馬良. 大規(guī)模旅行商問題(TSP)的競爭決策算法[J]. 計(jì)算機(jī)工程, 2005, 31(9): 23-26.

[8] 寧愛兵,馬良. 0-1背包問題競爭決策算法[J]. 計(jì)算機(jī)工程與應(yīng)用, 2008, 44(3): 14-16,38.

[9] 熊小華, 寧愛兵, 馬良. 基于多交換鄰域搜索的多維0/1背包問題競爭決策算法[J]. 系統(tǒng)工程理論與實(shí)踐, 2010, 30(8): 1448-1456.

[10] WOLFRAM S. Theory and pplication of Cellular Automata[M]. Singapore: The World Scientific Publishing Company Limitd, 1986.

[11] WOLFRAM S. Computation theory of cellular automata[J]. Communications in Mathematical Physics, 1984, 96(1): 15-57.

[12] 左孝凌, 李為監(jiān), 劉永才. 離散數(shù)學(xué)[M]. 上海: 上?？茖W(xué)技術(shù)文獻(xiàn)出版社, 1982.

[13] 盧開澄. 計(jì)算機(jī)算法導(dǎo)引[M]. 北京: 清華大學(xué)出版社, 1996.

Cellular Competitive Decision Algorithm for Degree-Constrained Minimum Spanning tree Problem

XIONG Xiao-Hua1, NING Ai-Bing2
(1. College of Computer and Information, Shanghai Second Polytechnic University, Shanghai 201209, P. R. China; 2. School of Management, University of Shanghai for Science and Technology, Shanghai 200093, P. R. China)

Finding the Degree-Constrained Minimum Spanning Tree (DCMST for short) of a graph is a classical combinatorial optimization hard problem in network-designing and optimization. Competitive decision algorithm (CDA for short) is a new type algorithm especially suitable for solving combinatorial optimization problems. Cellular competitive decision algorithm for DCMST is presented here to improve the accuracy of the solution, which introduced the neighborhood evolution of cellular automata into CDA. To speed up the algorithm, the mathematical properties of DMST are used to reduce the scale of instances. To verify the effectiveness of the algorithm, it is being coded in Delphi 7.0 and series of instances are tested here.

competitive decision algorithm; cellular automata; degree-constrained minimum spanning tree; reduction

O223, TP301

A

2011-02-20;

2011-08-04

熊小華（1978－），女，江西南昌人，博士，講師，研究方向?yàn)樗惴ㄔO(shè)計(jì)、系統(tǒng)工程，電子郵箱xiong_xiao_hua@163.com。

國家自然科學(xué)基金項(xiàng)目（No. 70871081），上海市重點(diǎn)學(xué)科建設(shè)基金項(xiàng)目（No. S30504）汰的原則使一部分競爭者獲得資源而增加實(shí)力，一部分競爭者失去資源削弱實(shí)力甚至消亡。當(dāng)算法通過競爭不能獲得更優(yōu)的結(jié)果時(shí)，通過資源交換使算法進(jìn)入下一輪的競爭。在理論方面，現(xiàn)在已給出了競爭決策算法的通用流程、特點(diǎn)、分類、主要概念及其數(shù)學(xué)描述、常用的競爭力函數(shù)、常用的決策函數(shù)、常用的初始狀態(tài)以及常用的資源交換規(guī)則等。在應(yīng)用方面，已利用其通用流程實(shí)現(xiàn)了車輛路徑問題[4]、度約束最小生成樹[5]、旅行商問題[7]、背包問題[8-9]等NP難題的算法并編程實(shí)現(xiàn)。

1001-4543(2011)03-0207-07