搜索

DFS(深搜)

方法

  1. 从某一初始出发点i开始访问:
  • 输出改点编号
  • 对该点作被访问标志(以免被重复访问)
  1. 从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(广搜)

方法

  • 从图中某结点 ii 出发
  • 在访问了 ii 之后依次访问 ii 的各个未曾访问的邻接点
  • 分别从这些邻接点出发按广度优先搜索的顺序遍历图
  • 直至图中所有可被访问的结点都被访问到

原则:以为阶段,每一层的所有结点访问完后,再访问下一层的结点

实现

//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;
}

剪枝

可行性剪枝

当前状态和题意不符,并且由于题目可以推出,往后的所有情况和题意都不符,那么就可以进行剪枝,直接把这种情况及后续的所有情况判负,直接返回。

即:不可行,就返回。

排除等效冗余

当几个枝桠具有完全相同的效果的时候,只选择其中一个走就可以了。

即:都可以,选一个。

最优性剪枝

解决最优化问题的时候的一种常用剪枝。就是当你搜到一半的时候,已经比已经搜到的最优解要不优了,那么这个方案肯定是不行的,即刻停止搜索,进行回溯。

即:有比较,选最优。

顺序剪枝

普遍来讲,搜索的顺序是不固定的,对一个问题来讲,算法可以进入搜索树的任意的一个子节点。但假如我们要搜索一个最小值,而非要从最大值存在的那个节点开搜,就可能存在搜索到最后才出解。而我们从最小的节点开搜很可能马上就出解。这就是顺序剪枝的一个应用。一般来讲,有单调性存在的搜索问题可以和贪心思想结合,进行顺序剪枝。

即:有顺序,按题意。

记忆化

记录搜索的每一个状态,当重复搜索到相同的状态的时候直接返回。

即:搜重了,直接跳。