unit4深度优先搜索课件

1、CS101课件地址：第四讲深度优先搜索框架死路一条?死路一条死路一条?初始位置死路一条死路一条?基本流程1.2.3.如果P是目标节点，返回如果P是叶子结点，返回失败对当前P节点的每个孩子节点C3.1 搜索C节点出口3.1.1如果搜索C返回失败了，那么返回4.深度优先搜索框架形成的认知结构问题表征(数据结构）例如，地图信息用二维数组，分配问题采用布尔数组标记，最大值（最小值）采用一个变量目标的表示例如，地图上目标通常是一个位置，分配方案是每个人都满足(搜索深度到达人数），最大值（最小值）到达目标数值行动选项地图上一般是移动方向，分配方案选择或者不选择元素，最大值（最小值）加上或减去元素数值状态表

2、示例如，位置就是地图上的坐标(x, y)，分配方案是全部元素的子集，最大值（最小值）用数值表示深度优先搜索框架bool finished = false;/是否获得全部解，结束搜索? Dfs(int a, int k, data input) /a表示当前获得的部分解的集合，k表示搜索深度，input表示输入int cnoptions; /行动选项int noptions;/可选行动数量当前a1k是否是一个可行解if (is_a_solution(a, k, input) /process_solution(a, k, input); /更新到最终结果里面去,或者直接输出 else /根据当前

3、状态，构造这一步可能的选择，存入c数组，其长度存入noption construct_candidates(a, k, input, c , &noptions);for(int i=0; i < noptions; i+) ak = ci;make_move(a, k, input); /更新状态Dfs(a, k+1, input); /向下搜索一层unmake_move(a, k, input); /回溯，还原此前选择作出的改变if (finished)return; /如果符合终止条件就提前DfsTemplate.cpp通用框架例题：集合的全部子集给定一个集合a1,a2,

4、, an,输出该集合的全部子集每个元素都可以选择放入子集或者不放入共计2𝑛种选择空集也是该集合的子集例题：集合的全部子集subset.cpp例题：家园动物城遇到了麻烦，的3K开始扩张领地，动物这严重威胁动物城动物们的安全。为了 准备组建一支。但由于家园，它们对抗3K 玩耍大大咧咧，动物城内部成员存在一些不愉快，让它们加入同一只的。并肩是不可能希望能够有一个程序帮助组建动物城新军，令成员数量是最多的。例题：家园输入第1行有2个正整数n和m，表示n个动物，样例输入7 101 2它们之间有m个关系。动物编号为1，2，n。接下来的m行中，每行有2个正整数u和v，表示动物u与动物v是敌人

5、输出第1行，动物城新军的最大数量第2行，新军的成员，每名成员以空格分隔53 64 55 6样例输出31 3 7例题：家园 问题分析问题表征(数据结构）选取一个子集，元素数最多，且子集内的元素不存在关系目标的表示子集的元素数量最大行动选项元素加入或不加入子集状态表示全部可能的子集例题：家园 算法设计army当前新军成员，p为动物城第p个成员，size是当前新军的成员数量void search(p, size) if(p > n) 处理当前方案，更新最终结果returnif(p与army中的任何人都不存在) search(p+1, size+1) /新军中加入psearch(p+1, siz

6、e) /新军中不加入p例题：家园如何表示关系enemyij = 1说明i和j存在关系12345671112111111161117例题：家园defense.cpp例题：生成字符序列从三个元素的集合A，B，C中选取元素生成一个N个字符组 成的序列，使得没有两个相邻字的子序列（子序列长度=2）相同。N = 5时ABCBA是的，而序列ABCBC与ABABC是不的，因为其中子序列BC，AB是相同的。输入一行，N(1<=N<=12)输出满足条件的N个字符的所有序列及其总数例如n=10时的样例序列例题：生成字符序列将集合中的元素放入一个长度为n的序列，满足规定条件问题表征(数据结构）目标的表示

7、满足条件的序列数量A，B，CnABC行动选项从集合中选择元素放入序列位置k状态表示全部长度为n的序列例题：生成字符序列 算法设计a为输入的元素集合，str当前序列，k为序列中第k个位置void search(k) if (k > l) 方案数+1 returnfor (每一个a中的元素) if (满足放入当前位置的条件，不造成子序列将ak放入strsearch(k+1)例题：生成字符序列genstr.cpp思考：统计水洼有一个大小为N*M的园子，雨后积了很多水。八方向连通的积 水被认为是在一起的。请求出园子里共有多少个水洼？(八连 通是指右图中相对w的.部分)输入第1行2个整数，n，m第2行至n+1行，每行m个字符，表示积水情况输出www