算法合集之淺析二分圖匹配在信息學(xué)競(jìng)賽中的應(yīng)用-資料下載頁(yè)
2024-10-16 20:32本頁(yè)面
【正文】 下面給出算法的流程： 將 Y39。結(jié)點(diǎn)非降序排列 初始化 M39。， P和 Path j ← 1 q ← Y39。的第 j個(gè)結(jié)點(diǎn) 存在 q的某個(gè)鄰結(jié)點(diǎn) p為可匹配點(diǎn) 更新 M39。， R和 Path jm j ← j + 1 結(jié)束 N N Y Y 復(fù)雜度分析 下面來(lái)分析一下該算法的時(shí)間復(fù)雜度。 算法中執(zhí)行了如下操作： 3 更新 M39。； O(n) 2 詢問(wèn)是否存在 q的某個(gè)鄰結(jié)點(diǎn) p為可匹配點(diǎn)； O(mn)=O(n3) 1 將所有 Y39。結(jié)點(diǎn)按權(quán)值大小非降序排列； O(mlog2m)=O(n2log2n) 4 更新 R以及 Path。 O(n3) 復(fù)雜度分析 前三個(gè)操作復(fù)雜度都顯而易見(jiàn)，下面討論操作 4的時(shí)間復(fù)雜度。 如果某個(gè)點(diǎn)為可匹配點(diǎn)，則它的路徑必然為 i0→ j1→ i1→ j2→ i2 →… → jk → ik (k≥0),其中 i0為未匹配點(diǎn)而且(jt, it)(t ∈ [1,k]) 為匹配邊。 i0 j1 i1 j2 i2 jk ik 復(fù)雜度分析 也就是說(shuō)我們?cè)诟?R和 Path時(shí)只需要處理X39。結(jié)點(diǎn)和已匹配的 Y39。結(jié)點(diǎn)以及它們之間的邊構(gòu)成的子二分圖。 顯然任意時(shí)刻圖 G39。的匹配邊數(shù)都不超過(guò) n1，所以該子圖的點(diǎn)數(shù)為 O(n)，邊數(shù)為 O(n2)。所以該操作執(zhí)行一次的復(fù)雜度即為 O(n2)，最多執(zhí)行 n次，所以其復(fù)雜度為 O(n3)。 所以 Y39。結(jié)點(diǎn)中的未匹配點(diǎn)是不可能出現(xiàn)在某個(gè) X39。結(jié)點(diǎn) i的 Pathi中的。 復(fù)雜度分析 那么算法總的時(shí)間復(fù)雜度為： O(n2log2n) +O(n3)+ O(n)+ O(n3)= O(n3) 因?yàn)?O(m)=O(n2)，所以該算法相對(duì)于算法一 O(m3)=O(n6)的復(fù)雜度，在效率上有了巨大的飛躍。 回顧 ?通過(guò)對(duì)最小生成樹(shù)性質(zhì)的 分析 得到一組不等式 Dv≤Du。 ?將不等式變形后，通過(guò)對(duì)其 觀察 ，聯(lián)想到了解決二分圖最佳匹配經(jīng)典的 KM算法，即得到了算法一。 ?正是通過(guò) 猜想 將權(quán)值由圖中的邊轉(zhuǎn)移到頂點(diǎn)上，重新構(gòu)造二分圖，才得到了更為優(yōu)秀的算法二！ 總結(jié) 信息學(xué)競(jìng)賽中的各種題目，往往都需要通過(guò)對(duì)題目的仔細(xì) 觀察 ，構(gòu)造出合適的數(shù)學(xué)模型，然后通過(guò)對(duì)題目以及模型的進(jìn)一步 分析 ， 挖掘出問(wèn)題的本質(zhì)，進(jìn)行大膽的 猜想 ，轉(zhuǎn)化模型， 設(shè)計(jì)優(yōu)秀的算法解決問(wèn)題。 結(jié)語(yǔ) 仔細(xì)觀察 大膽猜想 認(rèn)真分析
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1