C语言-深度优先搜索(DFS)

发布于 / 数据结构与算法 / Comments Off on C语言-深度优先搜索(DFS)

0x00、从迷宫说起

    假设你现在处于一个这样的巨大的迷宫中,没有通讯工具,没有上帝视角,无法激活巴拉拉正能量,只能靠自己,从红色的脚印走到绿色的脚印,你会怎么走?

相信你的答案一定是正确的。在没有地图的情况下,走出去的最好的方式一定是:在1点,始终保持右手靠着墙壁,一直前进,一定就会走到终点。

在1点出发,走到第一个岔路口,然后要保证右手靠墙,我们就向下走,接着下一个岔路口向左走,然后又是一个岔路口,走到4,发现是死胡同,保证右手靠墙的原地返回,走向3,2,...然后返回上一层岔路口,层层查找。

我们把这种搜索终点的方式称之为"深度优先搜索,简称DFS(Depth First Search)"

0x01、深度优先搜索的实现

从起点,走向第一层岔道,在第一层岔道内部搜索,然后进入第一层岔道内部的岔道,走到了死胡同再返回第一层岔道,走向第二层岔道。。。

写到这里可能很多人会听出来了,这个和我们前面说过的"栈"很类似,因为先进入的岔道一定会先出来,符合栈的"先进先出"法则。

但是这里我们可以用递归来实现,递归的时候系统会调用系统栈,也算是间接使用了栈。

0x02、解决一个实际问题试试

假设我是一个卖货的老大爷,我有n种货物,每件货物质量为weight[i],价值为cost[i],我现在需要选择若干件货物放在一个最大承重为V的包包里,使得包中物品价值最大,求最大价值

解决这道题前我们先把它和迷宫问题联系在一起。

这里每件物品都有选中与不选中两种可能,这就相当于迷宫中的"岔道口"。而物品总量不得超过V,这就是迷宫中的死胡同。

所以每次都要对物品进行排序,排序的起点是数组下标为0的位置,所以得到函数原型:

void DFS(int index, int sumW, int sumC);
//这里index为正在处理的位置。sumW为当前总质量,sumC为当前总价值

我们定义一个全局变量,MaxValue,让每次到"死胡同"时,计算价值与MaxValue进行比较,如果大,则替换。反之,则返回

//死胡同情况
if(index == n){    //已经完成了对n件货物的全部处理,相当于死胡同
    if(sumW <= V)    //必须要使得总质量比最大承重小
        if(sumC > MaxValue)    //如果大,则替换
            MaxValue = sumC;
    return;    //死胡同,返回。
}

岔道口我们有两种选择,选中并加上质量和价值,或者不选中,什么也不加,代码如下:

DFS(index+1, sumW, sumC);
    //index+1表示处理下一件,sumW和sumC表示下标为index的货物没被选中
DFS(index+1, sumW+weight[index], sumC+cost[index]);
    //index+1表示处理下一件,后两个参数加上了本间物品的价值与质量,表示本件物品被选中了

全部代码如下:

#include <iostream>
using namespace std;
int n, V, MaxValue = 0;
int weight[100], cost[100];

void DFS(int index, int sumW, int sumC){
//如果是死胡同
    if(index == n){
        if(sumW <= V && sumC > MaxValue) MaxValue = sumC;
        return;
    }
//如果是岔路口
    DFS(index + 1, sumW, sumC);
    DFS(index + 1, sumW + weight[index], sumC + cost[index]);
}

int main(){
    cout << "输入物品数量和包的最大承重:";
    cin >> n >> V;
    for(int i = 0; i < n; i++){
        cout << "输入第" <<i<< "件物品的重量和价值";
        cin >> weight[i] >> cost[i];
    }
    DFS(0, 0, 0);    //初始值是下标为0的物品,初始重量和初始价值均为0
    cout << "最大价值为:" << MaxValue << endl;
    return 0;
}

运行结果:

转载原创文章请注明,转载自: 斐斐のBlog » C语言-深度优先搜索(DFS)
评论已关闭