[發(fā)明專利]一種分布式的自適應(yīng)圖頂點著色方法及系統(tǒng)

有效

• 申請?zhí)枺?/td>: 202010837566.5
• 申請日: 2020-08-19
• 公開（公告）號: CN112150581B
• 公開（公告）日: 2022-09-30
• 發(fā)明（設(shè)計）人: 王志剛;王寧;楊洋;魏志強;黃磊;劉昊;盛艷秀
• 申請（專利權(quán)）人: 中國海洋大學(xué)
• 主分類號: G06T11/60
• 分類號: G06T11/60
• 代理公司: 北京工信聯(lián)合知識產(chǎn)權(quán)代理有限公司 11266
• 代理人: 蘆玲玲

1.一種分布式的自適應(yīng)圖頂點著色方法，其特征在于，所述方法包括：

步驟1，分別獲取無向圖中每個頂點v_i的所有鄰接頂點在上一次迭代過程中的著色信息集合C^t-1(v_i)；其中，t為當(dāng)前的迭代次數(shù)；

步驟2，對每個頂點v_i進(jìn)行著色沖突判斷；其中，對于任一個頂點vi，若滿足當(dāng)前的概率發(fā)生器的值r_s小于等于第一閾值α并且該頂點v_i的著色信息c_i∈C^t-1(v_i)并且c_i∈B^t(v_i)，則確定該頂點v_i與其鄰接頂點產(chǎn)生著色沖突，更新該頂點vi對應(yīng)的狀態(tài)累積監(jiān)控變量s_i為初始閾值；其中，s_i用于記錄該頂點v_i的著色信息連續(xù)未發(fā)生變化的迭代次數(shù)；B^t(v_i)為該頂點v_i在更新時刻已經(jīng)收到的來自于當(dāng)前迭代步的且位于該頂點v_i所在任務(wù)的部分鄰接頂點的著色信息；

步驟3，確定每個頂點v_i對應(yīng)的可用顏色集合U(v_i)，分別從每個頂點v_i對應(yīng)的可用顏色集合U(v_i)中根據(jù)第二閾值β隨機選擇一個顏色，確定每個頂點v_i的著色信息c_i；

步驟4，對于每個頂點v_i，沿邊向其所有鄰接頂點v_j發(fā)送其著色信息c_i；

步驟5，判斷是否滿足每個頂點v_i的著色信息和其所有鄰接頂點的顏色均不同；其中，若滿足，則直接確定所述無向圖中每個頂點的著色信息；若不滿足，則根據(jù)運行信息調(diào)整第一閾值α和第二閾值β，并返回步驟1重新進(jìn)行迭代，直至每個頂點v_i的著色信息和其所有鄰接頂點的顏色均不同時停止，并確定所述無向圖中每個頂點的著色信息。

2.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述方法還包括：

在對每個頂點v_i進(jìn)行著色沖突判斷時，若不滿足當(dāng)前的概率發(fā)生器的值r_s小于等于第一閾值α并且該頂點v_i的著色信息c_i∈C^t-1(v_i)并且c_i∈B^t(v_i)，則確定該頂點v_i與其鄰接頂點v_j未產(chǎn)生著色沖突，更新s_i＝s_i+1，并直接進(jìn)入步驟4。

3.根據(jù)權(quán)利要求1所述的方法，其特征在于，所述方法還包括：

在進(jìn)行下一次迭代前，利用如下公式動態(tài)地調(diào)整所述第一閾值α，包括：

α＝p+(p-dv/maxd)×γ，

γ＝|V^x|/|V|，

其中，p為預(yù)設(shè)的基本閾值，取值范圍為0到1；d_v為當(dāng)前的頂點v_i的度數(shù)，maxd為所述無向圖中所有頂點的最大度數(shù)，γ為取值為0到1的收斂調(diào)控參數(shù)；|V|為所述無向圖中的全部頂點數(shù)量，|V^x|為在預(yù)設(shè)的連續(xù)x步迭代計算中顏色均未發(fā)生變化的頂點數(shù)量。