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

有效

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

本發(fā)明公開了一種分布式的自適應圖頂點著色方法及系統(tǒng)，包括：分別獲取無向圖中每個頂點v_i的所有鄰接頂點在上一次迭代過程中的著色信息集合C^t?1(v_i)；對每個頂點v_i進行著色沖突判斷；其中，對于任一個頂點vi，若滿足當前的概率發(fā)生器的值r_s小于等于第一閾值α并且該頂點v_i的著色信息c_i∈C^t?1(v_i)并且c_i∈B^t(v_i)，則確定該頂點v_i與其鄰接頂點產(chǎn)生著色沖突；確定每個頂點v_i對應的可用顏色集合U(v_i)，分別從每個頂點v_i對應的可用顏色集合U(v_i)中根據(jù)第二閾值β隨機選擇一個顏色，確定每個頂點v_i的著色信息c_i；對于每個頂點v_i，沿邊向其所有鄰接頂點v_j發(fā)送其著色信息c_i；若滿足每個頂點v_i的著色信息和其所有鄰接頂點的顏色均不同，則確定所述無向圖中每個頂點的著色信息。

技術(shù)領(lǐng)域

本發(fā)明涉及數(shù)據(jù)處理技術(shù)領(lǐng)域，并且更具體地，涉及一種分布式的自適應圖頂點著色方法及系統(tǒng)。

背景技術(shù)

NP-C問題是世界七大數(shù)學難題之一，即便是在信息技術(shù)高速發(fā)展的今天，各領(lǐng)域仍存在大量NP-C問題有待解決。而圖頂點著色問題(GVCP,graph vertex coloringproblem)則是最著名的NP-C問題之一。GVCP研究如何給一個無向連通圖的頂點著色，使得有公共邊的相鄰頂點的顏色不同。具體地，GVCP判定主要考慮能否用給定的k種顏色完成著色任務，而GVCP質(zhì)量優(yōu)化則致力于最小化k值，它們被廣泛應用于任務調(diào)度、寄存器分配和時間表安排等實際場景。因此，研究GVCP的判定和質(zhì)量優(yōu)化，不僅對NP-C類問題的探索與解決具有重要的理論意義，同時也有廣闊的商業(yè)應用價值。

由于直接計算GVCP的復雜度較高，目前普遍采用的方案是啟發(fā)式求解，即通過迭代逼近的方式逐步尋求最優(yōu)解。即便如此，在大數(shù)據(jù)時代，圖數(shù)據(jù)規(guī)模呈爆發(fā)式增長，致使傳統(tǒng)的集中式(單機)迭代方式仍難以在合理時間內(nèi)完成計算任務。近年來，基于云計算的新型分布式處理系統(tǒng)在計算和存儲能力方面具有良好的擴展性，可為GVCP的迭代求解提供有效支撐。其中，尤以Google公司提出的分布式圖計算系統(tǒng)Pregel及其開源實現(xiàn)與擴展如GraphLab等最為適宜。它們提供了以頂點為中心的編程接口以及性能優(yōu)化，使應用層面的用戶僅需關(guān)心業(yè)務邏輯，無需了解分布式處理細節(jié)。

在分布式圖計算系統(tǒng)中，圖頂點數(shù)據(jù)被分配到不同任務(如物理機、進程或線程等)上以便增加著色處理的并行度。某次迭代過程中，各任務上的頂點并行著色，并將各自選擇的顏色以消息的形式廣播給有邊連接的鄰接頂點，而系統(tǒng)則通過全局同步路障來協(xié)調(diào)各任務的處理進度(同步計算)并確保所有頂點在計算時能夠收到所有應該收到的消息數(shù)據(jù)。需要注意的是，本步迭代發(fā)送的消息只能在路障之后的下一步迭代中才可被使用。然而，具體到GVCP計算，邏輯上拓撲結(jié)構(gòu)相鄰的頂點在物理上可能歸屬于不同的任務，其并行著色過程中極有可能選擇相同顏色而產(chǎn)生著色沖突。另一方面，同步路障的存在導致著色信息的傳播具有滯后性，即實時性差。較差的實時性導致只有在下一步迭代才會意識到著色沖突進而繼續(xù)進行顏色選擇。但再選擇過程仍可能產(chǎn)生著色沖突，并最終陷入無限振蕩，導致算法無法收斂。為解決該問題，已有技術(shù)或者通過逐步計算獨立集然后以獨立集為單位分批順序著色，以避免相鄰頂點同時著色，或者通過破除全局同步路障的方式對著色引入隨機擾動以跳出振蕩循環(huán)。然而，前者引入額外計算開銷和獨立集結(jié)果的維護開銷，后者則因擾動的不可控性(難以復現(xiàn))極大增加了程序調(diào)試與容錯控制的難度。

發(fā)明內(nèi)容

本發(fā)明提出一種分布式的自適應圖頂點著色方法及系統(tǒng)，以解決如何高效、準確對無向圖頂點進行著色的問題。