深度优先搜索初析(1)

深度优先搜索初析(1)

/ 0评 / 1444次 / 1

——以“未名湖畔的烦恼”为例

题目描述

每年冬天,北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋,可是人太多了,每天下午收工后,常常一双冰鞋都不剩。
  每天早上,租鞋窗口都会排起长龙,假设有还鞋的m个,有需要租鞋的n个。现在的问题是,这些人有多少种排法,可以避免出现体育组没有冰鞋可租的尴尬场面。(两个同样需求的人(比如都是租鞋或都是还鞋)交换位置是同一种排法)

输入格式  

两个整数,表示m和n

输出格式  

一个整数,表示队伍的排法的方案数。

数据规模和约定  

m,n∈[0,18]

题目分析

看到题目的第一反应,北大那么有钱为什么还会差冰鞋(doge)。

先看题干,对于排队方案的总数计算,交换相同需求的人算同一种拍法,数据规模也不大,也就是说整个搜索树不会超过36层。

那就想到使用深度优先搜索来解决问题。也就是我们今天要讨论的问题——什么是“深度优先搜索”

所谓深度优先搜索,本质还是搜索,深度优先只是一种搜索策略。搜索的本质是对所有的可能情况进行遍历与验证的过程,不过这也有别于数学意义上的穷举法。当我们在将搜索树沿深度方向向下延伸的过程当中,我们其实也在不断地进行剪枝的操作,并以此可以大幅加快搜索步骤。

说了这么多,还是先上图。

对某一节点的分析

如此进行反复的判断与剪枝操作,也就是通过

return true 进入下一层
return false 剪枝或结束

来实现

最后,上代码!

代码

/*
* @Author: Gehrychiang
* @Date:   2019-11-05 13:40:11
* @Last Modified by:   Gehrychiang
* @Last Modified time: 2019-11-07 13:43:08
* @Email:gehrychiang@ailiyun.com
* @Website:www.yilantingfeng.site
*/
#include <iostream>
#include <cstdio>
using namespace std;
int sum=0;
bool dfs(int rm, int rn,int pool)
{
	if (rm==0&&rn==0)
	{
		++sum;
		return false;
	}
	if (rm>=1&&dfs(rm-1,rn,pool+1))
	{
        return true;
	}
	if (pool-1>=0&&rn>=1&&dfs(rm,rn-1,pool-1))
	{
		return true;
	}
	return false;
}
int main(int argc, char const *argv[])
{
	int m,n;
	cin>>m>>n;
	dfs(m,n,0);
	cout<<sum;
	return 0;
}

发表回复

您的电子邮箱地址不会被公开。

你好 No.63967