%function [e,c]=GCPanneal1(L,s,t,dt,lamda,d,b,n)
%
%圖著色問題(Graph Colouring Problem)的退火算法
%GCP問題可看為將頂點(diǎn)集劃分為最少個(gè)數(shù)獨(dú)立集的問題
%
%求解此問題有兩種算法，
%GCPanneal1適用于度數(shù)小于20的情形
%GCPanneal2適用于各種度數(shù)
%在GCPanneal1中，w(i)表示賦予顏色i的權(quán)值
%
%n為問題規(guī)模，即節(jié)點(diǎn)個(gè)數(shù)；b為關(guān)聯(lián)矩陣
%lamda是一個(gè)大于1的罰函數(shù)因子
%d為圖G的最大度數(shù)，最小著色上界為d+1
%e(u)表示u被著的顏色號(hào)
%c(i)表示著以顏色i的頂點(diǎn)個(gè)數(shù)
%
%L可取較大值，如500、1000；
%s取1、2等；t為初始溫度，參考范圍為0.5--2；
%dt為衰減因子，一般不小于0.9;
%L、s、t、dt應(yīng)通過多次試驗(yàn)來確定，以獲得優(yōu)化的結(jié)果
%參考《非數(shù)值并行算法--模擬退火算法》科學(xué)出版社

function [e,c]=GCPanneal1(L,s,t,dt,lamda,d,b,n)
w(1)=2^d;
for j=2:(d+1)
    w(j)=2*w(j-1)-w(1)-1;
end
%賦權(quán)

e=zeros(1,n);
e=e+1;
c=zeros(1,d+1);
c(1)=n;
%設(shè)定初始解

s0=0;
while 1
    a=0;
    for k=1:L
        [u,i,j,df]=GCPgen1(e,d,b,n,w,lamda);
        if GCPacc1(df,t)
              e(u)=j;c(i)=c(i)-1;c(j)=c(j)+1;
              a=1;
        end
    end
    fprintf('圖中各點(diǎn)被著的顏色號(hào)\n');
    disp(e);
    fprintf('著以各顏色的頂點(diǎn)個(gè)數(shù)\n');
    disp(c);
    t=t*dt
    if a==0
        s0=s0+1;
    else 
        s0=0;
    end
    if s0==s
        break;
    end
end