oi提高2012常州夏令營day

1、搜索以及優(yōu)化常用搜索方式DFSBFSDFS-ID (比BFS多產(chǎn)生1/(k-1)倍節(jié)點(diǎn).但節(jié)省內(nèi)存)A*IDA*常用搜索方式DFS常用搜索方式DFS-ID常用搜索方式void dfs(int x, int d)if (d maxdep) return;if (x = target)blablabla.for (int i=1; i=n; i+)if (fxi & !usedi)usedi = true;sd = i;dfs(i, d + 1);usedi = false;組合雙向BFS反向BFS，正向DFS-ID (利用哈希)等等剪枝首先需要：正確性,高效性常用剪枝：1.可行性剪枝2.最優(yōu)性剪

2、枝（上下界）例題1 給出一個n*m的方格(n,m=8)，并給出三個特殊格子表示這三個格子必須在特定的三步到達(dá)(順序一定).要求從左下角走到左下第二個格子的方案數(shù).(可行性剪枝)例題1 直接搜索會超時，考慮一個出現(xiàn)頻率非常高的廢狀態(tài)：在走完某一步之后將為走完的格子分成兩個塊不連通，那么這就已經(jīng)完了。哪些情況？1 撞墻2 撞自己如何判斷？ 撞了之后是否左右還有格子。例題2構(gòu)造數(shù)列ai滿足1. a1 = 12. ai = ak + aj (j, k I)使得at = n,且t最小.(最優(yōu)化剪枝) 例題2 1. 將n分解質(zhì)因數(shù)。將較大的質(zhì)因數(shù)-1后繼續(xù)分解?？捎纱素澬牡靡粋€較優(yōu)解。 2.當(dāng)數(shù)列中最大數(shù)

3、ai超過n/2時，此時最有解相當(dāng)于從a1.ai中選擇一些數(shù)字使得和等于n。那么最優(yōu)的方案可通過動態(tài)規(guī)劃求出。例題3 在n*n(n=3)的格子中每個格子有一個數(shù)字(09)，現(xiàn)在告訴你每個格子與其相鄰的四個格子中比他大的有多少個(04)，要求出原來的數(shù)字。多解輸出任意一個。sgu125例題3直接搜索會超時，改變搜索順序即可。 617 254 839按照這個順序搜索。A* 啟發(fā)函數(shù)f(n)=g(n) + h(n)表示估計(jì)的該結(jié)點(diǎn)的好壞。一般越小代表這個點(diǎn)越優(yōu)。 其中g(shù)(n)表示從初始結(jié)點(diǎn)到n的路徑長度,h(n)表示從n到目標(biāo)結(jié)點(diǎn)的距離的估計(jì)。 A*算法每次選擇f(n)最小的點(diǎn)進(jìn)行拓展(類似dijks

4、tra)A*當(dāng)h(n)=h(n)時，A*算法變成了貪心算法當(dāng)h(n)=0時，A*算法成了dijkstra算法若搜索圖中邊權(quán)非負(fù)，且滿足h(n)h(n),則搜索數(shù)量會減少，但不一定能找到最優(yōu)解。所以，在保證h(n)x為待查的狀態(tài)。(3).對所有處在待查狀態(tài)的節(jié)點(diǎn)pj遞歸調(diào)用過程Euler（pj）將Euler（pj）找到的環(huán)q1q2qx插入到環(huán)p1p2px中，得到回路p1p2pjq1qypj+1px。歐拉路代碼:void Euler(int x)for (x的出邊e)if (!usede)usede = true;Euler(e.x);s+ans = e;sgu101漢密爾頓路若無特殊條件：搜索.

5、狀壓.存在漢密爾頓回路的充分條件： 對任意u,v有degu+degv = n(Ore條件) 漢密爾頓路在知道滿足Ore條件的情況下構(gòu)造一個解：1 . extend操作：將一條路徑兩端延伸至最長2. inverse操作：在路徑s.k,k+1.t上，找到k使得s到k+1有邊，k到t有邊，斷開k到k+1連接s，k+1和k，t構(gòu)成一個環(huán)3. add操作：在環(huán)外找一個點(diǎn)z，使得環(huán)上有點(diǎn)k與z有邊，斷開環(huán)連接z和k得到更長的鏈漢密爾頓路隨意找一條路徑，然后循環(huán)做這三步操作直至所有點(diǎn)加入環(huán)。在滿足Ore條件時，以上三步操作在未將n個點(diǎn)全部加入時總是可以反復(fù)進(jìn)行。以下證明： add ：由于Ore條件，圖總是連

6、通的(反證法) 所以總是可以進(jìn)行 inverse： 由于先做了extend操作，所以s和t只能和鏈上的點(diǎn)有邊，又因?yàn)閐egs + degt = n所以而k的選擇只有至多n-1個，所以根據(jù)抽屜原理總有k存在使得s與k+1有邊，k與t有邊。所以inverse也總是可以進(jìn)行的。漢密爾頓路sgu122無向圖連通性連通圖：圖中任意兩點(diǎn)間存在一條通路連通分量(塊)： 圖的一個連通的子圖求無向圖的連通分量： bfs或dfsu,v之間距離d(u, v)為從u到v的長度最短的通路。 當(dāng)u和v不連通時規(guī)定d為無限大。圖的直徑D為任意兩點(diǎn)間距離最大值無向圖的割點(diǎn)和橋 若圖G=存在點(diǎn)v使得刪除點(diǎn)v后圖G的連通塊增加則

7、v稱為割點(diǎn) 若存在點(diǎn)e使得刪除e后圖G的連通塊增加則e稱為割邊或橋無向圖割點(diǎn)和橋圖中3號點(diǎn)就是一個割點(diǎn)，e7就是一條割邊無向圖的割點(diǎn)和橋 如何求？ O(n3)的挨個檢查 有沒有更快的辦法？無向圖的割點(diǎn)和橋 根據(jù)割點(diǎn)的定義可以發(fā)現(xiàn),原圖必然分成了兩個部分，且這兩個部分靠著割點(diǎn)相連。也就是說在使用dfs遍歷這個圖的過程中，想要從第一部分進(jìn)入第二部分一定需要經(jīng)過這個割點(diǎn)，且訪問完所有第二部分的點(diǎn)之后才回到第一部分 如何利用這一點(diǎn)？無向圖的割點(diǎn)和橋 在dfs過程中，每一個點(diǎn)都會有一個被訪問到的次序。 考慮在第二部分的點(diǎn)，他們的訪問序號一定大于割 點(diǎn)的訪問序號(假設(shè)從第一部分開始訪問)。 根據(jù)這一點(diǎn)設(shè)計(jì)

8、算法無向圖的割點(diǎn)和橋 但是，一個點(diǎn)的訪問序號不等于他最早可以被訪問到時的次序。比如在這里,從1開始訪問的話順序可以是1,2,3也可以是1,3,2。所以第二部分的訪問一定在訪問了割點(diǎn)以后意味著第二部分的點(diǎn)最早能被訪問到的時間依然大于割點(diǎn)被訪問到的時間。無向圖的割點(diǎn)和橋 最早訪問時間： 所有直接相連的點(diǎn)中dfs序最小的再+1 定義下序點(diǎn)： 在dfs樹中該點(diǎn)的子節(jié)點(diǎn) 則顯然割點(diǎn)=某個下序點(diǎn)的最早訪問時間大于自己的dfs序的點(diǎn)。無向圖的割點(diǎn)和橋 實(shí)現(xiàn)：dfs過程中，記錄下每個點(diǎn)的到達(dá)時間n1，所有直接相連的點(diǎn)的到達(dá)時間的最小值n2。訪問完一個點(diǎn)后比較這個點(diǎn)的n1和其所有下序點(diǎn)的n2。 若n14-3-2

9、-5，那么2的dfs序是4,大于了5的距離3。然而采用在一遍dfs中同時記錄的方式不會出現(xiàn)問題。無向圖的割點(diǎn)和橋 求割邊的方法非常類似：若存在邊A-B，且A的n1值小于B的n1值(A比B先被訪問到) 且B的n2值大于等于A的n1值(B的最早訪問時間也在訪問過A之后) 那么這條邊就是割邊(橋)有向圖連通性可達(dá)：若存在一條u到v的通路則稱u可達(dá)v。并規(guī)定任意一點(diǎn)可達(dá)自身強(qiáng)連通：圖中任意兩點(diǎn)都是可達(dá)的單向連通：圖中任意兩點(diǎn)間至少一個點(diǎn)可達(dá)另一個點(diǎn)(弱)連通：忽略邊的方向后圖連通有向圖連通性1是強(qiáng)連通的,2是單向連通的,3是弱連通的有向圖強(qiáng)連通的定理若有向圖是強(qiáng)連通的，當(dāng)且僅當(dāng)至少存在一條環(huán)經(jīng)過了圖中

10、所有點(diǎn)。充分性 ：顯然必要性 ：將點(diǎn)順序排好 v1,v2,.vn,則由強(qiáng)連通可得v1可達(dá)v2,v2可達(dá)v3.vn可達(dá)v1.構(gòu)成一個環(huán)且經(jīng)過所有點(diǎn)至少一次有向圖強(qiáng)連通分量有向圖的強(qiáng)連通分量為其一個子圖，且它是強(qiáng)連通的。有向圖強(qiáng)連通分量那么如何找到強(qiáng)連通分量。有很多算法Kosaraju， Tarjan， Gabow算法等等.這里講一下tarjan算法tarjan算法 顯然，在對一張無向圖做dfs的時候若發(fā)現(xiàn)某個節(jié)點(diǎn)的子孫節(jié)點(diǎn)可以到達(dá)自己，那么以該點(diǎn)為根的子樹中仍在堆棧中的點(diǎn)構(gòu)成一個強(qiáng)連通分量. 整個tarjan算法圍繞該思路展開tarjan算法 算法寫出來非常類似求割點(diǎn)的程序。 在dfs中每個點(diǎn)維

11、護(hù)兩個信息，dfs序n1，以及可達(dá)的點(diǎn)中dfs序最小的(這里不算自己到自己這一點(diǎn))點(diǎn)n2，n2的值的更新有兩種可能。一開始n2=n1。在枚舉下一個訪問點(diǎn)的時候，假設(shè)下一個直接相連的點(diǎn)為x。若x已經(jīng)訪問過，則用x的n1更新,若沒有訪問過，則dfs(x)，之后拿x的n2更新。若 某個點(diǎn)的子節(jié)點(diǎn)都訪問完之后發(fā)現(xiàn)該點(diǎn)n1=n2，則以該點(diǎn)為根的子樹中仍在堆棧中的點(diǎn)構(gòu)成一個強(qiáng)連通分量。tarjan算法void dfs(int x)stack+top = x;usedx = true;dfnx = lowx = +cnt; /dfn 和 low 分別表示n1 和 n2for (int i=1; i=n; i+)if (gxi)if (!usedi)dfs(i);lowx = min(lowx, lowi);elselowx = min(lowx, dfni); / 根據(jù)low的定義,用lowi來更新也是可以的.if (lowx = dfnx)