數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)筆記（01背包問題/圖問題）

01背包問題:在M件物品取出若干件放在空間為W的背包里，每件物品的體積為W1，W2……Wn，與之相對(duì)應(yīng)的價(jià)值為P1,P2……Pn。求如何安排能帶走最多價(jià)值的物品？

動(dòng)態(tài)規(guī)劃解決背包問題：

設(shè)f(i,W)表示，從前i件物品中挑選一些，放進(jìn)一個(gè)空間為W的背包中能獲得的最大總價(jià)值。

那么如果第i件物品也在最優(yōu)解中，那么f(i,W)=f(i-1,W-Wi)+Pi，因?yàn)閺淖顑?yōu)解中吧i去掉，前面選中的物品肯定能使一個(gè)空間為W-Wi的背包價(jià)值最大化，不然它們也不會(huì)出現(xiàn)在最優(yōu)解中。

而如果第i件物品不在最優(yōu)解中，那么f(i,W)=f(i-1,W)，第i件物品沒有占用空間。

通過比較上面兩個(gè)表達(dá)式的大小可以決定第i個(gè)物品是不是在最優(yōu)解中。這就形成了一個(gè)遞歸。

但是如果W<Wi，也就是這個(gè)背包裝不下第i個(gè)物品了，自然只能是f(i,W)=f(i-1,W)。

遞歸的終止條件是i=1.第一件物品如果能裝下，價(jià)值就是Pi,裝不下就是0.

有許多計(jì)算過程重復(fù)，可以把重復(fù)的f(i,w)保存下來降低復(fù)雜度。

圖：

圖可以用鄰接表法表示。每個(gè)點(diǎn)擁有一個(gè)數(shù)組，記錄了和它相鄰的點(diǎn)。

圖也可以用矩陣法表示，橫縱是各個(gè)點(diǎn)，如果這兩個(gè)點(diǎn)是相鄰的則矩陣的值為1，否則0。只需要對(duì)角線的一半，因?yàn)榱硪话胧侵貜?fù)的。橫縱相同的點(diǎn)設(shè)為0.

廣度優(yōu)先搜索BFS：

選取某一點(diǎn)作為源點(diǎn)開始搜索，每一輪將某個(gè)點(diǎn)所有相鄰的點(diǎn)搜索完畢(稱為將此點(diǎn)探索完畢)，然后從剩下未探索完畢點(diǎn)里選取一個(gè)作為下一輪探索的起點(diǎn)(選一個(gè)距離最近的，使用隊(duì)列維護(hù))。

因?yàn)槊總€(gè)點(diǎn)只能被發(fā)現(xiàn)一次，每個(gè)點(diǎn)（除了源）都有確定的父結(jié)點(diǎn)，因此廣度優(yōu)先搜索會(huì)形成一棵樹。（廣度優(yōu)先樹）

具體算法：

每個(gè)點(diǎn)有除了數(shù)據(jù)域，有三個(gè)字段。第一個(gè)是顏色，白色的表示沒被發(fā)現(xiàn)，灰色的表示已經(jīng)被發(fā)現(xiàn)了但是沒有探索完畢(會(huì)出現(xiàn)在待探索隊(duì)列中，或者剛出隊(duì)，是本輪搜索的起點(diǎn)。)，黑色的表示探索完畢(與其相鄰的點(diǎn)全部被發(fā)現(xiàn)了)。第二個(gè)字段表示點(diǎn)的父親(P,C相鄰，探索P周邊的時(shí)候第一次發(fā)現(xiàn)C使得C由白邊灰,則P是C的父親)。第三個(gè)結(jié)點(diǎn)表示深度(和源點(diǎn)的距離，兒子結(jié)點(diǎn)的深度為父親結(jié)點(diǎn)的深度加一)。從源點(diǎn)開始，對(duì)其所有相鄰的點(diǎn)進(jìn)行搜索，每新發(fā)現(xiàn)一個(gè)點(diǎn)就涂成灰色，并且加入待探索隊(duì)列中。如果某點(diǎn)周邊探索完畢，此點(diǎn)就被涂成黑色，然后從隊(duì)列中取出一個(gè)來進(jìn)行下一輪搜索，直到所有結(jié)點(diǎn)變黑，隊(duì)列中也變空，則整個(gè)圖搜索完畢。

深度優(yōu)先搜索：

從源點(diǎn)開始搜索，如果其存在未被發(fā)現(xiàn)(白色)的相鄰點(diǎn)，就涂成灰色，并以那個(gè)點(diǎn)為起點(diǎn)繼續(xù)往深處探索(遞歸)。如果某個(gè)點(diǎn)的所有鄰點(diǎn)都被發(fā)現(xiàn)并且依次遞歸探索過了，那么把此點(diǎn)涂成黑色(形成了一棵樹，此結(jié)點(diǎn)是樹的根節(jié)點(diǎn)。)。如果地圖中還存在白色的點(diǎn)，那么設(shè)為源點(diǎn)開始新一輪搜索（又形成一棵樹）。因此深度優(yōu)先搜索形成一個(gè)森林。

深度優(yōu)先搜索會(huì)維護(hù)一個(gè)全局的時(shí)間戳變量，每次新發(fā)現(xiàn)一個(gè)點(diǎn)并開始一次遞歸搜索的時(shí)候時(shí)間戳自增一次。每個(gè)點(diǎn)會(huì)記錄兩個(gè)時(shí)間戳，一個(gè)是它被發(fā)現(xiàn)的時(shí)刻，一個(gè)是它被探索完畢的時(shí)刻（所有鄰點(diǎn)都變黑）

最小生成樹：能連通所有點(diǎn)，并且使得各邊權(quán)值和最小的樹.

構(gòu)造最小生成樹使用貪心算法（貪心算法：每一步都采取對(duì)當(dāng)前狀況最有利的選擇）。假設(shè)有一個(gè)邊的集合A，是一棵最小生成樹的一個(gè)子集。如果每次都能找到一條邊來加入A(稱為安全邊)，并且保證A依舊是某個(gè)最小生成樹的子集，那么最終就能構(gòu)造出最小生成樹。

尋找安全邊的依據(jù)：A是某最小生成樹的子集，S是圖中的一個(gè)割集且S不妨害A（S沒有割到A的邊），那么S中權(quán)值最小的一條邊可以安全的加入A中而保持A的性質(zhì)。

Kruskal算法:

并查集是一種維護(hù)集合關(guān)系的數(shù)據(jù)結(jié)構(gòu)，能夠快速的判斷一個(gè)元素是否在某個(gè)集合中(或者兩個(gè)元素是否在同一個(gè)集合中)，以及將兩個(gè)集合合并起來。

Kruskal算法首先將每個(gè)點(diǎn)都生成一棵樹(一個(gè)并查集合)，然后按照權(quán)值由小到大遍歷各邊（安全邊）。如果某邊兩點(diǎn)屬于不同的并查集則合并兩個(gè)集合，直到最后形成一棵樹，也就是最小生成樹。

Prim算法:

把一個(gè)點(diǎn)作為樹的跟結(jié)點(diǎn)，從剩下的點(diǎn)里，每次選取一個(gè)離樹最近的點(diǎn)連入樹中，最終形成最小生成樹(最近的意思是說，把這個(gè)點(diǎn)連接到樹上的某個(gè)點(diǎn)，連線的權(quán)值最小。通常使用用斐波那契堆實(shí)現(xiàn)的最小優(yōu)先隊(duì)列來維護(hù)剩余的點(diǎn))

具體算法：每個(gè)點(diǎn)有一個(gè)d字段表示和樹的最小距離，初始時(shí)根結(jié)點(diǎn)的d設(shè)為0，其余結(jié)點(diǎn)的設(shè)為無窮大。每個(gè)結(jié)點(diǎn)還有一個(gè)p字段表示其父。準(zhǔn)備一個(gè)以d為依據(jù)的最小優(yōu)先隊(duì)列將圖中各點(diǎn)放入。

每次從最小優(yōu)先隊(duì)列中取出一個(gè)點(diǎn)S并進(jìn)行如下操作：

1.將S加入樹中(通過其父，隊(duì)列中第一個(gè)取出的是d為0的根節(jié)點(diǎn)，無父)

2.遍歷和S相鄰的結(jié)點(diǎn)，如果某個(gè)鄰結(jié)點(diǎn)C在隊(duì)列中且SC的權(quán)值比C的d字段要小，則將d字段降低為此權(quán)值(自然在隊(duì)列中的順序得到提升)，然后將C的父設(shè)為S。

單源最短路徑:求從某源點(diǎn)出發(fā)，到圖中各點(diǎn)的最短路徑(各邊權(quán)值不同)

最短估計(jì)路徑和松弛:給每個(gè)點(diǎn)一個(gè)屬性d，表示這個(gè)點(diǎn)距離源點(diǎn)的估計(jì)值，使得實(shí)際的最短路徑權(quán)值不會(huì)超過這個(gè)值.

對(duì)點(diǎn)u和v進(jìn)行松弛，是有可能降低v點(diǎn)的路徑估計(jì)值的操作（d值）。如果d(v)>d(u)+uv，那么就將d(v)改為d(u)+uv，且將v的父設(shè)為u。意思是，u對(duì)v說，大哥啊，你原來的路太長(zhǎng)了，改從我這經(jīng)過吧！

對(duì)于從S到某一點(diǎn)v的最短路徑，從s開始一路松弛下去，最終v的d值一定等于最短路徑的權(quán)值。Dijkstra算法依據(jù)此條性質(zhì)求最短路徑。

Dijkstra算法:（要求圖中不存在負(fù)權(quán)邊）

使用一個(gè)以d為依據(jù)的最小優(yōu)先隊(duì)列來維護(hù)未求得最短路徑的各點(diǎn)(初始時(shí)，源點(diǎn)的d值為零,其余點(diǎn)的d值為無窮大)。每次從最小優(yōu)先隊(duì)列取出一點(diǎn)，并對(duì)其相鄰的點(diǎn)依次進(jìn)行松弛操作，以期降低估計(jì)值。這樣下次從隊(duì)列中取出的點(diǎn)就是剩余估計(jì)值最小的那個(gè)點(diǎn)，最小優(yōu)先隊(duì)列可以保證對(duì)于某一條最短路徑而言，各點(diǎn)事依據(jù)估計(jì)值依次松弛下去的，最終估計(jì)值就是最短路徑的權(quán)值，并通過松弛得到的父子關(guān)系確定路徑。本質(zhì)也是一種貪心策略。

最大流解決最大二分匹配問題:

流網(wǎng)絡(luò)：

一個(gè)有向圖，擁有一對(duì)源點(diǎn)s和匯點(diǎn)v,圖中每點(diǎn)都出現(xiàn)在s到v的一條路徑中。對(duì)每一點(diǎn)而言，凈流入為零（類似基爾霍夫電流定律）,每邊有個(gè)容量值(類似于線路的最大電流)，實(shí)際流量（類似于電流）不能超過容量。

殘留網(wǎng)絡(luò)，增廣路徑和最大流的Ford-Fulkerson方法：

一個(gè)流網(wǎng)絡(luò)的殘留網(wǎng)絡(luò)的每邊的權(quán)值等于容量-實(shí)際流量，反應(yīng)了一個(gè)流量網(wǎng)絡(luò)還剩余的運(yùn)載能力。殘留網(wǎng)絡(luò)中如果存在從源點(diǎn)到匯點(diǎn)的路徑，則成為增光路徑。順著此路徑增加沿路的流即可增加整個(gè)網(wǎng)絡(luò)的流。反復(fù)尋找增廣路徑并沿路增加，如果最終找不到增廣路徑了，說明已經(jīng)找到了網(wǎng)絡(luò)的最大流。這個(gè)尋找最大流的方法就是Ford-Fulkerson方法。如果各路徑的容量是有理數(shù)，此方法一定可以找到最大流。如果各路徑是整數(shù)，復(fù)雜度則相對(duì)較低（每次增廣至少增加一個(gè)整數(shù)單位）

Edmonds-Karp算法：

對(duì)Ford-Fulkerson方法的改進(jìn)，每次在殘留網(wǎng)絡(luò)中尋找增廣路徑時(shí)，是尋找一個(gè)源點(diǎn)到匯點(diǎn)的最短路徑。

Floyd-Warshall算法求兩點(diǎn)間最短路徑:

此算法通過動(dòng)態(tài)規(guī)劃的方式，遞歸求得圖中任意兩點(diǎn)間的最短路徑。設(shè)某個(gè)圖中前k個(gè)頂點(diǎn)的集合為Ak，若從i到j有若干這樣的路徑：i到k之間的中間點(diǎn)必須從集合Ak中選取。那么用d(i,j,k)來表示這些路徑中最短的一條。顯然當(dāng)k為圖的頂點(diǎn)樹的時(shí)候，d(i,j,k)就是i和j之間的最短路徑。

對(duì)于d(i,j,k),假如第k個(gè)點(diǎn)不i到j之間的中間點(diǎn)，那么d(i,j,k)=d(i,j,k-1),因?yàn)榈?/span>k個(gè)點(diǎn)不影響路徑；如果第k個(gè)點(diǎn)是i到j的中間點(diǎn)，那么路徑分成兩半，每一半都是對(duì)應(yīng)兩個(gè)端點(diǎn)間的最短路徑，因此d(i,j,k)=d(i,k,k)+d(k,j,k)。因此d(i,k,k)+d(k,j,k)和d(i,j,k-1)誰比較小，決定了第k個(gè)點(diǎn)是否在i到j的最短路徑上，形成遞歸。

遞歸的終止條件是k=0,此時(shí)沒有中間點(diǎn)（空集）,i和j直接相連，d(i,j,0)=W(i,j)，也就是ij線的距離。

另外當(dāng)k為i或j本身時(shí)，k必然不在中間點(diǎn)上，此時(shí)d(i,j,k)=d(i,j,k-1)

最大二分匹配：

二分圖：一個(gè)所有回路長(zhǎng)度均為偶數(shù)的無向圖，這樣的圖能夠?qū)㈨旤c(diǎn)分為兩部分，每部分內(nèi)部各頂點(diǎn)間均不相連。

匹配：一個(gè)匹配是一個(gè)圖的一組邊的集合，圖的每個(gè)頂點(diǎn)之多連接匹配中的一條邊，如果沒有就是這個(gè)點(diǎn)未被匹配到。一個(gè)匹配相當(dāng)于將圖中的若干頂點(diǎn)兩兩一對(duì)相連。

最大二分匹配：假設(shè)一個(gè)二分圖，頂點(diǎn)分為左，右兩側(cè)。每側(cè)頂點(diǎn)內(nèi)部互不相連。左側(cè)每個(gè)頂點(diǎn)表示一個(gè)人，右側(cè)每個(gè)頂點(diǎn)表示一份工作。二分圖中每個(gè)連接人-工作的邊表示這個(gè)人有能力做這項(xiàng)工作。每項(xiàng)工作最多只需要一個(gè)人，每個(gè)人最多只能完成一項(xiàng)工作，如何分配工作(匹配)才能人盡其用呢？這就是一個(gè)求二分圖中最大匹配的問題。

最大流解決最大二分匹配問題：

在左側(cè)頂點(diǎn)的左邊加入源點(diǎn)，右側(cè)頂點(diǎn)的右邊加入?yún)R點(diǎn)，連接源點(diǎn)-左側(cè)各點(diǎn)-右側(cè)各點(diǎn)-匯點(diǎn)的各邊賦予1的容量，于是就構(gòu)造出了一個(gè)流網(wǎng)絡(luò)。由于各邊容量均為1，那么使得此流網(wǎng)絡(luò)形成最大流的方案，也就是原二分圖的最大匹配了。