任務與資源匹配問題的經(jīng)典算法分析概述目錄TOC\o"1-3"\h\u21642任務與資源匹配問題的經(jīng)典算法分析概述 1281321.1二分查找算法與二分圖 134421.1.1二分查找算法 1275551.1.2二分圖 2234061.2匈牙利算法 2271741.3KM算法 3276881.4Gale-Shapley算法 3在研究任務分配和資源匹配方案時，需要采用二分查找法來得到與任務大小相適應的待分配任務集合大小，然后利用該集合大小調(diào)用基于二分圖的優(yōu)化分配模塊來匹配任務執(zhí)行節(jié)點。基于二分圖的優(yōu)化匹配模塊需要調(diào)用KM算法模塊來得到任務與任務執(zhí)行節(jié)點的集合。在KM算法模塊中，需要用到匈牙利算法和深度優(yōu)先搜索算法來進行輔助運算。1.1二分查找算法與二分圖1.1.1二分查找算法二分查找算法是一種常用的查找方法，能夠?qū)⒕€性的查找時間提升到對數(shù)范圍，大大提高查找效率[[][]羅南超,蹇旭,崔麗.一種改進的新二分查找算法的研究與實現(xiàn)[J].計算機時代,2009(07):56-57.假設(shè)有一升序的數(shù)據(jù)集合，二分查找法通過變量left（數(shù)據(jù)集左邊界值）和rig?t（數(shù)據(jù)集右邊界值）控制一個循環(huán)來查找目標元素。首先，將left設(shè)置為0，rig?t設(shè)置為n?1。在循環(huán)的迭代過程中，將middle設(shè)置為left和rig?t所在區(qū)間內(nèi)數(shù)據(jù)集合的中間值，如果middle小于目標值，將middle的后一個元素的值賦值給左邊界值left，即原middle后一個元素的值與rig?t所在區(qū)間內(nèi)的數(shù)據(jù)集合成為下一個要查找的區(qū)間；如果middle大于目標值，則將middle的前一個元素的值賦值給右邊界值rig?t，即left與原middle前一個元素的值所在區(qū)間的數(shù)據(jù)集合成為下一個要查找的區(qū)間。隨著查找的進行，left往右移，rig?t往左移。當middle與目標值相同時，查找停止；當left與rig?t重合時，查找結(jié)束，且查找的數(shù)據(jù)集合內(nèi)沒有目標值。二分查找的復雜度取決于查找過程中可能的最大分區(qū)次數(shù)。在沒有找到目標，即分區(qū)次數(shù)最大時，算法時間復雜度為Olgn[[][]鄒國霞,何南.一種改進的二分查找算法[J].軟件導刊,2010,9(03):53-55.1.1.2二分圖二分圖又稱作二部圖，是圖論中的一種特殊模型。設(shè)G=V,E是一個無向圖，如果頂點集V可分割為兩個互不相交的子集X和子集Y，并且圖G中每條邊所連接的兩個頂點一個在子集X中，另一個在子集Y中，則稱圖G在二分圖G的一個子圖M中，若M的邊集E中的任意兩條邊都依附于不同的頂點，則稱M是一個匹配。如果在圖G的一個匹配中，X≤Y且匹配數(shù)M=二分圖G的每條邊都對應一個權(quán)重，使得所有匹配邊的權(quán)重和最大的完備匹配方案，記作最優(yōu)完備匹配。G中每個X和Y都有對應的頂標值，每條邊都有一個權(quán)重W，頂標值之和等于邊權(quán)重的邊構(gòu)成的子圖，就是相等子圖。1.2匈牙利算法一般使用匈牙利算法進行二分圖的完備匹配。算法中需要使用到深度優(yōu)先搜索、交錯路和增廣路的概念。深度優(yōu)先搜索：圖有兩種常用的搜索方式，深度優(yōu)先搜索和廣度優(yōu)先搜索，而匈牙利算法中主要使用的是深度優(yōu)先搜索。深度優(yōu)先搜索圖的主要步驟是：將圖G中某頂點v作為起始頂點，先訪問起始頂點v，按序從v的尚未訪問的鄰接點出發(fā)，對圖G進行深度優(yōu)先搜索，直到圖G中和v有路徑相通的頂點都已被訪問；若圖G中還有尚未訪問過的頂點，則再從一個未被訪問的頂點出發(fā)，重新進行深度優(yōu)先搜索，直到訪問完圖G中所有頂點為止。交錯路：從圖中一個未匹配頂點出發(fā)，依次遍歷未匹配邊、匹配邊、未匹配邊，如此交替下去，這條路徑稱為交錯路。增廣路：從圖中一個未匹配頂點出發(fā)，依次遍歷未匹配邊、匹配邊、未匹配邊，如此交替下去，若路徑的最后一個頂點是未匹配點，則這條路徑稱為增廣路。簡而言之，起點和終點都是未匹配點的交錯路為增廣路。M為圖G的一個匹配，若P是圖G中一條連通兩個未匹配頂點的路徑，并且已匹配和未匹配的邊在路徑P上交替出現(xiàn)，則稱P為相對于M的一條增廣路徑。接著通過增廣路的定義可以推出以下結(jié)論：路徑P邊的數(shù)量必定為奇數(shù)，其第一條邊和最后一條邊都不屬于M；將M和P取反可以得到一個更大的匹配；M為G的最大匹配當且僅當M的增廣路徑不存在。匈牙利算法的核心就是使用深度優(yōu)先搜索的辦法找一條增廣路徑。其算法步驟如下：（１）置M為空；（２）將M和P取反，得到一個更大的匹配M＇；（３）重復（２）直到找不出增廣路徑為止。1.3KM算法KM算法的流程如下：（１）初始化圖中可行頂標的值（設(shè)定lx，ly的初始值）；（２）用匈牙利算法尋找相等子圖的完備匹配；（３）若未找到增廣路徑，則修改可行頂標的值；（４）重復（２）和（３）直到找到相等子圖的完備匹配為止。KM算法的核心在于修改可行頂標的值，使其最終達到一個最優(yōu)完備匹配。KM算法的可行頂標和權(quán)重用于限制子圖中新邊的加入，使新加入的邊總能為子圖添加匹配數(shù)，同時又最大限度地提高權(quán)重和。1.4Gale-Shapley算法Gale-Shapley算法是蓋爾和沙普利在研究大學錄取和穩(wěn)定婚姻匹配問題時提出的，是雙邊匹配理論中常用到的算法。Gale-Shapley算法是一種基于“請求-響應”的循環(huán)算法[[][]張登兵.基于序數(shù)效用的匹配決策問題與Gale-Shapley算法[J].統(tǒng)計與決策,2017(14):90-91.請求者根據(jù)自己的偏好列表發(fā)出匹配請求；響應者根據(jù)自己的優(yōu)先順序選擇接受或者拒絕請求。進入第下一輪，未匹配成功