算法設(shè)計與 第五章1圖的搜索算法

1、第五章 圖的搜索算法 5 51 1 圖搜索概述圖搜索概述 5.1.15.1.1 圖及其術(shù)語圖及其術(shù)語 5.1.25.1.2 圖搜索及其術(shù)語圖搜索及其術(shù)語5 52 2 廣度優(yōu)先搜索廣度優(yōu)先搜索 5.2.15.2.1 算法算法框架框架 5.2.25.2.2 廣度優(yōu)先搜索廣度優(yōu)先搜索的的應(yīng)用應(yīng)用5.3 5.3 深度優(yōu)先搜索深度優(yōu)先搜索 圖是一種限止最少的數(shù)據(jù)結(jié)構(gòu)，因此更接近現(xiàn)實，實際圖是一種限止最少的數(shù)據(jù)結(jié)構(gòu)，因此更接近現(xiàn)實，實際問題中很多數(shù)據(jù)關(guān)系都可以抽象成圖，相關(guān)問題則可利用圖問題中很多數(shù)據(jù)關(guān)系都可以抽象成圖，相關(guān)問題則可利用圖的基本算法進行求解，很早就有專門研究圖的是一門數(shù)學(xué)學(xué)的基本算法進行求

2、解，很早就有專門研究圖的是一門數(shù)學(xué)學(xué)科科“圖論圖論”；其中的計算問題包括；其中的計算問題包括圖的搜索、路徑問題、連圖的搜索、路徑問題、連通性問題、可平面性檢驗、著色問題、網(wǎng)絡(luò)優(yōu)化通性問題、可平面性檢驗、著色問題、網(wǎng)絡(luò)優(yōu)化等。圖論中等。圖論中的著名算法有：求最小生成樹的的著名算法有：求最小生成樹的Kruskal算法、求最短路徑算法、求最短路徑的的Dijkstra算法和算法和Floyd算法、求二部圖最大匹配（指派問算法、求二部圖最大匹配（指派問題）的匈牙利算法、求一般圖最大匹配的題）的匈牙利算法、求一般圖最大匹配的Edmonds“花花”算法、算法、求網(wǎng)絡(luò)最大流和最小割求網(wǎng)絡(luò)最大流和最小割的算法等。

3、其中的一些算法在數(shù)據(jù)結(jié)的算法等。其中的一些算法在數(shù)據(jù)結(jié)構(gòu)課程中已經(jīng)學(xué)習過了。構(gòu)課程中已經(jīng)學(xué)習過了。 1顯式圖與隱式圖顯式圖與隱式圖 在路徑問題、連通性問題、可平面性檢驗、著色在路徑問題、連通性問題、可平面性檢驗、著色問題和網(wǎng)絡(luò)優(yōu)化等問題中，圖的結(jié)構(gòu)是顯式給出的，問題和網(wǎng)絡(luò)優(yōu)化等問題中，圖的結(jié)構(gòu)是顯式給出的，包括圖中的頂點、邊及權(quán)重，這類圖我們稱為包括圖中的頂點、邊及權(quán)重，這類圖我們稱為顯式圖顯式圖，也就是一般意義上的圖。也就是一般意義上的圖。 隱式圖隱式圖是由問題的初始結(jié)點，為了求解或求證是由問題的初始結(jié)點，為了求解或求證問題，根據(jù)題目的規(guī)則（一般是由題目的意思隱含問題，根據(jù)題目的規(guī)則（一般是

4、由題目的意思隱含給出的），也就是生成子結(jié)點的約束條件，逐步擴給出的），也就是生成子結(jié)點的約束條件，逐步擴展結(jié)點，直到得到目標結(jié)點為止的一個展結(jié)點，直到得到目標結(jié)點為止的一個隱式的圖隱式的圖。 5 51 11 1 圖及其術(shù)語圖及其術(shù)語2.2.顯式圖的常用術(shù)語顯式圖的常用術(shù)語 如圖如圖5-1所示的所示的 ， ， 均為顯式圖均為顯式圖 (Graph)。圖。圖中的這些點中的這些點(v1,v2,vn)(v1,v2,vn)被稱為被稱為頂點頂點 (vertex)或結(jié)點或結(jié)點，連，連接頂點的曲線或直線稱為接頂點的曲線或直線稱為邊邊 (edge)。 通常將這種由若干個頂點以及連接某些頂點的邊所組通常將這種由若干

5、個頂點以及連接某些頂點的邊所組成的圖形稱為圖，頂點通常被稱作是圖中的數(shù)據(jù)元素成的圖形稱為圖，頂點通常被稱作是圖中的數(shù)據(jù)元素 .v1v2v3v4v1v3v2v4v1v2v3v4v5圖圖 5-1 v1v3v2v434296圖圖 5-2 帶權(quán)圖帶權(quán)圖：j即圖即圖5 -2給圖給圖 5-1中各圖的邊上附加一個代表性數(shù)據(jù)中各圖的邊上附加一個代表性數(shù)據(jù) (比比如表示長度、流量或其他如表示長度、流量或其他 )，則稱其為帶權(quán)圖，則稱其為帶權(quán)圖 。環(huán)環(huán) (cycle)：圖：圖5-1中中 圖中的圖中的 v 1點本身也有邊相連，這種邊稱點本身也有邊相連，這種邊稱為環(huán)。為環(huán)。 有限圖有限圖：頂點與邊數(shù)均為有限的圖，如圖

6、：頂點與邊數(shù)均為有限的圖，如圖 5-1中的三個圖均屬于中的三個圖均屬于有限圖。有限圖。 簡單圖簡單圖：沒有環(huán)且每兩個頂點間最多只有一條邊相連的圖，如圖：沒有環(huán)且每兩個頂點間最多只有一條邊相連的圖，如圖 5-1中的中的 圖。圖。 鄰接與關(guān)聯(lián)鄰接與關(guān)聯(lián)：當（：當（ v 1， v 2） E，或，或 E，即，即 v 1， v 2間有邊相連時，則稱間有邊相連時，則稱 v 1和和 v 2是相鄰的，它們互為鄰接點是相鄰的，它們互為鄰接點（ adjacent），同時稱（），同時稱（ v 1， v 2）或）或 是與頂點是與頂點 v 1、 v 2相關(guān)聯(lián)的邊。相關(guān)聯(lián)的邊。 頂點的度數(shù)頂點的度數(shù) (degree)：從

7、該頂點引出的邊的條數(shù)，即與該：從該頂點引出的邊的條數(shù)，即與該頂點相關(guān)聯(lián)的邊的數(shù)目，簡稱度。頂點相關(guān)聯(lián)的邊的數(shù)目，簡稱度。入度入度（ indegree）：有向圖中把以頂點）：有向圖中把以頂點 v為終點的邊的條為終點的邊的條數(shù)稱為是頂點數(shù)稱為是頂點 v的入度。的入度。 出度出度（ outdegree）：有向圖中把以頂點）：有向圖中把以頂點 v為起點的邊的條為起點的邊的條數(shù)稱為是頂點數(shù)稱為是頂點 v的出度。的出度。終端頂點：有向圖中把出度為終端頂點：有向圖中把出度為 0的頂點稱為終端頂點，如圖的頂點稱為終端頂點，如圖 5-1中中 圖的圖的 v 3。 路徑與路長路徑與路長：在圖：在圖 G=( V， E

8、)中，如果存在由不同的邊中，如果存在由不同的邊 (v i0， v i1 )， (v i1， v i2 )， ， (v in-1， v in )或是或是 ， ， ， )組成組成的序列，則稱頂點的序列，則稱頂點 v i0， v in是連通的，頂點序列（是連通的，頂點序列（ v i0， v i1， v i2， ， v in）是從頂點）是從頂點 v i0到頂點到頂點 v in的一條的一條道路。路長是道路上邊的數(shù)目，道路。路長是道路上邊的數(shù)目， v i0到到 v in的這條道路上的這條道路上的路長為的路長為 n。 連通圖連通圖：對于圖中任意兩個頂點：對于圖中任意兩個頂點 v i、 v j V， v i、

9、 v j之之間有道路相連，則稱該圖為連通圖。如間有道路相連，則稱該圖為連通圖。如 5-1中的中的 圖。圖。網(wǎng)絡(luò)網(wǎng)絡(luò)：帶權(quán)的連通圖，如圖：帶權(quán)的連通圖，如圖 5-2所示。所示。3隱式圖術(shù)語 1）子集樹 當要求解的問題需要是在當要求解的問題需要是在n n 個元素的子集中進行搜索，其搜個元素的子集中進行搜索，其搜索空間樹被稱作索空間樹被稱作子集樹子集樹（subset treesubset tree）。這）。這n n個元素都有在子個元素都有在子集中或被選取記為集中或被選取記為1 1，不在子集中或被舍去記為，不在子集中或被舍去記為0 0，這樣搜索空，這樣搜索空間為：間為： （0 0，0 0，0 0，0

10、0），（），（0 0，0 0，0 0，1 1），）， （0 0，0 0，1 1，0 0），（），（0 0，0 0，1 1，1 1），）， （1 1，1 1，1 1，1 1）。）。共共2 2n n 個狀態(tài)。若表示為樹形結(jié)構(gòu)就是一棵有個狀態(tài)。若表示為樹形結(jié)構(gòu)就是一棵有2 2n n個葉結(jié)點的二叉?zhèn)€葉結(jié)點的二叉樹，對樹中所有分支進行遍歷的算法都必須耗時樹，對樹中所有分支進行遍歷的算法都必須耗時O（2n）。）。 圖圖5-3 n=3的子集樹的子集樹 當要求解的問題需要在當要求解的問題需要在n n 元素的排列中搜索問題的解時，元素的排列中搜索問題的解時，解空間樹被稱作解空間樹被稱作排列樹排列樹（permut

11、ation treepermutation tree）。）。搜索空間為：搜索空間為：（1 1，2 2，3 3，n-1n-1，n n）, , （2 2，1 1，3 3，n-1n-1，n n）, , （2 2，3 3，1 1，n-1n-1，n n）, ,（2 2，3 3，4 4，1 1，n-1n-1，n n）, ,（n n，n-1n-1，3 3，2 2，1 1） 第一個元素有第一個元素有n 種選擇，第二個元素有種選擇，第二個元素有n-1種選擇，第三個種選擇，第三個元素有元素有n-2種選擇，種選擇，第，第n個元素有個元素有1種選擇，共計種選擇，共計n!個狀態(tài)。個狀態(tài)。若表示為樹形就是一個若表示為樹形

12、就是一個n度樹，這樣的樹有度樹，這樣的樹有n! 個葉結(jié)點，所以每個葉結(jié)點，所以每一個遍歷樹中所有節(jié)點的算法都必須耗時一個遍歷樹中所有節(jié)點的算法都必須耗時O(n! ) 2）排列樹 圖圖5-3 n=4的部分子集樹的部分子集樹 12503418 X1=115121o75173133282623211383292419454035615651141196416303227252220234 X2=2341 3 41 241 23X3=311 43 42 32 43 44 3 4 2 3 2 4 3 4 1 3 x4=1 4圖的存儲 1）鄰接矩陣法 鄰接矩陣是表示頂點之間相鄰關(guān)系的矩陣，鄰接矩陣是表示頂

13、點之間相鄰關(guān)系的矩陣，設(shè)設(shè)G=(V,E)G=(V,E)是具有是具有n n個頂點的圖，則個頂點的圖，則G G的鄰接矩陣可定義為：的鄰接矩陣可定義為： Ai,j=1, Ai,j=1, 若（若（Vi,Vj)Vi,Vj)或或是是E(G)E(G)中的邊。中的邊。 Ai,j=0, Ai,j=0, 若若 (Vi,Vj)(Vi,Vj)或或不是不是E(G)E(G)中的邊。中的邊。若若G G是網(wǎng)絡(luò)，則鄰接矩陣可定義為：是網(wǎng)絡(luò)，則鄰接矩陣可定義為： Ai,j=WAi,j=Wij ij 若（若（Vi,Vj)Vi,Vj)或或?qū)儆趯儆贓(G);E(G); Ai,j=0或或 若（若（Vi,Vj）或）或 不屬于不屬于E(G)

14、; 其中，其中，Wij表示邊上的權(quán)值，表示邊上的權(quán)值，表示一個計算機允許的，大于表示一個計算機允許的，大于所有邊上權(quán)值的數(shù)；所有邊上權(quán)值的數(shù)； 2）鄰接表 對于圖對于圖G G中的每個結(jié)點中的每個結(jié)點Vi, Vi, 把所有鄰接于把所有鄰接于ViVi的頂點的頂點VjVj鏈成一個鏈成一個單鏈表，這個單鏈表就稱為頂點單鏈表，這個單鏈表就稱為頂點ViVi的鄰接表。的鄰接表。 鄰接表由邊表和頂點兩部分組成。鄰接表由邊表和頂點兩部分組成。 邊表為一個單鏈表，每個表結(jié)點均有兩個域：邊表為一個單鏈表，每個表結(jié)點均有兩個域： 鄰接點域鄰接點域adjvexadjvex，存放與，存放與vivi相鄰接的頂點相鄰接的頂點

15、v vj j的序號的序號j j。 鏈 域鏈 域 n e x tn e x t ， 將 鄰 接 表 的 所 有 表 結(jié) 點 鏈 在 一 起 。， 將 鄰 接 表 的 所 有 表 結(jié) 點 鏈 在 一 起 。 頂 點 表 為 一 數(shù) 組 ， 每 個 元 素 均 有 兩 個 域 ：頂 點 表 為 一 數(shù) 組 ， 每 個 元 素 均 有 兩 個 域 ： 頂 點 域頂 點 域 v e r t e xv e r t e x ， 存 放 頂 點， 存 放 頂 點 v vi i的 信 息的 信 息 指針域指針域firstedgefirstedge， v vi i的邊表的頭指針。的邊表的頭指針。 對于無向圖來說，

16、對于無向圖來說，ViVi的鄰接表中每個表結(jié)點都對應(yīng)于與的鄰接表中每個表結(jié)點都對應(yīng)于與ViVi相相關(guān)聯(lián)的一條邊，關(guān)聯(lián)的一條邊， 對于有向圖來說，對于有向圖來說，ViVi的鄰接表中每個表結(jié)點對應(yīng)于的鄰接表中每個表結(jié)點對應(yīng)于ViVi為始點為始點射出的一條邊。射出的一條邊。 圖圖7.17.1 圖圖5-5 圖圖5-1中（中（1）圖的鄰接表）圖的鄰接表 5 51 12 2 圖搜索及其術(shù)語圖搜索及其術(shù)語1 1窮舉搜索與啟發(fā)式搜索窮舉搜索與啟發(fā)式搜索 窮舉搜索窮舉搜索是對圖的最基本的搜索算法，是是對圖的最基本的搜索算法，是蠻力策略的一種蠻力策略的一種表現(xiàn)形式表現(xiàn)形式。即不考慮給定問題的特有性質(zhì)，按事先定好的順

17、序，。即不考慮給定問題的特有性質(zhì)，按事先定好的順序，依次運用規(guī)則，依次運用規(guī)則，盲目搜索盲目搜索的方法。的方法。 啟發(fā)式搜索啟發(fā)式搜索是利用一些啟發(fā)信息，提前判斷出先搜索哪些是利用一些啟發(fā)信息，提前判斷出先搜索哪些狀態(tài)可能盡快找到問題的解或某些情況不可能取到最優(yōu)解，從狀態(tài)可能盡快找到問題的解或某些情況不可能取到最優(yōu)解，從而可以提前舍棄對這些狀態(tài)的嘗試。即考慮給定問題的特有性而可以提前舍棄對這些狀態(tài)的嘗試。即考慮給定問題的特有性質(zhì)，選用合適的細則，提高搜索的效率。質(zhì)，選用合適的細則，提高搜索的效率。 2 2相關(guān)概念和術(shù)語相關(guān)概念和術(shù)語 問題狀態(tài)問題狀態(tài): :樹中的每一個結(jié)點確定所求解問題的一個問

18、題狀態(tài)。樹中的每一個結(jié)點確定所求解問題的一個問題狀態(tài)。狀態(tài)空間狀態(tài)空間: :由根結(jié)點到其它結(jié)點的由根結(jié)點到其它結(jié)點的所有路徑所有路徑（分支），就確定（分支），就確定 了這個問題的狀態(tài)空間。了這個問題的狀態(tài)空間。解狀態(tài)解狀態(tài): :是這樣一些問題狀態(tài)是這樣一些問題狀態(tài)S，對于這些問題狀態(tài)，由根到，對于這些問題狀態(tài)，由根到S 的那條路徑確定了這解空間中的一個元組。的那條路徑確定了這解空間中的一個元組。 答案狀態(tài)答案狀態(tài): :是這樣的一些解狀態(tài)是這樣的一些解狀態(tài)S，對于這些解狀態(tài)而言，由，對于這些解狀態(tài)而言，由 根到根到S的這條路徑確定了這問題的一個解的這條路徑確定了這問題的一個解狀態(tài)空間樹狀態(tài)空間樹

19、: :解空間的樹結(jié)構(gòu)解空間的樹結(jié)構(gòu), ,又稱隱式圖。又稱隱式圖。 活結(jié)點活結(jié)點：如果已生成一個結(jié)點而它的所有兒子結(jié)點還沒有：如果已生成一個結(jié)點而它的所有兒子結(jié)點還沒有全部生成，則這個結(jié)點叫做活結(jié)點。全部生成，則這個結(jié)點叫做活結(jié)點。 E-結(jié)點結(jié)點：當前正在生成其兒子結(jié)點的活結(jié)點叫：當前正在生成其兒子結(jié)點的活結(jié)點叫E-結(jié)點（正結(jié)點（正 擴展的結(jié)點）。擴展的結(jié)點）。死結(jié)點死結(jié)點 ：不再進一步擴展或者其兒子結(jié)點已全部生成的生：不再進一步擴展或者其兒子結(jié)點已全部生成的生成結(jié)點就是死結(jié)點成結(jié)點就是死結(jié)點 。5 52 21 1 算法框架算法框架 1算法的基本思路算法的基本思路 算法設(shè)計的基本步驟為算法設(shè)計的

20、基本步驟為： 1）確定圖的存儲方式；）確定圖的存儲方式； 2）圖的遍歷過程中的操作，其中包括為輸出問題解）圖的遍歷過程中的操作，其中包括為輸出問題解而進行的存儲操作；而進行的存儲操作； 3 3）輸出問題的結(jié)論。）輸出問題的結(jié)論。 2 2算法框架算法框架 從從廣度優(yōu)先搜索定義可以看出活結(jié)點的擴展是按先來先處廣度優(yōu)先搜索定義可以看出活結(jié)點的擴展是按先來先處理的原則進行的，所以在算法中要用理的原則進行的，所以在算法中要用“隊隊”來存儲每個來存儲每個E-E-結(jié)點結(jié)點擴展出的活結(jié)點。為了算法的簡潔，抽象地定義：擴展出的活結(jié)點。為了算法的簡潔，抽象地定義：queuequeue為隊列類型，為隊列類型，Ini

21、tQueue( ) InitQueue( ) 為隊列初始化函數(shù)，為隊列初始化函數(shù)， EnQueue(QEnQueue(Q，k)k)為入隊函數(shù)，為入隊函數(shù)，QueueEmpty(Q) QueueEmpty(Q) 為判斷隊空函數(shù)，為判斷隊空函數(shù)，DeQueue(Q) DeQueue(Q) 為出隊函數(shù)。為出隊函數(shù)。 實際應(yīng)用中，用數(shù)組或鏈表實現(xiàn)隊列。實際應(yīng)用中，用數(shù)組或鏈表實現(xiàn)隊列。 開辟數(shù)組開辟數(shù)組visitedvisited記錄記錄visitedvisited結(jié)點的搜索情況。結(jié)點的搜索情況。 在算法框架中以輸出結(jié)點值表示在算法框架中以輸出結(jié)點值表示“訪問訪問”。1）鄰接表表示圖的廣度優(yōu)先搜索算法

22、 int visitedn; /n visitedn; /n 為結(jié)點個數(shù)為結(jié)點個數(shù)/ /bfs(int k,graph head) int i； queue Q ； edgenode *p； /定義隊列定義隊列/ InitQueue(Q)； /隊列初始化隊列初始化/ print(“visit vertex”，k)； / 訪問源點訪問源點vk/ visitedk=1； EnQueue(Q，k)； /vk已訪問，將其入隊。已訪問，將其入隊。/ while(!QueueEmpty(Q) /隊非空則執(zhí)行隊非空則執(zhí)行/ i=DeQueue(Q)； / vi出隊為出隊為E-結(jié)點結(jié)點/ p=headi.fi

23、rstedge； /取取vi的邊表頭指針的邊表頭指針/ while(pnull) /擴展擴展E-結(jié)點結(jié)點 / if(visitedp-adjvex=0) /若若vj未訪問過未訪問過/ print (“visitvertex”，p-adjvex)；/訪問訪問vj/ visitedp-adjvex=1； EnQueue(Q，p-adjvex)； /訪問過的訪問過的vj人隊人隊/ p=p-next ； /找找vi的下一鄰接點的下一鄰接點/ 2）鄰接矩陣表示的圖的廣度優(yōu)先搜索算法bfsm(int k, graph g100，int n) int i，j； CirQueue Q； InitQueue(Q

24、)； print (visit vertex， k)； /訪問源點訪問源點vk/ visitedk=1； EnQueue(Q，k)； while(not QueueEmpty(Q) i=DeQueue(Q)； /vi出隊出隊/ for(j=0;jn;j+) /擴展結(jié)點擴展結(jié)點/ if(gij=1 and visitedj=0) print(visit vertex，j)； visitedj=1； EnQueue(Q，j)； /訪問過的訪問過的vj人隊人隊/ 522 廣度優(yōu)先搜索的應(yīng)用廣度優(yōu)先搜索的應(yīng)用 【例【例1 1】已知若干個城市的地圖，求從一個城市】已知若干個城市的地圖，求從一個城市到另一

25、個城市的路徑，要求路徑中經(jīng)過的城市最到另一個城市的路徑，要求路徑中經(jīng)過的城市最少少 【例【例2 2】走迷宮問題】走迷宮問題 【例【例1 1】已知若干個城市的地圖，求從一個城市到另一個】已知若干個城市的地圖，求從一個城市到另一個城市的路徑，要求路徑中經(jīng)過的城市最少。城市的路徑，要求路徑中經(jīng)過的城市最少。 算法設(shè)計：算法設(shè)計： 圖的廣度優(yōu)先搜索類似與樹的層次遍圖的廣度優(yōu)先搜索類似與樹的層次遍歷，逐層搜索正好可以盡快找到一個結(jié)點歷，逐層搜索正好可以盡快找到一個結(jié)點與另一個結(jié)點相對而言最直接的路徑。與另一個結(jié)點相對而言最直接的路徑。 如圖如圖5-6表示的是從城市表示的是從城市A到城市到城市H的交通圖。

26、的交通圖。從圖中可以看出，從城市從圖中可以看出，從城市A到城市到城市H要經(jīng)過若干個要經(jīng)過若干個城市?，F(xiàn)要找出一條經(jīng)過城市最少一條路線。城市?，F(xiàn)要找出一條經(jīng)過城市最少一條路線。 圖5-6 表5-1 圖5-6的鄰接距陣 具體過程如下：具體過程如下： 1 1）將城市）將城市A A（編號（編號1 1）入隊，隊首）入隊，隊首qhqh置為置為0 0、隊尾、隊尾qeqe置為置為1 1。2 2）將隊首所指的城市所有可直通的城市入隊）將隊首所指的城市所有可直通的城市入隊( (如果這如果這個城市在隊中出現(xiàn)過就不入隊個城市在隊中出現(xiàn)過就不入隊),),然后將隊首加然后將隊首加1 1，得到，得到新的隊首城市。重復(fù)以上步

27、驟，直到城市新的隊首城市。重復(fù)以上步驟，直到城市H H入隊為止。入隊為止。當搜到城市當搜到城市H H時，搜索結(jié)束。時，搜索結(jié)束。 3）輸出最少城市線路）輸出最少城市線路。 數(shù)據(jù)結(jié)構(gòu)設(shè)計：數(shù)據(jù)結(jié)構(gòu)設(shè)計： 1 1）線性數(shù)組）線性數(shù)組a作為活結(jié)點隊的存儲空間。作為活結(jié)點隊的存儲空間。2 2）隊列的每個結(jié)點有兩個成員：）隊列的每個結(jié)點有兩個成員：ai.city記記錄入隊的城市，錄入隊的城市，ai.pre記錄該城市的前趨城記錄該城市的前趨城市在隊列中的下標，這樣通過市在隊列中的下標，這樣通過ai.pre就可以就可以倒推出最短線路。倒推出最短線路。3 3）設(shè)置數(shù)組）設(shè)置數(shù)組visited記錄已搜索過的城市

28、。記錄已搜索過的城市。 算法如下：算法如下：search( )( )qh=0; qe=1;sq1.city=1;sq1.pre=0;visited1=1;qh=0; qe=1;sq1.city=1;sq1.pre=0;visited1=1; while( qhqe) / while( qhqe) /當隊不空當隊不空/ /qh=qh+1; /qh=qh+1; /結(jié)點出隊結(jié)點出隊/ / for(i=1;i=n,i+) /for(i=1;i=n,i+) /擴展結(jié)點擴展結(jié)點/ / if if （jzsqqh.cityi=1 and visitedi=0jzsqqh.cityi=1 and visite

29、di=0） qe=qe+1; / qe=qe+1; /結(jié)點入隊結(jié)點入隊/ /sqqe.city=i;sqqe.pre=qh;visitedqe=1;sqqe.city=i;sqqe.pre=qh;visitedqe=1;if (sqqe.city=8) out( );if (sqqe.city=8) out( ); print(“No avaliable way.”);print(“No avaliable way.”); 算法分析：時間復(fù)雜度是算法分析：時間復(fù)雜度是O（n）；空間復(fù)雜性為）；空間復(fù)雜性為（n2），包括圖本身的存儲空間和搜索時輔助空間），包括圖本身的存儲空間和搜索時輔助空間“隊

30、隊”的存儲空間。的存儲空間。out( ); /out( ); /輸出路徑輸出路徑/ /print(sqqe.city);print(sqqe.city); while(sqqe.pre0)while(sqqe.pre0) qe=sqqe.pre; print(-,sqqe.city); 【例【例2】走迷宮問題】走迷宮問題 迷宮是許多小方格構(gòu)成的矩形，在每個小方格中有的是墻（圖中的迷宮是許多小方格構(gòu)成的矩形，在每個小方格中有的是墻（圖中的“1”1”）有的是路（圖中的）有的是路（圖中的“0”0”）。走迷宮就是從一個小方格沿上、下、左、）。走迷宮就是從一個小方格沿上、下、左、右四個方向到鄰近的方格，

31、當然不能穿墻。設(shè)迷宮的入口是在左上角右四個方向到鄰近的方格，當然不能穿墻。設(shè)迷宮的入口是在左上角(1,1)(1,1)，出口是右下角出口是右下角(8,8)(8,8)。根據(jù)給定的迷宮，找出一條從入口到出口的路徑。根據(jù)給定的迷宮，找出一條從入口到出口的路徑。 算法設(shè)計：算法設(shè)計： 從入口開始廣度優(yōu)先搜索可到達的方格入隊，再擴展從入口開始廣度優(yōu)先搜索可到達的方格入隊，再擴展 隊首的方格，直到搜索到出口時算法結(jié)束。隊首的方格，直到搜索到出口時算法結(jié)束。 對于迷宮中任意一點對于迷宮中任意一點A（Y，X），有四個搜索方向：），有四個搜索方向： 向上向上A（Y-1，X） 向下向下A（Y+1，X） 向左向左A（

32、Y，X-1） 向右向右A（Y，X+1） 當對應(yīng)方格可行（值為當對應(yīng)方格可行（值為0），就擴展為活結(jié)點。），就擴展為活結(jié)點。 數(shù)據(jù)結(jié)構(gòu)設(shè)計數(shù)據(jù)結(jié)構(gòu)設(shè)計： 用數(shù)組做隊的存儲空間，隊中結(jié)點有三個用數(shù)組做隊的存儲空間，隊中結(jié)點有三個成員：行號、列號、前一個方格在隊列中的成員：行號、列號、前一個方格在隊列中的下標。搜索過的方格不另外開辟空間記錄其下標。搜索過的方格不另外開辟空間記錄其訪問的情況，而是用迷宮原有的存儲空間置訪問的情況，而是用迷宮原有的存儲空間置元素值為元素值為“-1”-1”時，標識已經(jīng)訪問過該方格。時，標識已經(jīng)訪問過該方格。 為了構(gòu)造循環(huán)體，用數(shù)組為了構(gòu)造循環(huán)體，用數(shù)組fx=1,-1,0,

33、0fx=1,-1,0,0、fy= 0,0,-1,1 fy= 0,0,-1,1 模擬上下左右搜索時的下標模擬上下左右搜索時的下標的變化過程。的變化過程。 int jz88= 1,0,0,0,1,0,1,1,0,1,1,1,1,0,1,1, 0,1,1,0,0,1,1,1, 0,1,0,1,1,1,0,1, 1,1,0,1,1,1,0,0,0,0,1,1,1,1,1,0, 1,1,1,0,0,1,1,0, 1,1,1,1,0,0,0,1;struct intcity, pre; sq100;int qh,qe,i,visited100;main( )int i,n=8;for(i=1;i=n,i=

34、i+1) visitedi=0;search( );search( )qh=0; qe=1;maze11=-1;Sq1.pre=0;sq1.x=1;sq1.y=1; while( qhqe) /當隊不空當隊不空/qh=qh+1; /結(jié)點出隊結(jié)點出隊/ for(k=1;k=4,k=k+1) /擴展結(jié)點擴展結(jié)點/i=sqqh.x+fxk;j=sqqh.y+fyk; if(check(i,j)=1) qe =qe+1;sqqe.x=i;sqqe.y=j; sqqe.pre=qh;mazeij=-1; if(sqqe.x =8 and sqqe.y=8) out();return; 檢查位置函數(shù)檢查位

35、置函數(shù)Check(int i,int j)int flag = 1;if(i8 or j8) flag =0;/是否在迷宮內(nèi)是否在迷宮內(nèi)if(mazeij=1 or mazeij=-1)flag=0;/是否可行是否可行return flag;out( );/輸出路徑輸出路徑/print(“(”,sqqe.x,”,”sqqe.y,”)”);while(sqqe.pre0) qe=sqqe.pre; print(-, “(”,sqqe.x,”,”sqqe.y,”)”);算法分析：算法分析： 算法算法的時間復(fù)雜度并不復(fù)雜是的時間復(fù)雜度并不復(fù)雜是O O（n n），算法的空間復(fù)雜性），算法的空間復(fù)雜性為

36、為O O（n n2 2），包括圖本身的存儲空間和搜索時輔助空間），包括圖本身的存儲空間和搜索時輔助空間“隊隊”的的存儲空間。存儲空間。 輸出路徑及算法分析輸出路徑及算法分析 深度優(yōu)先遍歷首先訪問出發(fā)點深度優(yōu)先遍歷首先訪問出發(fā)點v v，并將其標記為已，并將其標記為已訪問過；然后依次從訪問過；然后依次從v v出發(fā)搜索出發(fā)搜索v v的每個鄰接點的每個鄰接點w w。若。若w w未未曾訪問過，則以曾訪問過，則以w w為新的出發(fā)點繼續(xù)進行深度優(yōu)先遍歷，為新的出發(fā)點繼續(xù)進行深度優(yōu)先遍歷，直至圖中所有和源點直至圖中所有和源點v v有路徑相通的頂點均已被訪問為有路徑相通的頂點均已被訪問為止。止。 若此時圖中仍有

37、未訪問的頂點，則另選一個尚未訪若此時圖中仍有未訪問的頂點，則另選一個尚未訪問的頂點作為新的源點重復(fù)上述過程，直至圖中所有頂問的頂點作為新的源點重復(fù)上述過程，直至圖中所有頂點均已被訪問為止。點均已被訪問為止。5.3 深度優(yōu)先搜索深度優(yōu)先搜索 深度搜索與廣度搜索的相近，最終都要擴展一個深度搜索與廣度搜索的相近，最終都要擴展一個結(jié)點的所有子結(jié)點結(jié)點的所有子結(jié)點. . 區(qū)別在于對擴展結(jié)點過程，深度搜索擴展的是區(qū)別在于對擴展結(jié)點過程，深度搜索擴展的是E-E-結(jié)結(jié)點的鄰接結(jié)點中的一個，并將其作為新的點的鄰接結(jié)點中的一個，并將其作為新的E-E-結(jié)點繼續(xù)擴結(jié)點繼續(xù)擴展，當前展，當前E-E-結(jié)點仍為活結(jié)點，待搜

38、索完其子結(jié)點后，回結(jié)點仍為活結(jié)點，待搜索完其子結(jié)點后，回溯到該結(jié)點擴展它的其它未搜索的鄰接結(jié)點。而廣度搜溯到該結(jié)點擴展它的其它未搜索的鄰接結(jié)點。而廣度搜索，則是擴展索，則是擴展E-E-結(jié)點的所有鄰接結(jié)點，結(jié)點的所有鄰接結(jié)點，E-E-結(jié)點就成為一結(jié)點就成為一個死結(jié)點。個死結(jié)點。531 算法框架算法框架 1 1算法的基本思路算法的基本思路 2 2算法框架算法框架1算法的基本思路算法的基本思路 算法設(shè)計的基本步驟為： 1）確定圖的存儲方式； 2）遍歷過程中的操作，其中包括為輸出問題解而進行的存儲操作； 3）輸出問題的結(jié)論。 4）一般在回溯前的應(yīng)該將結(jié)點狀態(tài)恢復(fù)為原始狀態(tài)，特別是在有多解需求的問題中。

39、2算法框架 1）用鄰接表存儲圖的搜索算法 2）用鄰接矩陣存儲圖的搜索算法graph head100graph head100；dfs(int k) / headdfs(int k) / head圖的頂點數(shù)組圖的頂點數(shù)組/ / edgenode edgenode * *ptr / ptrptr / ptr圖的邊表指針圖的邊表指針/ / visitedk=1; / visitedk=1; /* * 記錄已遍歷過記錄已遍歷過 * */ / print(“ print(“訪問訪問 ”,k); /,k); /* * 印出遍歷頂點值印出遍歷頂點值 * */ / ptr=headk.firstedge; /

40、 ptr=headk.firstedge; /* * 頂點的第一個鄰接點頂點的第一個鄰接點 * */ / while ( ptr NULL ) / while ( ptr NULL ) /* * 遍歷至鏈表尾遍歷至鏈表尾 * */ / if ( visitedptr-vertex=0) / if ( visitedptr-vertex=0) /* * 如果沒遍歷過如果沒遍歷過 * */ / dfs(ptr-vertex); / dfs(ptr-vertex); /* * 遞歸遍歷遞歸遍歷 * */ / ptr = ptr-nextnode; / ptr = ptr-nextnode; /* *

41、 下一個頂點下一個頂點 * */ / 算法分析：算法分析：n n圖中有圖中有 n n 個頂點，個頂點，e e 條邊。掃描邊的時間為條邊。掃描邊的時間為O(e)O(e)。遍歷圖。遍歷圖的時間復(fù)雜性為的時間復(fù)雜性為O(n+e)O(n+e)。 ngraph g100100,int ngraph g100100,int n；ndfsm(int k)dfsm(int k) int j int j； print(“ print(“訪問訪問 ”,k);,k); visitedk=1 visitedk=1； for(j=1 for(j=1；j=nj=n；j+) /j+) /依次搜索依次搜索vkvk的鄰接點的鄰

42、接點 if(gkj=1 and visitedj=0) if(gkj=1 and visitedj=0) dfsm(g,j) dfsm(g,j) /(vk /(vk，vj)Evj)E，且，且vjvj未訪問過，故未訪問過，故vjvj為新出發(fā)點為新出發(fā)點 算法分析：查找每一個頂點的所有的邊，所需時間為算法分析：查找每一個頂點的所有的邊，所需時間為O(n)O(n)，遍，遍歷圖中所有的頂點所需的時間為歷圖中所有的頂點所需的時間為O(n2)O(n2)。 532 深度優(yōu)先搜索的應(yīng)用深度優(yōu)先搜索的應(yīng)用【例1】走迷宮問題：問題同522【例2】1、算法設(shè)計、算法設(shè)計：深度優(yōu)先搜索，就是一直向著可通行的下一個方格

43、行進，直到搜索到出口就找到一個解。若行不通時，則返回上一個方格，繼續(xù)搜索其它方向。2 2、數(shù)據(jù)結(jié)構(gòu)設(shè)計、數(shù)據(jù)結(jié)構(gòu)設(shè)計：我們還是用迷宮本身的存儲空間除了記錄走過的信息，還要標識是否可行： mazeij=3 標識走過的方格 ； mazeij=2 標識走入死胡同的方格，這樣，最后存儲為“3”的方格為可行的方格。而當一個方格四個方向都搜索完還沒有走到出口，說明該方格或無路可走或只能走入了“死胡同”。3 3、算法、算法int maze88=0,0,0,0,0,0,0,0,int maze88=0,0,0,0,0,0,0,0, 0,11,1,1,0,1,0,0,0,0,0,1,0,1,0, 0,11,1,

44、1,0,1,0,0,0,0,0,1,0,1,0, 0,1,0,0,0,0,1,0,0,1,0,1,1,0,1,0, 0,1,0,0,0,0,1,0,0,1,0,1,1,0,1,0, 0,1,0,0,0,0,1,1,0,1,0,0,1,0,0,0, 0,1,0,0,0,0,1,1,0,1,0,0,1,0,0,0, 0,1,1,1,1,1,1,0;fx4=1,-1,0,0, 0,1,1,1,1,1,1,0;fx4=1,-1,0,0, fy4=0,0,-1,1; int i,j,k,total; fy4=0,0,-1,1; int i,j,k,total;main( )main( ) int tot

45、al=0; int total=0; maze11=3; / maze11=3; /入口坐標設(shè)置已走標志入口坐標設(shè)置已走標志/ / search(1,1); search(1,1); print(“Total is”,total); / print(“Total is”,total); /統(tǒng)計總步數(shù)統(tǒng)計總步數(shù)/ / nsearch(int i, int j)search(int i, int j)int k,newi,newj;int k,newi,newj; for(k=1;k=4;k+) / for(k=1;k=4;k+) /搜索可達的方格搜索可達的方格/ / if(check(i,j,k

46、)=1) if(check(i,j,k)=1) newi=i+fxk; newj=j+fyk; newi=i+fxk; newj=j+fyk; mazenewinewj=3; / mazenewinewj=3; /來到新位置后來到新位置后, ,設(shè)置已走過標志設(shè)置已走過標志/ / if (newi=8 and newj=8) / if (newi=8 and newj=8) /到出口則輸出到出口則輸出, ,否則下一步遞歸否則下一步遞歸/ / Out( ); Out( ); else search(newi,newj); else search(newi,newj); mazeij=2; / ma

47、zeij=2; /某一方格只能走入死胡同某一方格只能走入死胡同/ / nOut( )Out( )n int i,j; int i,j; for( i=1;i=8;i+) for( i=1;i=8;i+) n print(“ print(“換行符換行符”););n for(j=1;j=8;j+) for(j=1;j=8;j+) n if if（mazeij=3mazeij=3） n print(“V”);print(“V”);n total+; / total+; /統(tǒng)計總步數(shù)統(tǒng)計總步數(shù)/ /n else elsen print(“ print(“* *”);”);n n check(int i

48、,int j,int k)check(int i,int j,int k)int flag=1;int flag=1; i= i+fxk; j= j +fyk; i= i+fxk; j= j +fyk; if(i8 or j8) / if(i8 or j8) /是否在迷宮內(nèi)是否在迷宮內(nèi)/ / flag=0; flag=0; else else if(mazeij0) / if(mazeij0) /是否可行是否可行/ / flag=0; flag=0; return(flag); return(flag); 4、算法說明、算法說明：1）和廣度優(yōu)先算法一樣每個方格有四個方向可以）和廣度優(yōu)先算法一樣

49、每個方格有四個方向可以進行搜索，這樣一點結(jié)點（方格）就可多次成為進行搜索，這樣一點結(jié)點（方格）就可多次成為“活結(jié)點活結(jié)點”，而在廣度優(yōu)先算法一點結(jié)點（方格），而在廣度優(yōu)先算法一點結(jié)點（方格）就可一次成為就可一次成為“活結(jié)點活結(jié)點”，一出隊就成了死結(jié)點。，一出隊就成了死結(jié)點。2）用廣度優(yōu)先算法，用廣度優(yōu)先算法，搜索出的是搜索出的是一條最短的路徑一條最短的路徑，而用而用深度優(yōu)先深度優(yōu)先搜索則搜索則只能找出一條可行只能找出一條可行的路徑，的路徑，而不能保證是最短的路徑。而不能保證是最短的路徑。3）在空間效率上二者相近。都需要輔助空間。）在空間效率上二者相近。都需要輔助空間。 【例【例2】有如圖】有如

50、圖1所示的七巧板，試編寫一源所示的七巧板，試編寫一源程序如下，使用至多四種不同顏色對七巧板進行程序如下，使用至多四種不同顏色對七巧板進行涂色涂色(每塊涂一種顏色每塊涂一種顏色)，要求相鄰區(qū)域的顏色互，要求相鄰區(qū)域的顏色互不相同，打印輸出所有可能的涂色方案。不相同，打印輸出所有可能的涂色方案。 n1、問題分析、問題分析:為了讓算法能識別不同區(qū)域間的相鄰關(guān) 系，我們把七巧板上每一個區(qū)域看成一個頂點若兩個區(qū)域相鄰，則相應(yīng)的頂點間用一條邊相連，這樣該問題就轉(zhuǎn)化為圖一個圖的搜索問題了。2 2、算法設(shè)計、算法設(shè)計: : 按順序分別對號、號、按順序分別對號、號、.、號區(qū)域進行、號區(qū)域進行試探性涂色，用、號代

51、表種顏色。試探性涂色，用、號代表種顏色。 則涂色過程如下：則涂色過程如下： 1 1）對某一區(qū)域涂上與其相鄰區(qū)域不同的顏色。）對某一區(qū)域涂上與其相鄰區(qū)域不同的顏色。 2 2）若使用種顏色進行涂色均不能滿足要求，則）若使用種顏色進行涂色均不能滿足要求，則回溯一步，更改前一區(qū)域的顏色?；厮菀徊剑那耙粎^(qū)域的顏色。 3 3）轉(zhuǎn)步驟繼續(xù)涂色，直到全部區(qū)域全部涂色為）轉(zhuǎn)步驟繼續(xù)涂色，直到全部區(qū)域全部涂色為止，輸出結(jié)果。止，輸出結(jié)果。 已經(jīng)有研究證明，對任意的平面圖至少存在一種四已經(jīng)有研究證明，對任意的平面圖至少存在一種四色涂色法。色涂色法。3、數(shù)據(jù)采用的存儲結(jié)構(gòu)：鄰接矩陣存儲 0 1 0 0 1 0 1

52、 1 0 0 1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1 1 1 0 0 0 0 0 1 0 1 1 1 0 0 0 1 0 1 1 1 0 0n4 4、算法如下、算法如下: :nint data77,n,color7,total;int data77,n,color7,total;nmain( )main( )n int i,j; int i,j;n for(i=1;i=n;i+) for(i=1;i=n;i+) n for(j=1;j=n;j+) for(j=1;j=n;j+)n input(dataij); input(dataij);n for(j=1;j=n;

53、j+) for(j=1;j7) if (s7)n output( ); output( ); else else for(i=1;i=4;i+) for(i=1;i=4;i+) colors=i; colors=i; if if （colorsame(s)=0colorsame(s)=0）n try(s+1);try(s+1); n noutput( )output( ) int i,; int i,; print( print(換行符，換行符，serial numberserial number：,total);,total); for i:=1 to n do for i:=1 to n

54、do n print(colori); print(colori); total=total+1; total=total+1;n ncolorsame(int s) /colorsame(int s) /判斷相鄰點是否同色判斷相鄰點是否同色/ / int i,flag; int i,flag; flag=0; flag=0; for(i=1;i=s-1;i+) for(i=1;iDFN(3)=3L(10)=4DFN(3)=3。同理，結(jié)點。同理，結(jié)點2 2、5 5也是也是關(guān)結(jié)點。關(guān)結(jié)點。 按后根次序訪問深度優(yōu)先生成樹的結(jié)點，可按后根次序訪問深度優(yōu)先生成樹的結(jié)點，可以很容易地算出以很容易地算出L

55、 L（U U）。于是，為了確定圖）。于是，為了確定圖G G的的關(guān)結(jié)點關(guān)結(jié)點, ,必須既完成對必須既完成對G G的深度優(yōu)先檢索，產(chǎn)生的深度優(yōu)先檢索，產(chǎn)生G G的深度優(yōu)先生成樹的深度優(yōu)先生成樹T T，又要按后根次序訪問樹，又要按后根次序訪問樹T T的的結(jié)點。結(jié)點。算法算法ARTART計算計算DFNDFN和和L L的算法如下：的算法如下： int DFNnint DFNn，LnLn，numnum，n n ART ART（u u，v v） /u/u是深度優(yōu)先檢索的開始是深度優(yōu)先檢索的開始結(jié)點。在深度優(yōu)先生成樹中，結(jié)點。在深度優(yōu)先生成樹中， u u若有父親，那末若有父親，那末v v就是它的父親。假設(shè)數(shù)組

56、就是它的父親。假設(shè)數(shù)組DFNDFN是全程量，并將其初始化為是全程量，并將其初始化為0 0。numnum是全程變是全程變量，被初始化為量，被初始化為 1 1。n n是是 G G的結(jié)點數(shù)的結(jié)點數(shù)算法如下：算法如下： int DFNn，Ln，num=1，n；TRY（u，v）DFNu=num；Lu=num；num=num1；while （每個鄰接于（每個鄰接于u的結(jié)點的結(jié)點 w ） if （DFN（w）=0） TRY（w，u）；）； if(L（u）L（w）L（u）=L（w）；）； else if （wv） if (L（u）DFN（w）) L（u）= DFN（w）；）； 算法說明：算法說明： 算法算法A

57、RTART實現(xiàn)了對圖實現(xiàn)了對圖G G的深度優(yōu)先檢索；在的深度優(yōu)先檢索；在檢索期間，對每個新訪問的結(jié)點賦予深度優(yōu)先數(shù)；檢索期間，對每個新訪問的結(jié)點賦予深度優(yōu)先數(shù)；同時對這棵樹中每個結(jié)點的同時對這棵樹中每個結(jié)點的L L（i i）值也進行計算。）值也進行計算。 如果連通圖如果連通圖G G有有n n個結(jié)點個結(jié)點e e條邊，且條邊，且G G由鄰接由鄰接表表示，那末表表示，那末ARTART的計算時間為的計算時間為O O（n ne e）。識別）。識別關(guān)結(jié)點的總時間不超過關(guān)結(jié)點的總時間不超過O O（n ne e）。）。3 3非重連通圖的加邊策略非重連通圖的加邊策略q G=( V, E )G=( V, E )是

58、是G G的最大重連通子圖，指的的最大重連通子圖，指的是是G G中再沒有這樣的重連通子圖中再沒有這樣的重連通子圖G=( V, G=( V, E )E )存在，使得存在，使得VVVV且且EEEE。q 最大重連通子圖稱為重連通分圖最大重連通子圖稱為重連通分圖 使用這個方法將圖使用這個方法將圖5-65-6變成重連通圖，需要變成重連通圖，需要對應(yīng)于關(guān)結(jié)點對應(yīng)于關(guān)結(jié)點3 3增加邊（增加邊（4 4，1010）和（）和（1010，9 9）；）；對應(yīng)關(guān)結(jié)點對應(yīng)關(guān)結(jié)點2 2增加邊（增加邊（1 1，5 5）；對應(yīng)關(guān)結(jié)點）；對應(yīng)關(guān)結(jié)點5 5增加增加（6 6，7 7），結(jié)果如圖），結(jié)果如圖5-115-11。 圖5-11

59、 (圖5-6改進為重連通圖）54 回回 溯溯 法法 回溯算法實際是一個類似枚舉的搜索嘗試方法，它的回溯算法實際是一個類似枚舉的搜索嘗試方法，它的主題思想是在搜索嘗試中找問題的解，當不滿足求解條件主題思想是在搜索嘗試中找問題的解，當不滿足求解條件就就”回溯回溯”返回，嘗試別的路徑?；厮菟惴ㄊ菄L試搜索算返回，嘗試別的路徑。回溯算法是嘗試搜索算法中最為基本的一種算法，其采用了一種法中最為基本的一種算法，其采用了一種“走不通就掉頭走不通就掉頭”的思想，作為其控制結(jié)構(gòu)。的思想，作為其控制結(jié)構(gòu)。541 認識回溯法【例【例1 1】八皇后問題模型建立】八皇后問題模型建立 要在要在8 8* *8 8的國際象棋棋

60、盤中放八個皇后，使任的國際象棋棋盤中放八個皇后，使任意兩個皇后都不能互相吃掉。規(guī)則：皇后能吃掉同意兩個皇后都不能互相吃掉。規(guī)則：皇后能吃掉同一行、同一列、同一對角線的任意棋子。如圖一行、同一列、同一對角線的任意棋子。如圖5-125-12為一種方案，求所有的解。為一種方案，求所有的解。 模型建立模型建立 不妨設(shè)八個皇后為不妨設(shè)八個皇后為x xi i，她們分別在第，她們分別在第i i行（行（i=1i=1，2 2，3 3，44，8 8），這樣問題的解空間，就是一個），這樣問題的解空間，就是一個八個皇后所在列的序號，為八個皇后所在列的序號，為n n元一維向量（元一維向量（x x1 1,x,x2 2,x