基于加權二部圖最大匹配的通信編組方法

中圖分類號：TN919 文獻標志碼：A DOI：10.3969/j.issn.1673-3819.2025.04.016

引用格式：，.基于加權二部圖最大匹配的通信編組方法[J].指揮控制與仿真，2025，47（4）：109-113.WANG SJ，YANGRP.Communicationgrouping methodofdiversifiedtasksbasedonmaximummatchingof weightedbipartite graphJ.CommandControlamp;Simulation，2025，47（4）：109-113.

Communication grouping method of diversified tasks based on maximum matching of weighted bipartite graph

WANG Shijie， YANG Ruopeng

（Schoolof InformationandCommunication，National Universityof Defenseand Technology，Wuhan 43Oooo，China）

Abstract：The informationand communication support tasksunder modemnconditionshavethecharacteristics of strong abruptness，large numberof participantsandhighdegreeofcooperation.Thisputsforwardhigherrequirements forthequality andefciencyofcommunicationgrouping.Thetraditionalgrouping modemainlyreliesonmanualmethods，，whichisdificult to adapttotheactual needsof diversified tasks.Aninteligentcommunicationgrouping methodbasedonthe maximum matchingof weightedbipartitegraphsisproposed.Throughdatacollectionandprocessing，optimizationandimprovementof two partdiagrams，introductionofjobimportance，implementationof matchingandrecommendationandothersteps，tcaoptimizethegrouping processand innovate thegrouping mode，therebyscientifically，timelyandreliablyrecommendthebest communication grouping scheme，and promote the effective playof information and communication support effiency.

Key Words：communication grouping；weighted bipartite graph；maximum matching；diversified tasks；active recommendation

信息通信保障任務中的通信編組是指在執行信息通信保障任務時，根據任務需求，將各類業務人員合理分配到相應崗位，以確保任務的順利完成。在信息通信保障任務中，通常存在任務突發、上下聯動、多方協同的特點。由于任務的復雜性和多變性，通信編組在這些情況下難以全面衡量所有業務人員在不同任務崗位上的勝任能力。不同人員的能力水平、經驗以及在不同類型任務中的表現差異，使得編組者難以在短時間內做出科學、全面、及時的人員匹配決策[1]。通過引入二部圖最大匹配思想[2]，借助智能推薦技術，通過數據處理、模型分析、排序推薦[3]，能夠在復雜情況下為信息通信籌劃者提供有效參考，提高力量編配的科學性、時效性、針對性。

1 基本概念

1.1 多樣化任務通信編組

現代條件下的通信保障任務呈現出任務類型多樣化、執行環境復雜化、參與主體多元化等趨勢。不限于傳統的軍用或應急任務，其還包括跨領域、跨行業的通信支持需求，如應對自然災害、社會公共事件、大型國際會議等場景，并且具有社會影響力大、行動時效性強等特點，需要科學編配通信力量以提供可靠的信息通信保障[4]。通信編組就是在構建通信網絡前，運用技術手段將所屬以及配屬的通信人員匹配到合適的任務崗位上，以最佳的人崗匹配結果支撐信息通信保障效能的有效發揮。

1.2 加權二部圖最大匹配

二部圖中的頂點集合可以被劃分為兩個互不相交的子集，使得圖中的每一條邊都連接兩個子集中的頂點，而同一個子集內的頂點之間則不相連。通常用數學表達式 G=（U，V，E） 表示，其中 U={u₁，u₂，…，u_n} 和 V={v₁，v₂，…，v_m} 分別表示一類頂點集合， E={e_ij} 表示兩個頂點 u_i 和 v_j 之間的連線集合。加權二部圖在二部圖的基礎上引入權重的概念，通過為邊 e_ij 賦予權重 w_ij ，表現頂點之間的關聯程度，如圖1所示。

圖1加權二部圖Fig.1Weighted bipartite graph

匹配表示在二部圖中，一個頂點最多只與一條邊相連，即任意兩條邊的頂點不相同。有權最大匹配則是指在一個帶有權重的二部圖中，找到一個匹配使得該匹配中所有邊的權重之和達到最大[5]

1.3 主動推薦技術

主動推薦技術主要根據用戶的歷史行為、興趣偏好和實際需求，為用戶提供個性化推薦服務的系統。不僅依賴于傳統的推薦方法，還結合了深度學習、強化學習、知識圖譜和情景感知等新興技術，以增強其智能化程度和適應性。推薦方法主要包括三類：基于內容的推薦、基于協同過濾的推薦和混合推薦[6]。近年來，許多學者將新技術與推薦模型相結合，提出了基于深度學習的推薦、基于強化學習的推薦、基于知識圖譜的推薦等創新方法，通過不同的算法和模型，適應多變的環境，為用戶提供更高價值的推薦目標[7]。

在本研究中，主動推薦技術主要用于為信息通信保障任務中的通信編組提供個性化的崗位匹配建議。通過分析參與者的歷史表現、技能水平和任務需求，系統能夠主動地推薦最合適的通信人員與特定任務崗位相匹配，從而提高通信編組的科學性和效率。

2基于改進加權二部圖最大匹配的力量編配推薦

2.1 總體構想

運用加權二部圖最大匹配的方法，構建通信人員U={u₁，u₂，…，u_n} 、任務崗位 V={v₁，v₂，…，v_m} 兩個頂點集；基于歷次任務進行匹配，將通信人員在不同崗位上的歷史勝任度設為 w_ij ，構成歷史勝任度 W={w_ij} 連線集，形成通信人員-任務崗位加權二部圖。由此，力量編配問題可以轉化為加權二部圖的最大匹配問題，即尋找一個匹配，使得 最大，如圖2所示。

圖2加權通信人員-任務崗位二部圖Fig.2Weightedbipartitegraphofcommunicationpersonnel-taskposts

2.2 主要步驟

1）數據采集與處理

在每次人員崗位匹配中，對任務完成情況進行評估，得到通信人員 u_i 在最近一次擔負任務崗位 v_j 的評分，記為 s_ij 。考慮隨著時間的推移，單次匹配形成的能力因遺忘效應而逐漸衰減，根據遺忘機制引入遺忘因子 λ_ij 來量化最近一次匹配中能力的衰減程度[8]。遺忘因子 λ_ij 表達如下：

其中： Φ_t 為當前時間； t_ij 表示最近一次通信人員 u_i 與任務崗位 v_j 匹配的時間； hl 為用戶的遺忘速率， hl 越大則遺忘的速度越慢， hl 越小則遺忘的速度越快[9]。由此將該通信人員在該崗位上的當前歷史勝任度表示為

w_ij=λ_ijs_ij

2）優化改進二部圖

通信人員強調“一專多能”式培養，需要具備勝任不同崗位的能力，可通過全新的匹配，賦予通信人員新的任務崗位。歷史勝任度是指通信人員在不同崗位上以往表現的綜合評估，它直接影響人員的匹配效果，因此為提升力量編配的全面性，對加權二部圖中未匹配的頂點之間進行連線，并通過預測來補充歷史勝任度。由加權二部圖可以構建歷史勝任度矩陣，再根據矩陣分解的方法，能夠有效預測空缺的歷史勝任度，從而得到完整的歷史勝任度矩陣，即得到了所有 w_ij 的值[10]，如圖3所示。

在加權二部圖最大匹配的算法中，兩邊頂點的數量保持一致，實際任務中通信人員的數量往往超過任務崗位的數量，因此需要虛設 n-m 個任務崗位，并將虛設崗位上通信人員的歷史勝任度均設為0，從而滿足模型要求。考慮到某些特殊崗位對通信人員的能力素質有特殊的要求，比如無人機中繼平臺操作手，必須具備相應的操作能力，可以將此類能力不匹配的人員崗位歷史勝任度調整為0。

圖3補充人員崗位歷史勝任度Fig.3Replenish historical competency of personnel-posts

3）引入崗位重要度

傳統的加權二部圖大多只考慮邊的影響，對頂點的影響考慮較少，然而在實際任務中，由于節點重要度、業務依賴度、環境適配度等因素的差異，不同任務中的同一崗位、同一任務中的不同崗位在重要度上是不一樣的，而重要度高的崗位必須優先考慮匹配歷史勝任度高的人員，由此增加了頂點對全局的影響。由此，可以通過層次分析法確定任務崗位重要度，將其作為頂點的固有屬性引人改進加權二部圖中，任務崗位 v_j 的重要度設為 p_j ，于是最大匹配問題的要求轉化為使得匹配度函數 最大，如圖4所示。

圖4引入崗位重要度

Fig.4Introduce post importance

4）實施匹配與推薦

在二部圖最大匹配的求解中，主流的算法有HK算法（Hopcroft-Karpalgorithm）和KM算法（Kuhn-Munkresalgorithm）。通過比較可以發現HK算法更加適合無權值二部圖的求解，能夠適應大規模數據的要求，在最大匹配的查找速度和效率上更占優勢；而KM算法更加適合加權二部圖的求解，注重權重的影響，在最大匹配的權值最大化上更占優勢[]，如表1所示。

而在改進加權通信人員-任務崗位二部圖中，數據規模較小，權重影響較大，應采取KM算法求得最大匹配，并根據匹配結果將力量編配情況推薦給信息通信籌劃者。

表1加權二部圖最大匹配算法比較

Tab.1Comparison of weighted bipartite graph maximum matching algorithms

3 算例演示

假設現有6名通信人員和4個任務崗位，需要通過合理的編組使得信息通信保障效能最大化，通過數據采集與處理、預測補充歷史勝任度、優化改進二部圖得到人員-崗位歷史勝任度評分矩陣如表2所示，崗位重要度評分如表3所示。

表2人員-崗位歷史勝任度Tab.2Historical competency of personnel-posts

表3崗位重要度

Tab.3Postimportance

由表2和表3可以將歷史勝任度與崗位重要度結合，計算出人員-崗位匹配度 w_ijp_j ，形成新的權重矩陣，如表4所示。

由此，構建了一個兩邊均有6個頂點的加權二部圖，頂點之間連線的權重為匹配度 w_ijp_j ，通過KM算法計算最大匹配，具體步驟為：

step1：初始化頂標。對每個頂點 u_i ，設置其頂標為該頂點關聯的最大邊權max w_ij ;每個頂點 v_j 頂標設為0。

表4人員-崗位匹配度

Tab.4Matching degree of personnel-posts

step2：尋找增廣路徑。逐個從頂點 u_i 出發，嘗試在當前的“相等子圖”（邊權等于兩端點頂標之和的邊構成的子圖）中使用匈牙利算法尋找增廣路徑。如果找到增廣路徑，執行step3；如果沒有找到，則執行 step4。

step3：更新匹配。如果step2中找到增廣路徑，通過反轉路徑上的匹配狀態來更新當前的匹配結果，沿增廣路徑的邊將會從未匹配狀態變為匹配狀態，而路徑上的匹配邊則變為未匹配狀態。

step4：調整頂標。如果 step2 中沒有找到增廣路徑，則根據一定的規則 U 和 u 的頂標，以擴大相等子圖。具體來說，會尋找一個差值 d ，使得將 U 中某些頂標的值減去 d，V 中某些頂標的值加上 d 后，至少有一條新的邊可以進入相等子圖。在此算例中可設定差值d=1 。而后回到 step2 ，直至更新匹配。

step5：逐個覆蓋。判斷是否所有頂點均完成匹配，若是則算法結束，若否則回到 step2 ，為下一個未覆蓋的頂點尋找增廣路徑，直到每個頂點都完成匹配。此時，得到的匹配結果即為加權二部圖的最大匹配。

算法流程圖如圖5所示。

本研究采用python語言進行代碼編寫，實現KM算法的自動運行，將人員-崗位匹配度 w_ijp_j 作為輸入，可以立即得到匹配結果為 [w₅₁，w₁₂，w₄₃，w₆₄] ，權重總和為

圖5算法流程圖

Fig.5Flowdiagramof thealgorithm

63，即通信人員 u₅ 擔負任務崗位 v₁ 、通信人員 u₁ 擔負任務崗位 v₂ 、通信人員 u₄ 擔負任務崗位 v₃ 、通信人員 u₆ 擔負任務崗位 v₄ 時，全局信息通信保障效能最高，為最佳通信編組。

4結束語

通過利用通信人員與任務崗位匹配的歷史數據，引入加權二部圖最大匹配思想，采用KM算法，可以有效解決通信編組隨意性大、時效性弱、可靠性差等問題，能夠較好適應現代多樣化任務的特點規律，為提高信息通信籌劃的信息化、智能化水平發揮積極作用。

參考文獻：

[1] 王會濤，楊若鵬，張晨.面向工程化的戰術通信網網絡規劃問題研究[C]//中國指揮與控制學會第十屆中國指揮控制大會論文集（下冊）.，2022：5.D0I：10.26914/c.cnkihy.2022.018873.WANGHT，YANG RP，ZHANG C.Researchonnetworkplanningoftactical communicationnetworkforen-gineering[C]//Chinese Institute of CommandandControl.Proceedings of the 1Oth Chinese Command andControl Conference（VolumeI）.School of InformationandCommunication，National UniversityofDefenseandTechnology，2022：5．D01：10. 26914/c .cnkihy.2022.018873.

[2] 謝志遠.關于二部圖與匹配問題的研究[D].洛陽：河南科技大學，2014.XIE ZY. Research on bipartite graph and matching prob-

lem[D].Luoyang：Henan University of Science and

Technology，2014.

[3］潘微科，林晶，明仲.智能推薦技術[M].北京：清華大學出版社，2022.PAN WK，LIN J，MING Z. Intellgent recommendationtechnology[M].Beijing：TsinghuaUniversityPress，2022.

[4]寧靜.武警部隊通信保障措施研究[J].中國新通信，2021，23（2） ： 37-38.NING J. Research on communication safeguard measuresfor the People's Armed Police[J]. China New Communi-cations，2021，23（2）：37-38.

[5]徐俊明.圖論及其應用[M].4版.合肥：中國科學技術大學出版社，2019.XU JM.Graph theory with applications[M]. 4th ed.Hefei：University of Science and Technology of ChinaPress，2019.

[6]王喆.深度學習推薦系統[M].北京：電子工業出版社，2020.WANG Z. Deep learning recommender system[M]. Bei-jing：Publishing House of Electronics Industry，2020.

[7］胡琪，朱定局，吳惠糞，等.智能推薦系統研究綜述[J].計算機系統應用，2022，31（4）：47-58.HU Q，ZHU D J，WU H L，et al. Survey on intelligentrecommendation system[J]. Computer Systems amp; Appli-cations，2022，31（4）：47-58.

[8]YUAN C，GUANG Q.Model bloggers‘ interests based onforgetting mechanism[C].Proceeding of the 17th Interna-tional Conference on World WideWeb.

[9]劉曉光，謝曉堯.一種結合遺忘機制與加權二部圖的推薦算法[J]．河南科技大學學報（自然科學版），2015，36（3） ： 48-53.LIU XG，XIE X Y.A recommendation algorithm combi-ningforgeting mechanism and weighted bipartite graph[J].Journal ofHenanUniversity ofScienceandTechnology（Natural Science），2015，36（3）： 48-53.

[10]KORENY，BELL R，VOLINSKYC.Matrix factorizationtechniques for recommend systems[J]. IEEE Computer，2009，42（8） ：30-37.

[11］王桂平，楊建喜，李韌.圖論算法理論、實現及應用[M].2版.北京：北京大學出版社，2022.WANGGP，YANG JX，LIR.Theory，realization andapplication of graph theoryalgorithm[M].2nd ed.Beijing：Peking University Press，2022.

（責任編輯：許韋韋）