算法一：深度优先搜索
1.1、图的表示方法
1.1.1、图的表示方法 --- 邻接矩阵
用一个二维数组G存放图，G[i][j]表示节点i和j之间边的情况（如有无边，边方向，权值大小等）
遍历复杂度：O(n^2) n为节点数目
1.1.2、 图的表示方法 --- 邻接表
每个节点V对应一个一维数据(vector)，里面存放从V连出去的边，边的信息包括另一顶点，还可能包含边的权值等；
原图
使用邻接表的表示
遍历复杂度：O(n+e) n为节点数目，e为边数目；
在边稀疏的情况下，邻接表的效率比邻接矩阵效率高。
1.2、深度优先搜索思路
从起点出发，走过的点要做标记，发现有没有走过的点，就随意挑一个往前走，走不了就回退，此种路径搜索策略就称为“深度优先搜索”。所谓深度，就是以距离起点的步数来衡量的；按目的可以分为以下3种情况。
1.2.1、判断从V出发是否能走到终点
思路如下：
bool Dfs()
{
if(v 为终点)
return true;
if(v 为旧点)
return false;
将v标记为旧点；
对和v相邻的每个节点u {
if(Dfs(U) == true)
return true;
}
return false;
}
int main()
{
将所有点都标记为新点
设置起点
设置终点
cout<<Dfs(起点)；
}
1.2.2、判断从V出发是否能走到终点,如果能，要记录路径
Node path[MAX_LEN]; //MAX_LEN取节点总数即可，用来记录路径
int depth;
bool Dfs()
{
if(v 为终点) {
path[depth] = V;
return true;
}
if(v 为旧点) {
return false;
}
将v标记为旧点；
path[depth] = V;
depth++;
对和v相邻的每个节点u {
if(Dfs(U) == true)
return true;
}
depth--;
return false;
}
int main()
{
将所有点都标记为新点
设置起点
设置终点
depth = 0;
if(Dfs(起点)) {
for(int i = 0; i <= depth; I++)
cout << path[i] << endl;
}
}
1.2.3、遍历图上所有节点
bool Dfs()
{
if(v 为旧点)
return;
将v标记为旧点；
对和v相邻的每个节点u {
Dfs(U);
}
int main()
{
将所有点都标记为新点
while(在图中能找到的新点k)
Dfs(k);
}
1.3、深度优先搜索例题
/*
右图是一个城堡的地形图 。请你编写一个程序，计算城堡一共有多少房间， 最大的房间有多大。 城堡被分割成m×n(m≤50，n≤50)个方块，每个方块可以有0~4面墙。
解题思路：
建模：
可以将城堡的地形图转化成一个无向图，每个房间是图中的一个节点，相邻两个房间之间如果没有墙，则在房间之间有一条边；
这样，求房间的个数就转换成了求图中有多少个极大连通子图；
什么事极大连通子图：对于一个连通子图，往里头加任何一个图里的其他节点，就会变得不连通，那么这个连通子图就是极大连通子图；
对每一个房间，深度优先搜索，从而给这个房间能够到达的所有位置标记。最后统计一共用了几种记号，以及每种记号的数量；
*/
int rawNum = 0, colNum = 0;
int rooms[60][60];
int visited[60][60];
int roomNum = 0, maxRoomArea = 0, roomArea = 0;
void Dfs(int i, int j)
{
if(visited[i][j]) {
return;
}
roomArea++;
visited[i][j] = roomNum;
if((rooms[i][j] & 1) == 0) {
Dfs(i,j-1);
}
if((rooms[i][j] & 2) == 0) {
Dfs(i-1,j);
}
if((rooms[i][j] & 4) == 0) {
Dfs(i,j+1);
}
if((rooms[i][j] & 8) == 0) {
Dfs(i+1,j);
}
}
int main(int argc, const char * argv[]) {
cin >> rawNum >> colNum;
for(int i = 1; i <= rawNum; i++) {
for(int j = 1; j <= colNum; j++) {
cin >> rooms[i][j];
}
}
memset(visited,0,sizeof(visited));
for(int i = 1; i <= rawNum; i++) {
for(int j = 1; j <= colNum; j++) {
if(!visited[i][j]) {
roomNum++;
roomArea = 0;
Dfs(i,j);
maxRoomArea = max(roomArea, maxRoomArea);
}
}
}
cout << roomNum << endl;
cout << maxRoomArea << endl;
return 0;
}
/*
踩方格
题目描述：有一个方格矩阵，矩阵边界在无穷远处。我们做如下假设:
a.每走一步时，只能从当前方格移动一格，走到某个相邻的方格上; b. 走过的格子立即塌陷无法再走第二次;
c. 只能向北、东、西三个方向走;
请问:如果允许在方格矩阵上走n步(n<=20)，共有多少种不同的方案。 2种走法只要有一步不一样，即被认为是不同的方案。
思路：
递归
从(i,j)出发，走n步的方案数，等于一下三项之和：
从(i+1,j)出发，走n-1步的方案数。前提：(i+1,j)还没走过；
从(i,j+1)出发，走n-1步的方案数。前提：(i,j+1)还没走过；
从(i,j-1)出发，走n-1步的方案数。前提：(i,j-1)还没走过；
*/
//int visited[30][50];
int ways(int i, int j, int n)
{
if(n == 0) {
return 1;
}
visited[i][j] = 1;
int num = 0;
if(visited[i][j-1] == 0) {
num+= ways(i,j-1,n-1);
}
if(visited[i][j+1] == 0) {
num+= ways(i,j+1,n-1);
}
if(visited[i+1][j] == 0) {
num+= ways(i+1,j,n-1);
}
visited[i][j] = 0; //这里在尝试完从i, j出发后需要将其恢复为可以访问的状态，这样在尝试从其他点开始的时候，还是可以访问i, j点的。
return num;
}
int main(int argc, const char * argv[]) {
int n;
cin >> n;
memset(visited,0,sizeof(visited));
cout << ways(0,25,n) << endl;
return 0;
}
/*
ROADS
N个城市，编号1到N。城市间有R条单向道路。 每条道路连接两个城市，有长度和过路费两个属性。Bob只有K块钱，他想从城市1走到城市N。问最短共需要走多长的路。如果到不了N，输出-1
2<=N<=100
0<=K<=10000
1<=R<=10000 每条路的长度 L, 1 <= L <= 100每条路的过路费T , 0 <= T <= 100
思路：
从城市1开始遍历整个图，找到所有能到达N的走法，选最优的一个；这里参考深
*/
int K,N,R; //K：bob拥有的钱，N：城市数量，R：路的数量
struct Road {
int d; //目的城市
int l; //路的长度
int t; //过路费
};
int minLen;
int totalCost;
int totalLen;
int visited[110];
vector<vector<Road> > G(100);
void dfs(int s)
{
if(s == N) {
minLen = min(minLen, totalLen);
return;
}
for(int i = 0; i < G[s].size(); i++) {
Road r = G[s][I];
if(totalCost + r.t > K) { //可行性剪枝
continue;
}
if(totalLen + r.l > minLen) { //最优性剪枝
continue;
}
if(!visited[r.d]) {
totalLen += r.l;
totalCost += r.t;
visited[r.d] = 1;
dfs(r.d);
totalLen -= r.l;
totalCost -= r.t;
visited[r.d] = 0;
}
}
}
int main()
{
cin >> K >> N >> R;
for(int i = 0; i < R; i++) {
int n;
Road r;
cin >> n >> r.d >> r.l >> r.t;
if(n != r.d) {
G[n].push_back(r);
}
}
memset(visited, 0, sizeof(visited));
totalLen = 0;
minLen = 1 << 30;
totalCost = 0;
visited[1] = 1;
dfs(1);
if(minLen < (1 << 30)) {
cout << minLen << endl;
}
else {
cout << "-1" << endl;
}
return 0;
}
算法二：广度优先搜索
1.1、算法思路
广度优先搜索算法如下:(用QUEUE)
(1) 把初始节点S0放入Open表中;
(2) 如果Open表为空，则问题无解，失败 退出;
(3) 把Open表的第一个节点取出放入 Closed表，并记该节点为n;
(4) 考察节点n是否为目标节点。若是，则 得到问题的解，成功退出;
(5) 若节点n不可扩展，则转第(2)步;
(6) 扩展节点n，将其不在Closed表和 Open表中的子节点(判重)放入Open表的尾 部，并为每一个子节点设置指向父节点的指针 (或记录节点的层次)，然后转第(2)步。
广度优先算法流程图
2.2、广度优先搜索例题
/*
八数码问题：
有一个3*3的棋盘，其中有0-8共9个数字，0表示空格， 其他的数字可以和0交换位置。求由初始状态 到达目标状态的步数最少的解。
8 2 3 1 2 3
1 4 6 --> 4 5 6
5 7 0 7 8 0
广度优先搜索：
1、用队列保存待扩展的节点
2、从队列队首取出节点，扩展出的新节点放入队尾，直到队首出现目标节点，即问题的解
3、关键问题：判重：新扩展出的节点如果和以前扩展出的节点相同，则这个新节点就不必再考虑；
这里存在的问题是状态节点数据众多，如何存储？以及怎样才能较快的判断一个状态是否是重复？
*/
int goalStatus = 123456780; //目标状态
const int MAXS = 400000;
char result[MAXS]; //要输出的移动方案
struct Node {
int status; //状态
int father; //父节点指针，即myQueue的下标
char move; //父节点到本节点的移动方式 u/d/r/l
Node(int s,int f,char m):status(s), father(f),move(m) { } Node() { }
};
Node myQueue[MAXS]; //状态队列，状态总数362880
int qHead = 0; //队头指针
int qTail = 1; //队尾指针
char moves[] = "udrl"; //四种移动
//求从status经过 move 移动后得到的新状态。若移动不可行则返回-1
int NewStatus( int status, char move)
{
char tmp[20];
int zeroPos; //字符'0'的位置
sprintf(tmp,"%09d",status); //需要保留前导0
for( int i = 0;i < 9; ++ I )
{
if(tmp[i] == '0') {
zeroPos = I;
break;
} //返回空格的位置
}
switch(move) {
case 'u':
if(zeroPos - 3 < 0 ) {
return -1; //空格在第一行
} else {
tmp[zeroPos] = tmp[zeroPos - 3];
tmp[zeroPos - 3] = '0';
}
break;
case 'd':
if(zeroPos + 3 > 8 ) {
return -1; //空格在第三行
} else {
tmp[zeroPos] = tmp[zeroPos + 3];
tmp[zeroPos + 3] = '0';
}
break;
case 'l':
if(zeroPos % 3 == 0 ) {
return -1; //空格在第一行
} else {
tmp[zeroPos] = tmp[zeroPos - 1];
tmp[zeroPos - 1] = '0';
}
break;
case 'r':
if(zeroPos % 3 == 2) {
return -1; //空格在第三列
} else {
tmp[zeroPos] = tmp[zeroPos + 1];
tmp[zeroPos + 1 ] = '0';
}
break;
}
return atoi(tmp);
}
//寻找从初始状态status到目标的路径，找不到则返回false
bool Bfs(int status)
{
int newStatus;
set<int> expanded;
myQueue[qHead] = Node(status,-1,0);
expanded.insert(status);
while(qHead != qTail) { //队列不为空
status = myQueue[qHead].status;
if(status == goalStatus) //找到目标状态
return true;
for(int i = 0; i < 4; i ++ ) { //尝试4种移动
newStatus = NewStatus(status,moves[I]);
if(newStatus == -1)
continue; //不可移，试下一种
if(expanded.find(newStatus)!=expanded.end())
continue; //已扩展过，试下一种
expanded.insert(newStatus);
myQueue[qTail++] = Node(newStatus,qHead,moves[i]); //新节点入队列
}
qHead ++;
}
return false;
}
int main()
{
char line1[50];
char line2[20];
while( cin.getline(line1, 48)) {
int i, j;
for(i = 0, j = 0; line1[i]; i++) {
if(line1[i] != ' ') {
if(line1[i] == 'x') {
line2[j++] = '0';
} else {
line2[j++] = line1[I];
}
}
}
line2[j] = 0;
if(Bfs(atoi(line2))) {
int moves = 0;
int pos = qHead;
do {
result[moves++] = myQueue[pos].move;
pos = myQueue[pos].father;
} while(pos);
for(int i = moves - 1; i >= 0; i--) {
cout << result[I];
}
} else {
cout << "unsolvable" << endl;
}
}
}
总结
- 广度搜索一般用于状态表示比较简单、求最优策略的问题
- 优点：是一种完备策略，即只要问题有解，它就一定可以找到解。并且，广度优先搜索找到的解，还一定是路径最短的解。
- 缺点：盲目性较大，尤其是当目标点距初始节点较远时，将产生许多无用的节点，因此其搜索效率较低。需要保存所有扩展出的状态，占用的空间大。
- 用队列存节点: FIFO
- 深度搜索几乎可以用于任何问题
- 只需要保存从起始状态到当前状态路径上的节点
- 用栈存节点：LIFO
