原文鏈接:http://helloitworks.com/678.html?utm_source=tuicool&utm_medium=referral
一胳螟、深度優(yōu)先搜索
深度優(yōu)先搜索算法(Depth First Search)糖耸，是圖論中的經(jīng)典算法丘薛。深度優(yōu)先搜索算法是沿著樹(shù)的深度遍歷樹(shù)的節(jié)點(diǎn)洋侨，盡可能深的搜索樹(shù)的分支。當(dāng)結(jié)點(diǎn)所有子結(jié)點(diǎn)那一層都被搜索過(guò)边苹，再回溯返回到當(dāng)前結(jié)點(diǎn)的鄰結(jié)點(diǎn)个束，繼續(xù)搜索聊疲，直到遍歷完整棵樹(shù)售睹。一般采用的是前序遍歷可训，先根然后再左右結(jié)點(diǎn)的方式進(jìn)行握截。一些經(jīng)典的問(wèn)題，比如八皇后固歪、馬走日牢裳、迷宮等叶沛，都可以通過(guò)深度優(yōu)先搜索算法來(lái)解決灰署。為了方便描述局嘁，下文用DFS來(lái)做為深度優(yōu)先搜索算法的簡(jiǎn)稱(chēng)悦昵。
二晌畅、我對(duì)DFS的認(rèn)識(shí)對(duì)于DFS踩麦，我相信很多人第一次接觸很難設(shè)計(jì)出相應(yīng)的算法，即便是有不錯(cuò)的編程經(jīng)驗(yàn)贫橙。我第一次幾乎沒(méi)辦法設(shè)計(jì)出解決八皇后的算法卢肃，即便是想了很久才顿。最后沒(méi)辦法只好參照別人寫(xiě)的遞歸式的DFS郑气。之后，雖然對(duì)這個(gè)算法有一點(diǎn)了解忙芒，但由于了解不夠深度呵萨，過(guò)了幾天就記不得了跨跨，下次又完全不知道怎么入手勇婴。然后需要再到網(wǎng)上搜下代碼，看一遍后大概才雙知道德谅。而且發(fā)現(xiàn)每次寫(xiě)代碼的時(shí)候心里總覺(jué)得不踏實(shí)窄做，一開(kāi)始總有錯(cuò)誤的地方，并且每次寫(xiě)的代碼都有些不同组砚√图眨總之乌叶，寫(xiě)過(guò)很多次后准浴，依然是停留到了解的階段，沒(méi)辦法進(jìn)一步提升求橄，特別是非遞歸式的DFS一直都停留到靠腦力記憶而不是理解的階段罐农。
今天周末有點(diǎn)時(shí)間催什，覺(jué)得有必要解決這些問(wèn)題蒲凶，試著花時(shí)間去歸納總結(jié)DFS的本質(zhì)，看能否做到一勞永逸裆悄。我設(shè)定的目標(biāo)是：1、不僅停留到理解階段孩等，而是要知道這個(gè)算法每一步的實(shí)現(xiàn)2采够、捉住其中的本質(zhì)蹬癌，給出這個(gè)算法的設(shè)計(jì)框架。3隅要、在1與2的基礎(chǔ)中步清，可以熟練寫(xiě)出遞歸與非遞歸兩種實(shí)現(xiàn)方式 廓啊。
經(jīng)過(guò)一個(gè)下午的研究，我發(fā)現(xiàn)任何DFS只需要通過(guò)下面幾步就可以實(shí)現(xiàn)炒瘟，無(wú)論是遞歸還是非遞歸方式唧领。我給這幾步分別做了一個(gè)命名雌续，分別是find驯杜、forward鸽心、done、back藤肢。如下：1嘁圈、find(right):在樹(shù)的當(dāng)前層蟀淮，橫向遍歷怠惶，嘗試找到ok的節(jié)點(diǎn)策治。（這一步通常被叫做剪枝兰吟，只留下ok的揽祥。）2拄丰、forward(down):若在當(dāng)前層找到ok的結(jié)點(diǎn)俐末，并且當(dāng)前層不是最后一層:把ok的節(jié)點(diǎn)放到當(dāng)前層卓箫；進(jìn)入下一層第一個(gè)結(jié)點(diǎn)烹卒。跳到find3旅急、done(right):若在當(dāng)前層找到ok的結(jié)點(diǎn)，并且當(dāng)前層是最后一層：打印出結(jié)果溺拱；進(jìn)入當(dāng)前層的下一個(gè)結(jié)點(diǎn)迫摔。跳到find4句占、back(up):在當(dāng)前層沒(méi)有找到ok的節(jié)點(diǎn)：返回上一層當(dāng)前結(jié)點(diǎn)的下一個(gè)兄弟節(jié)點(diǎn)躯嫉。跳到find
其實(shí)最重要的是find和敬。然后后面的forward昼弟、done舱痘、back只是用來(lái)控制搜索走向。這四步可以進(jìn)一步總結(jié)成兩步塌碌。為了了解算法台妆，我想最好的切入方式是從一些實(shí)例開(kāi)始接剩。下面分別從八皇后以及馬走日等問(wèn)題做為切入點(diǎn)來(lái)分析DFS
三萨咳、用DFS解八皇后
1培他、問(wèn)題描述八皇后問(wèn)題是一個(gè)以國(guó)際象棋為背景的問(wèn)題：如何能夠在8×8 的國(guó)際象棋棋盤(pán)上放置八個(gè)皇后舀凛，使得任何一個(gè)皇后都無(wú)法直接吃掉其他的皇后猛遍？也就是說(shuō)螃壤，使得棋盤(pán)中每個(gè)橫向、縱向冤馏、左上至右下斜向逮光、右上至左下斜向均只有一枚皇后涕刚。八皇后有92組解杜漠，下面給出其中一種解的圖例：
2驾茴、 問(wèn)題分析
規(guī)則是每一個(gè)皇后與前面的所有皇后不能在同一行锈至、同一列、同一對(duì)角線击碗。我們可以從第0行延都，第0列開(kāi)始擺放晰房，然后按照深度優(yōu)先的原則殊者，按照規(guī)則往更下面的行擺放皇后验夯，直到擺放完8行挥转。因?yàn)榻獠恢灰粋€(gè)绑谣，當(dāng)某一行（包括最后一行跟最后一行之前的所有行）的所有列都被嘗試過(guò)，再回溯返回到上一行借宵，繼續(xù)深度優(yōu)先幌衣，直到遍歷完整個(gè)棋盤(pán)的所有情況。得出所有的解壤玫。八皇后問(wèn)題可以看成是在深度為8的8叉樹(shù)中豁护，找出所有的解。
3欲间、代碼實(shí)現(xiàn)
遞歸算法：
#include <stdio.h>
#include <math.h>
/*八皇后問(wèn)題是在8*8的棋盤(pán)上放置8枚皇后楚里，使得棋盤(pán)中每個(gè)橫向、縱向猎贴、左上至右下斜向蝴光、右上至左下斜向均只有一枚皇后。
求解出所有擺法,一共有92種擺法*/
const int N = 8; //棋盤(pán)行數(shù)
int a[N] = {0}; //表示棋盤(pán)吝梅，若a[2]=2,則表示在第3行第2列放一個(gè)皇后，因?yàn)橥恍胁荒芊艃蓚€(gè)皇后惹骂，所以只需要1維數(shù)組就可以表示一個(gè)棋盤(pán)苏携。
int solution = 0;//解的個(gè)數(shù)
//row行，col列, 是否可以擺皇后
bool IsOK(int row, int col)
{
for (int i = 0; i < row; i++)
{
if (a[i] == col || (abs(a[i] - col) == row - i))
{
return false;
}
}
return true;
}
void Display()
{
printf("第%d種解：\n",++solution);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (a[i] == j)
{
printf("%d", i);
}
else
{
printf("#");
}
}
printf("\n");
}
printf("-----------------\n");
}
void DSF(int row)
{
for (int col = 0; col < N; col++)
{
//find
if (IsOK(row, col))
{
a[row] = col;
//forward
if (row != N -1)
{
DSF(row + 1);
}
else
{
//done
Display();
}
}
}
//back
}
int main()
{
DSF(0);
return 0;
}
非遞歸算法：
#include <stdio.h>
#include <math.h>
#include <stack>
using namespace std;
/*八皇后問(wèn)題是在8*8的棋盤(pán)上放置8枚皇后对粪，使得棋盤(pán)中每個(gè)橫向右冻、縱向、左上至右下斜向著拭、右上至左下斜向均只有一枚皇后*/
const int N = 8; //棋盤(pán)行數(shù)
int a[N] = {0}; //表示棋盤(pán)纱扭，若a[2]=2,則表示在第3行第2列放一個(gè)皇后，因?yàn)橥恍胁荒芊艃蓚€(gè)皇后儡遮，所以只需要1維數(shù)組就可以表示一個(gè)棋盤(pán)乳蛾。
int solution = 0;//解的個(gè)數(shù)
struct Node
{
int row;
int col;
};
//row行，col列, 是否可以擺皇后
bool IsOK(Node node)
{
for (int i = 0; i < node.row; i++)
{
if (a[i] == node.col || (abs(a[i] - node.col) == node.row - i))
{
return false;
}
}
return true;
}
//打印出所有解
void Print()
{
printf("第%d種解：\n", ++solution);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
if (a[i] == j)
{
printf("%d", i);
}
else
{
printf("#");
}
}
printf("\n");
}
printf("-----------------\n");
}
void DSF()
{
Node node;
stack stack;
node.row = 0;
node.col = 0;
stack.push(node);
while(stack.size() >= 1)
{
//--find
node = stack.top();
while (node.col < N && !IsOK(node))
{
node.col++;
}
if (node.col < N)
{
//--forward
if (node.row < N-1)
{
//把ok的節(jié)點(diǎn)放到當(dāng)前層
a[node.row] = node.col;
stack.pop();
stack.push(node);
//進(jìn)入下一層的第一個(gè)節(jié)點(diǎn)
node.row++;
node.col = 0;
stack.push(node);
}
else
{
//--done
a[node.row] = node.col;
Print();
//進(jìn)入當(dāng)前層的下一個(gè)結(jié)點(diǎn)
//node = stack.top();
node.col++;
stack.pop();
stack.push(node);
}
}
else
{
//--back
stack.pop();
if (stack.size() == 0)
{
return;
}
node = stack.top();
node.col++;
stack.pop();
stack.push(node);
}
}
}
int main()
{
DSF();
return 0;
}
三鄙币、馬走日
1肃叶、問(wèn)題描述在nn的棋盤(pán)中，馬只能走"日"字十嘿。馬從位置(0,0)出發(fā)因惭，把棋盤(pán)的每一格都走一次且只走一次。找出所有路徑绩衷。 55的棋盤(pán)上蹦魔，有304種解。下面是其中一種路徑的圖例：
2咳燕、問(wèn)題分析搜索過(guò)程是從(0,0)出發(fā)勿决，按照深度優(yōu)先的原則，從8個(gè)方向中嘗試一個(gè)可以走的點(diǎn)招盲，直到嘗試過(guò)所有的方向剥险，走完棋盤(pán)上的所有點(diǎn)，得出所有的解宪肖。馬走日問(wèn)題可以看成是在層數(shù)為n*n的8叉樹(shù)中表制，找出所有的解。
3控乾、代碼實(shí)現(xiàn)同樣的么介，也可以把上面的算法框架，套用于馬走日的身上蜕衡。遞歸算法：
#include <stdio.h>
/*馬走日*/
const int N = 5; //棋盤(pán)行數(shù)跟列數(shù)
int matrix[N][N] = {0}; //表示棋盤(pán)
int solution = 0;//解的個(gè)數(shù)
int count = 0; //第幾步
int move[8][2]={{-1,-2},{-2,-1}, {-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};//八個(gè)方向
//在棋盤(pán)范圍內(nèi)壤短，而且可放棋
bool IsOK(int x, int y)
{
if(( x <= N-1 ) && (x >=0 )
&& (y <= N-1 ) && (y >=0 )
&& (matrix[x ][y ]==0 ))
{
return true;
}
else
{
return false;
}
}
//打印出所有解
void Display()
{
printf("第%d種解：\n",++solution);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
printf("%3d",matrix[i][j]);
}
printf("\n");
}
printf("-----------------\n");
}
void DFS(int x, int y)
{
int nextX, nextY;
for (int i = 0; i < 8; i++)
{
nextX = x + move[i][0];
nextY = y + move[i][1];
//--find
if (IsOK(nextX, nextY))
{
if (count != N*N -1 )
{
//--forward
count++;
matrix[nextX][nextY] = count;
DFS(nextX, nextY);
matrix[nextX][nextY] = 0;
count--;
}
else
{
//--done
Display();
}
}
}
//--back
}
int main()
{
matrix[0][0] = 1;
count = 1;
DFS(0, 0);
return 0;
}
非遞歸算法：
#include <stdio.h>
#include <stack>
using namespace std;
/*馬走日*/
const int N = 5; //棋盤(pán)行數(shù)跟列數(shù)
int matrix[N][N] = {0}; //表示棋盤(pán)
int solution = 0;//解的個(gè)數(shù)
int count = 0; //第幾步
int move[8][2]={{-1,-2},{-2,-1}, {-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}};//八個(gè)方向
//注意find這一步當(dāng)前層的的結(jié)點(diǎn)，結(jié)點(diǎn)的坐標(biāo)不是x與y，而通過(guò)Node中的x與y與direction三者計(jì)算后得到當(dāng)前層的結(jié)點(diǎn)
struct Node
{
int x;
int y;
int direction;
};
//在棋盤(pán)范圍內(nèi)久脯，而且可放棋
bool IsOk(Node node)
{
int x, y;
x = node.x + move[node.direction][0];
y = node.y + move[node.direction][1];
if(( x <= N-1 ) && (x >=0 )
&& (y <= N-1 ) && (y >=0 )
&& (matrix[x][y]==0 ))
{
return true;
}
else
{
return false;
}
}
//打印
void Print()
{
printf("第%d種解：\n",++solution);
for (int i = 0; i < N; i++)
{
for (int j = 0; j < N; j++)
{
printf("%3d",matrix[i][j]);
}
printf("\n");
}
printf("-----------------\n");
}
void DFS()
{
Node node;
stack stack;
int x, y;
count = 1;
node.x = 0;
node.y = 0;
node.direction = 0;
matrix[0][0] = count++;
stack.push(node);
node.direction = 0;
stack.push(node);
while(stack.size() >= 2)
{
//--find
node = stack.top();
while (node.direction < 8 && !IsOk(node))
{
node.direction++;
}
if (node.direction < 8)
{
//--forward
if (count < N * N)
{
//把ok的節(jié)點(diǎn)放到當(dāng)前層
stack.pop();
stack.push(node);
x = node.x + move[node.direction][0];
y = node.y + move[node.direction][1];
matrix[x][y] = count++;
//進(jìn)入下一層的第一個(gè)節(jié)點(diǎn)
node.x = x;
node.y = y;
node.direction = 0;
stack.push(node);
}
else
{
//--done
//打印出結(jié)果;
x = node.x + move[node.direction][0];
y = node.y + move[node.direction][1];
matrix[x][y] = count++;
Print();
//注意先清除當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)
matrix[x][y] = 0;
count--;
//進(jìn)入當(dāng)前層的下一個(gè)結(jié)點(diǎn);
node.direction++;
stack.pop();
stack.push(node);
}
}
else
{
//----back
//返回上一層當(dāng)前結(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
stack.pop();
if (stack.size() == 1)
{
return;
}
node = stack.top();
//注意先清除當(dāng)前結(jié)點(diǎn)的數(shù)據(jù)
x = node.x + move[node.direction][0];
y = node.y + move[node.direction][1];
matrix[x][y] = 0;
count--;
node.direction++;
stack.pop();
stack.push(node);
}
}
}
int main()
{
DFS();
return 0;
}
四纳胧、DFS有更多的變種，但都可以通過(guò)上面所說(shuō)的四個(gè)步驟云解決帘撰。未完跑慕，待續(xù)。摧找。核行。。
五蹬耘、代碼：https://github.com/helloitworks/algorithm/tree/master/dfs
