《第13課 數(shù)據(jù)有關(guān)聯(lián)》參考課件8

數(shù)據(jù)有關(guān)聯(lián)浙教版四上目錄CONTENTS01KM算法的數(shù)據(jù)關(guān)聯(lián)02數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)03匈牙利算法的數(shù)據(jù)關(guān)聯(lián)概念04作業(yè)布置05總結(jié)回顧匈牙利算法的數(shù)據(jù)關(guān)聯(lián)概念01

匈牙利算法（HungarianAlgorithm），也稱為Kuhn-Munkres算法，是一種解決指派問題（Assignmentproblem）的優(yōu)化算法。指派問題是在給定的任務(wù)和資源之間建立最佳的一對一分配關(guān)系的問題。具體來說，匈牙利算法解決的是一個二維的代價矩陣，其中每個元素表示將一個任務(wù)分配給一個資源的成本或代價。算法的目標(biāo)是找到一種分配方式，使得總成本最小。匈牙利算法的基本思想是通過不斷尋找增廣路徑來找到最佳的分配方式。1代價矩陣德每一行減去改行的最小值。2代價矩陣德每一列減去該列的最小值。3用盡量少的線覆蓋矩陣中所有的0，判斷線的數(shù)量是否小于n（矩陣行數(shù)列數(shù)）4線的數(shù)量小于n，則需要繼續(xù)減，未被線覆蓋的行或者列繼續(xù)減掉未被覆蓋的最小值，被線覆蓋一次的不參與減，被線覆蓋兩次的反而要加這個最小值。5重復(fù)上面步驟4，直到找到線的個數(shù)等于n，則得到最終的匹配方案。匈牙利算法步驟：最后需要劃4條線才能覆蓋住矩陣中所有的0元素，迭代終止，根據(jù)矩陣中0元素的位置很容易得到最終的匹配關(guān)系：目標(biāo)1→目標(biāo)D，目標(biāo)2→目標(biāo)B，目標(biāo)3→目標(biāo)A，目標(biāo)4→目標(biāo)C。這個匹配滿足構(gòu)成的二分圖上的匹配邊總權(quán)重最小，即總的匹配距離最小，代價最低。若目標(biāo)和下一幀目標(biāo)個數(shù)不一致，則需要補0進行匈牙利算法。假設(shè)不用匈牙利算法進行匹配，而是按照順序進行局部最小值匹配。顯然不是最優(yōu)匹配。KM算法的數(shù)據(jù)關(guān)聯(lián)02現(xiàn)在常說的以及文獻中常提到的匈牙利算法和Kuhn-Munkres算法指的是同一個東西，求解的都是有權(quán)二分圖最小權(quán)匹配問題；JamesMunkres引入了“標(biāo)星0（starredzeros）”和“標(biāo)撇0（primedzeros）”的概念以改進匈牙利算法原始流程中的劃線法，在算法執(zhí)行過程中會選擇性地對代價矩陣中產(chǎn)生的0元素標(biāo)記星號（*）或標(biāo)記撇號（’）來輔助搜索增廣路，標(biāo)星0表示增廣路中的匹配邊，標(biāo)撇0表示增廣路中的未匹配邊?？梢哉fKM算法是對匈牙利算法進行了改進和推廣。后來習(xí)慣將Munkres提出的方法稱為Kuhn–Munkres算法、KM算法或Munkres分配算法。有一種觀點認(rèn)為匈牙利算法是不帶權(quán)重的，只用于在圖中尋找最大匹配。而KM算法是用于帶權(quán)重的匹配，求解過程中包含匈牙利算法。若是此觀點，則上述目標(biāo)跟蹤匹配例子其實應(yīng)該叫KM算法，因為距離度量就是權(quán)重。01而另外一種觀點則是匈牙利算法（HungarianAlgorithm），也稱為Kuhn-Munkres算法，是同一種算法的不同叫法。02數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)03數(shù)據(jù)關(guān)聯(lián)網(wǎng)絡(luò)數(shù)據(jù)關(guān)聯(lián)神經(jīng)網(wǎng)絡(luò)（DataAssociationNeuralNetwork）是一種利用神經(jīng)網(wǎng)絡(luò)進行數(shù)據(jù)關(guān)聯(lián)的方法。在目標(biāo)跟蹤、目標(biāo)識別和多目標(biāo)追蹤等任務(wù)中，數(shù)據(jù)關(guān)聯(lián)是指將觀測到的目標(biāo)與已知的目標(biāo)進行關(guān)聯(lián)，以確定它們之間的對應(yīng)關(guān)系。

傳統(tǒng)的數(shù)據(jù)關(guān)聯(lián)方法通常依賴于啟發(fā)式規(guī)則、距離度量或最大后驗概率等方法。而數(shù)據(jù)關(guān)聯(lián)神經(jīng)網(wǎng)絡(luò)通過學(xué)習(xí)數(shù)據(jù)之間的關(guān)聯(lián)模式，從數(shù)據(jù)中自動學(xué)習(xí)和推斷目標(biāo)之間的關(guān)聯(lián)關(guān)系?？偨Y(jié)回