國家集訓(xùn)隊(duì)集周

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

2、輯上的理性認(rèn)識，稱之為科學(xué)類比 科學(xué)類比！常見的類比模式具體事物類比抽象模型 圖形類比數(shù)式相似算法之間的類比 餐巾問題(餐巾花費(fèi)類比費(fèi)用流)下面的例子差分約束系統(tǒng)(不等式類比約束圖)相似算法之間的類比有些算法是相似的：在算法思想上相似在算法依據(jù)上相似在算法實(shí)現(xiàn)上相似例：最小最大邊問題 (USACO) 有n座城市，p條雙向道路把這些城市連接起來，一對城市之間可能有多條道路連接。FJ要找到k條從城市1到城市n的路徑，不同的路徑不能包含相同的道路。在這一前提條件下，F(xiàn)J希望所有路徑中經(jīng)過的最長的道路最短。 輸入樣例7 9 21 2 22 3 53 7 51 4 14 3 14 5 75 7 11 6

3、 36 7 3有7座城市，9條雙向道路，F(xiàn)J希望找到2條路徑分別給出每條道路連接的城市編號和道路長度1672345332515117輸出樣例5 1672345332551117Max3,3,2,5,5=5初步分析 這是一個關(guān)于流的問題。題目給定n個點(diǎn)和p條容量為1的無向邊，每條邊都擁有一個邊權(quán)，要求找到一個流量至少為k的流，同時(shí)流通過的邊權(quán)最大的邊最小。 似曾相識?最小最大匹配!最小最大匹配這個匹配是在一個帶權(quán)二分圖上進(jìn)行；是一個完備匹配；是滿足上述條件的匹配中最大邊權(quán)最小的匹配。即定義x=max匹配邊的權(quán)，求使x最小的完備匹配。算法1 利用參數(shù)搜索的思想，二分枚舉一個x，再判定這個x是否可以

4、得到。根據(jù)判定的結(jié)果適當(dāng)改變枚舉區(qū)間。設(shè)當(dāng)前區(qū)間為min,max,x=(min+max) div 2若x不行，則區(qū)間調(diào)整為x+1,max若x可行，則區(qū)間調(diào)整為min,x-1算法1（續(xù)）類比使用最大流算法判定能否得到不小于k的流使用匈牙利算法判定能否得到完備匹配算法1效率分析邊數(shù)有p條，對其進(jìn)行二分需要每次判定需要執(zhí)行一次最大流算法O(logp)O(kp)O(kplogp)O(logp)*O(kp)=至多找k次增廣路每次找增廣路復(fù)雜度O(p)小結(jié) 利用簡單類比，我們得到了一個不錯的算法。 這種“二分枚舉法”十分直觀 但是我們的類比停留在形式上！繼續(xù)尋找算法的相似點(diǎn)最短路問題最小生成樹問題最小最大

5、邊問題要求最大邊權(quán)最小 最小費(fèi)用最大流問題要求通過每條邊的邊權(quán)和最小 連續(xù)最短路算法1.初始流分布使每條邊e都為f(e)=0;2.在當(dāng)前的容許流分布下修改各邊(i,j)的費(fèi)用aij aij=wij 0=fij03.以aij為邊長，找一條s到t的最短增廣路連續(xù)最短路算法（續(xù)）4.若能找到增廣路就轉(zhuǎn)2，否則轉(zhuǎn)55.輸出結(jié)果如果利用普里姆算法的思想尋找增廣路會怎么樣？算法21.初始流分布使每條邊都為f(e)=0；2.設(shè)立臨時(shí)距離標(biāo)號di，表示當(dāng)前能擴(kuò)展到i的增廣軌中最長邊長度的最小值。初始時(shí)除源點(diǎn)以外的臨時(shí)距離標(biāo)號都為正無窮大。3.在計(jì)算距離標(biāo)號時(shí)，假設(shè)du已經(jīng)被擴(kuò)展，正在考察邊(u,v)：算法2（續(xù)）假設(shè)正在考察邊(u,v)：(I).若u到v的流量為0且v到u的流量為0，那么 dvmindv,maxdu,w(u,v)；(II).若v到u的流量為1，那么 dvmindu,dv；4.在求得所有的dv同時(shí)記錄路徑5.當(dāng)擴(kuò)展次數(shù)超過t時(shí)結(jié)束，否則轉(zhuǎn)2引理1的證明引理1：在算法依次找到的每條增廣路中，n的距離標(biāo)號是單調(diào)不減的。