窮舉搜索:回溯與深搜

計算機常用算法大致有兩大類，一類叫蠻力算法，一類叫貪心算法，前者常使用的手段就是搜索，對全部解空間進行地毯式搜索，直到找到指定解或最優(yōu)解。

【建立解空間】

問題的解應該如何描述，如何建立？借助圖論的思想，我們可以用圖來描述，圖的定義為G，由頂點集和邊集構成，頂點即實實在在的數(shù) 據(jù)、對象，而邊可以抽象為關系，即頂點間的關系，這種關系不一定非要在數(shù)據(jù)結構上表現(xiàn)出來，用數(shù)據(jù)結構的語言來描述，如果關系是一對一，則為線性表，如果 關系是一對多，則為樹，如果關系是多對多，則為圖，如果完全沒有關系，則為集合。但在數(shù)據(jù)結構中這種關系不一定非要在數(shù)據(jù)的存儲性質上一開始就表現(xiàn)出來， 譬如，你可以用一個數(shù)組表示一個線性表，也可以表示完全二叉樹，同樣也可以用鄰接表表示一個圖，對于關系的描述不是數(shù)據(jù)結構本身的描述，而是算法的描述， 正如數(shù)據(jù)結構是離不開特定的算法一樣，不可分開單獨而談。描述了解，那如何建立解空間，即如何對圖進行搜索？

【深度優(yōu)先搜索】

(Depth First Search)是用棧的機制對圖的頂點進行深度優(yōu)先的搜索。簡易流程如下：

DFS(V0（起始頂點）)

訪問V0

for(v=V0的第一個子結點 到 最后一個子結點（邊所對的頂點））

如果v未被訪問，DFS(v);

搜索過程是先往結點深處搜索，一旦有子結點未訪問就向下遍歷。這樣的方法類似回溯算法，先往下試探，如果不行出退回（回溯）。

【回溯】

回溯的經典例子是8皇后問題。

例：在國際象棋地圖上（8×8）放上8個皇后，使任意兩個皇后都不在同一行或同一列或同一斜行，找出所有解。

每一個皇后的位置可以認為是一個頂點，而皇后之間不在同一行或同一列或同一斜行的性質認為是頂點之間的關系，我們可以用回溯試探的方法考慮：先依次試探每一個皇后的位置，如果有不滿足條件的情況則退回，直到完成所有解的計數(shù)和輸出。

用數(shù)組存儲：int pos[8];

pos[0]表示第一個皇后的位置（0,1,…7)依次類推。

流程：

dfs(c)//c從0開始

for(v=0;v<8;++v)

如果pos[c]:=v滿足條件，dfs(c+1);

退回之后pos[c]:=0;

這跟書上的回溯算法不太一樣，因為是采用深搜的方法寫的，其實思想是一致的，要仔細體會。

八皇后問題 回溯法

問題描述：

八皇后問題是十九世紀著名數(shù)學家高斯于1850年提出的。問題是：在8*8的棋盤上擺放8個皇后，使其不能互相攻擊，即任意的兩個皇后不能處在同意行，同一列，或同意斜線上?？梢园寻嘶屎髥栴}拓展為n皇后問題，即在n*n的棋盤上擺放n個皇后，使其任意兩個皇后都不能處于同一行、同一列或同一斜線上。

問題分析 ：

顯然，每一行可以而且必須放一個皇后，所以n皇后問題的解可以用一個n元向量X=（x1,x2,…..xn）表示，其中，1≤ i≤ n且1≤ xi≤ n，即第n個皇后放在第i行第xi列上。

由于兩個皇后不能放在同一列上，所以，解向量X必須滿足的約束條件為:

xi≠ xj;

若兩個皇后的擺放位置分別是（i,xi）和（j,xj），在棋盤上斜率為-1的斜線上，滿足條件i-j=xi-xj;在棋盤上斜率為1的斜線上，滿足條件i+j=xi+xj;

綜合兩種情況，由于兩個皇后不能位于同一斜線上，所以，

解向量X必須滿足的約束條件為:

|i-xi|≠ |j-xj|

代碼如下：

#include #include int x[100]; bool place(int k)//考察皇后k放置在x[k]列是否發(fā)生沖突 { int i; for(i=1;i=1) { x[k]=x[k]+1; //在下一列放置第k個皇后 while(x[k]<=n&&!place(k)) x[k]=x[k]+1;//搜索下一列 if(x[k]<=n&&k==n)//得到一個輸出 { for(i=1;i<=n;i++) printf("%d ",x[i]); printf("\n"); //return;//若return則只求出其中一種解，若不return則可以繼續(xù)回溯，求出全部的可能的解 } else if(x[k]<=n&&k

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

數(shù)據(jù)結構

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實的內容，請聯(lián)系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。