上傳人：卓***

認(rèn)證信息

認(rèn)證類型：個(gè)人認(rèn)證

認(rèn)證主體：卓**（實(shí)名認(rèn)證）

IP屬地：廣東

IP屬地：廣東 上傳時(shí)間：2023-04-23 格式：PPT 頁(yè)數(shù)：36 大?。?.13MB 積分：15 舉報(bào) 版權(quán)申訴

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

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

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

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

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

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

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

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

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

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

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