搜索
DFS(深搜)
方法
- 从某一初始出发点i开始访问:
- 输出改点编号
- 对该点作被访问标志(以免被重复访问)
- 从i的其中一个未被访问的邻接点j作为初始出发继续深搜
当i的所有邻接点都被访问完,则返回到i的父结点的另一个邻接点k再继续深搜。直到全部结点访问完毕。
原则:能向前(指当前结点的下一层结点)走,就走。不能走就后退一步再选择可行点。
实现
//DFS
int maxn = 100;
int a[maxn][maxn];//建立一个二维数组,表示各结点间有无边 定义在全局里初始都为0
bool vis[maxn];//记录每个结点是否被访问过 定义在全局初始为false
int n, m;//n:n个结点 m:m条边
void init()
{
for (int i = 1; i <= m; i++)
{
cin >> x >> y;
a[x][y] = 1;
a[y][x] = 1;
}
}
void dfs(int i)
{
cout << i << " ";
vis[i] = true;
for (int j = 1; j <= n; j++)
{
if (a[i][j] == 1 && !vis[j])
dfs[j];
}
}
int main()
{
init();
dfs();
return 0;
}
BFS(广搜)
方法
- 从图中某结点 出发
- 在访问了 之后依次访问 的各个未曾访问的邻接点
- 分别从这些邻接点出发按广度优先搜索的顺序遍历图
- 直至图中所有可被访问的结点都被访问到
原则:以层
为阶段,每一层的所有结点访问完后,再访问下一层的结点
实现
//BFS
int maxn = 100;
int a[maxn][maxn];//建立一个二维数组,表示各结点间有无边 定义在全局里初始都为0
bool vis[maxn];//记录每个结点是否被访问过 定义在全局初始为false
int n, m, k;//n:n个结点 m:m条边
void init()
{
for (int i = 1; i <= m; i++)
{
a[x][y] = 1;
a[y][x] = 1;
}
}
void bfs()
{
int head, tail;
int q[maxn];
memset(q, 0, sizeof(q));
head = 0, tail = 1;//队列初始化 head指向队头元素的前一个位置 tail指向队尾元素所在的位置
q[1] = 1;
vis[1] = true;
while (head < tail) //队列不空
{
head++;//出队列
k = q[head];
cout << k << " ";
for (int j = 1; j <= n; j++)
{
if (a[k][j] == 1 && !vis[j])
{
tail++;
q[tail] = j;
vis[j] = true;
}//if
}//for
}//while
}//bfs
int main()
{
init();
bfs();
return 0;
}
剪枝
可行性剪枝
当前状态和题意不符,并且由于题目可以推出,往后的所有情况和题意都不符,那么就可以进行剪枝,直接把这种情况及后续的所有情况判负,直接返回。
即:不可行,就返回。
排除等效冗余
当几个枝桠具有完全相同的效果的时候,只选择其中一个走就可以了。
即:都可以,选一个。
最优性剪枝
解决最优化问题的时候的一种常用剪枝。就是当你搜到一半的时候,已经比已经搜到的最优解要不优了,那么这个方案肯定是不行的,即刻停止搜索,进行回溯。
即:有比较,选最优。
顺序剪枝
普遍来讲,搜索的顺序是不固定的,对一个问题来讲,算法可以进入搜索树的任意的一个子节点。但假如我们要搜索一个最小值,而非要从最大值存在的那个节点开搜,就可能存在搜索到最后才出解。而我们从最小的节点开搜很可能马上就出解。这就是顺序剪枝的一个应用。一般来讲,有单调性存在的搜索问题可以和贪心思想结合,进行顺序剪枝。
即:有顺序,按题意。
记忆化
记录搜索的每一个状态,当重复搜索到相同的状态的时候直接返回。
即:搜重了,直接跳。