算法合集之淺談類比思想第1頁，共36頁，2023年，2月20日，星期六內(nèi)容摘要信息學(xué)是一門變幻莫測的藝術(shù)。它包含著海量的知識點。我們不能奢求掌握所有的知識；只能在已有知識的基礎(chǔ)上，盡可能的把不熟悉的問題轉(zhuǎn)化為熟悉的問題。類比思想，就是一種非常優(yōu)秀的轉(zhuǎn)化方法。第2頁，共36頁，2023年，2月20日，星期六什么是類比呢？類比是最有創(chuàng)造力的一種思維方法。它關(guān)注兩個對象在某些方面的相同或相似之處，從而推測它們在其它方面也可能存在相同或相似之處。這就為我們解決復(fù)雜問題創(chuàng)造了條件。第3頁，共36頁，2023年，2月20日，星期六什么是類比呢？（續(xù)）第4頁，共36頁，2023年，2月20日，星期六鉛筆與鋼筆第5頁，共36頁，2023年，2月20日，星期六鉛筆與毛筆第6頁，共36頁，2023年，2月20日，星期六簡單類比與科學(xué)類比鉛筆和鋼筆恰好都是硬筆，類比成功具有偶然性，它是基于直觀上的感性認識，稱之為簡單類比

注意到鉛筆與毛筆的不同點，類比成功帶有某種必然性，它是基于邏輯上的理性認識，稱之為科學(xué)類比

科學(xué)類比！第7頁，共36頁，2023年，2月20日，星期六常見的類比模式具體事物類比抽象模型

圖形類比數(shù)式相似算法之間的類比

餐巾問題(餐巾花費類比費用流)下面的例子差分約束系統(tǒng)(不等式類比約束圖)第8頁，共36頁，2023年，2月20日，星期六相似算法之間的類比有些算法是相似的：在算法思想上相似在算法依據(jù)上相似在算法實現(xiàn)上相似第9頁，共36頁，2023年，2月20日，星期六例：最小最大邊問題(USACO)

有n座城市，p條雙向道路把這些城市連接起來，一對城市之間可能有多條道路連接。FJ要找到k條從城市1到城市n的路徑，不同的路徑不能包含相同的道路。在這一前提條件下，F(xiàn)J希望所有路徑中經(jīng)過的最長的道路最短。

第10頁，共36頁，2023年，2月20日，星期六輸入樣例792122235375141431457571163673有7座城市，9條雙向道路，F(xiàn)J希望找到2條路徑分別給出每條道路連接的城市編號和道路長度1672345332515117第11頁，共36頁，2023年，2月20日，星期六輸出樣例5

1672345332551117Max{3,3,2,5,5}=5第12頁，共36頁，2023年，2月20日，星期六初步分析這是一個關(guān)于流的問題。題目給定n個點和p條容量為1的無向邊，每條邊都擁有一個邊權(quán)，要求找到一個流量至少為k的流，同時流通過的邊權(quán)最大的邊最小。

似曾相識?最小最大匹配!第13頁，共36頁，2023年，2月20日，星期六最小最大匹配這個匹配是在一個帶權(quán)二分圖上進行；是一個完備匹配；是滿足上述條件的匹配中最大邊權(quán)最小的匹配。即定義x=max{匹配邊的權(quán)}，求使x最小的完備匹配。第14頁，共36頁，2023年，2月20日，星期六算法1利用參數(shù)搜索的思想，二分枚舉一個x，再判定這個x是否可以得到。根據(jù)判定的結(jié)果適當改變枚舉區(qū)間。設(shè)當前區(qū)間為[min,max],x=(min+max)div2若x不行，則區(qū)間調(diào)整為[x+1,max]若x可行，則區(qū)間調(diào)整為[min,x-1]第15頁，共36頁，2023年，2月20日，星期六算法1（續(xù)）類比使用最大流算法判定能否得到不小于k的流使用匈牙利算法判定能否得到完備匹配第16頁，共36頁，2023年，2月20日，星期六算法1效率分析邊數(shù)有p條，對其進行二分需要每次判定需要執(zhí)行一次最大流算法O(logp)O(kp)O(kplogp)O(logp)*O(kp)=至多找k次增廣路每次找增廣路復(fù)雜度O(p)第17頁，共36頁，2023年，2月20日，星期六小結(jié)利用簡單類比，我們得到了一個不錯的算法。這種“二分枚舉法”十分直觀但是我們的類比停留在形式上！第18頁，共36頁，2023年，2月20日，星期六繼續(xù)尋找算法的相似點最短路問題最小生成樹問題最小最大邊問題要求最大邊權(quán)最小最小費用最大流問題要求通過每條邊的邊權(quán)和最小

第19頁，共36頁，2023年，2月20日，星期六連續(xù)最短路算法1.初始流分布使每條邊e都為f(e)=0;2.在當前的容許流分布下修改各邊(i,j)的費用aijaij=wij0<=fij<cijaij=maxlongintfij=cijaij=-wjifji>03.以aij為邊長，找一條s到t的最短增廣路第20頁，共36頁，2023年，2月20日，星期六連續(xù)最短路算法（續(xù)）4.若能找到增廣路就轉(zhuǎn)2，否則轉(zhuǎn)55.輸出結(jié)果如果利用普里姆算法的思想尋找增廣路會怎么樣？第21頁，共36頁，2023年，2月20日，星期六算法21.初始流分布使每條邊都為f(e)=0；2.設(shè)立臨時距離標號d[i]，表示當前能擴展到i的增廣軌中最長邊長度的最小值。初始時除源點以外的臨時距離標號都為正無窮大。3.在計算距離標號時，假設(shè)d[u]已經(jīng)被擴展，正在考察邊(u,v)：……第22頁，共36頁，2023年，2月20日，星期六算法2（續(xù)）假設(shè)正在考察邊(u,v)：(I).若u到v的流量為0且v到u的流量為0，那么d[v]←min{d[v],max{d[u],w(u,v)}}；(II).若v到u的流量為1，那么d[v]←min{d[u],d[v]}；4.在求得所有的d[v]同時記錄路徑5.當擴展次數(shù)超過t時結(jié)束，否則轉(zhuǎn)2第23頁，共36頁，2023年，2月20日，星期六引理1的證明引理1：在算法依次找到的每條增廣路中，n的距離標號是單調(diào)不減的。證明：算法優(yōu)先擴展最短的增廣路。若存在增廣路Path與Path’滿足d[n]<d[n]’，則Path必在Path’前被擴展。因此n的距離標號單調(diào)不減。第24頁，共36頁，2023年，2月20日，星期六引理1的證明（續(xù)）1124536713534363第25頁，共36頁，2023年，2月20日，星期六引理2的證明引理2：擴展方式2不會使當前流經(jīng)過的最長邊變短。證明：我們使用反證法來證明結(jié)論。假設(shè)某次擴展使得最長邊變短，則必然出現(xiàn)了如下情況：svtu第26頁，共36頁，2023年，2月20日，星期六引理2的證明（續(xù)）也就是原來存在一條流的路徑s→u→v→t，方式2將其擴展成路徑s→v→t和1→u→t。svtu(u,v)不會是最長邊若(s,u)、(s,v)、(u,t)、(v,t)四者中存在長度不小于w(u,v)的邊，那么最長邊邊權(quán)不會減少；但如果所有邊權(quán)都小于w(u,v)，那么根據(jù)引理1，算法會優(yōu)先選擇s→u→t和s→v→t兩條路徑，不會從(u,v)經(jīng)過，這與假設(shè)矛盾。第27頁，共36頁，2023年，2月20日，星期六正確性的證明（續(xù)）定理：算法2是正確的。證明：根據(jù)引理1我們知道算法在貪心式地尋找增廣路，而根據(jù)引理2我們知道算法得到的永遠是當前流量下的最優(yōu)解。因此算法是正確的。第28頁，共36頁，2023年，2月20日，星期六算法2效率分析流量每次增加1，因此要增廣t次每次增廣需要執(zhí)行一次普里姆算法O(k)O(n^2+p)O(k(n^2+p))O(k)*O(n^2+p)=第29頁，共36頁，2023年，2月20日，星期六算法1和算法2的比較算法1算法2時間復(fù)雜度O(kplogp)O(k(n^2+p))空間復(fù)雜度O(p)O(p)編程難度低更低類比種類簡單類比科學(xué)類比第30頁，共36頁，2023年，2月20日，星期六小結(jié)最小最大邊問題形式上簡單類比最小最大匹配問題本質(zhì)上科學(xué)類比最小費用流問題第31頁，共36頁，2023年，2月20日，星期六可以用類比思想解決的問題特性1.可類比性3.可移植性2.可簡化性新問題與原問題相似新問題比原問題簡單算法要與類比對象密切相關(guān)

第32頁，共36頁，2023年，2月20日，星期六感謝謝謝大家第33頁，共36頁，2023年，2月20日，星期六簡單類比對象A具有性質(zhì)P、Q；對象A’具有性質(zhì)P’(P與P’類似)；對象A’可能具有性質(zhì)Q’(Q與Q’類似)第34頁，共36頁，2023年，2月20日，星期六科學(xué)類比對象A具有性質(zhì)P、Q和關(guān)系R；對象A’具有性質(zhì)P’；對象A’具有性質(zhì)Q’和關(guān)系R’