《深度优先搜素课件.ppt》由会员分享，可在线阅读，更多相关《深度优先搜素课件.ppt（17页珍藏版）》请在三一办公上搜索。
1、搜索基础,计算机程序设计九,#include #include using namespace std;int work(int x) int temp; if(x0) temp=x+work(x-1); return(temp); else return 0;int main() int a; cina; coutwork(a)endl; return 0;,搜索算法是利用计算机的高性能来有目的的穷举一个问题的部分或所有的可能情况，从而求出问题的解 。,深度优先搜索 Depth First Search （DFS）广度优先搜索 Breadth First Search （BFS）,搜索,深度
2、优先搜索,从问题的某一种可能出发, 搜索从这种情况出发所能达到的所有可能, 当这一条路走到“ 尽头 ”而没找到解时, 再倒回上一个步, 从另一个可能出发, 继续搜索.,一直走到底，走不通就掉头试下一条路。,7,3,22,8,8,9,12,10,17,5,6,8,15,2,3,查找22,棋盘上A点有一个过河卒，需要走到目标B点。卒行走的规则：可以向下、或者向右。同时在棋盘上C点有一个对方的马，该马所在的点和所有跳跃一步可达的点称为对方马的控制点(象棋中马走斜“日”)。因此称之为“马拦过河卒”。棋盘用坐标表示，A点(0, 0)、B点(n, m)(n, m为不超过17的整数)，同样马的位置坐标是需要
3、给出的。现在要求你计算出卒从A点能够到达B点的路径的条数，假设马的位置是固定不动的，并不是卒走一步马走一步。输入格式一行四个数据，分别表示B点坐标和马的坐标。输出格式一个数据，表示所有的路径条数样例输入6 6 3 3样例输出6,搜索例题一 马拦过河卒,#define maxn 18 / 定义常数，棋盘的最大坐标为15using namespace std;bool amaxnmaxn; /表示棋盘，为true表示此处危险int dx9=0,-2,-2,-1,-1,1,1,2,2; /增量数组，用于表示int dy9=0,-1,1,-2,2,-2,2,-1,1; /马可攻击到的点坐标的变化范围i
4、nt m,n,x,y,i,total=0;void findway(int e,int f) /表示以点(e,f)为起点开始搜索 if(e=n),搜索例题二 图书分配,老师有n(1=n=10)本书要分给参加竞赛的n个学生。如：A，B，C，D，E共5本书要分给参加培训的简、温、张、赵、韩5位学生，每人只能选1本。教师事先让每个人将自己喜爱的书填写在如下的表中，然后根据他们填写的表来分配书本。请你设计一个程序帮助教师求出可能的分配方案，使每个学生都满意。,输入格式：第一行一个数n（学生的个数，书的数量） 以下共n行，每行n个0或1（由空格隔开），第i行数据表示第i个同学对所有书的喜爱情况。0表示不
5、喜欢该书，1表示喜欢该书。输出格式：依次输出每个学生分到的书号(输出所有可行的方案)和总共有多少种可行方案。样例：输入：book.in50 0 1 1 01 1 0 0 00 1 1 0 00 0 0 1 00 1 0 0 1输出：book.out3 1 2 4 51,#define maxn 11using namespace std;bool amaxnmaxn,bookmaxn;/booki第i本书, 可借为true,不可借为falseint bmaxn; /bi记录第i个人借的书本的编号,void try(int i) /搜索第i个人可以借的书 int j; if(i=n+1)输出结果
6、; else /i=n+1表示n个人已讨论完,找到了一种方案 for(j=1;j=n;j+) /枚举第i号人可以借的书 if(bookj) /将i设置为没有借到书 ,int main() /主程序 scanf(%d,搜索例题三 四色问题,有形如下列图形的地图，图中每一块区域代表一个国家，现请你用红（1）、兰（2）、黄（3）、绿（4）四种颜色给这些国家填上颜色，要求每一国家用一种颜色，且任意两个相邻国家的颜色不能相同，请给出一种符合条件的填色方案。给出国家的数量（=50）和它们的邻接关系。找出所有方案，按国家编号由小到大输出。,四色猜想：“任何一张地图只用四种颜色就能使具有共同边界的国家着上不同
7、的颜色。”弗南西斯格思里,输入70 1 0 0 0 0 11 0 1 1 1 1 10 1 0 1 0 0 00 1 1 0 1 0 00 1 0 1 0 1 00 1 0 0 1 0 11 1 0 0 0 1 0 输出 1213134,从第一个国家开始，对每个国家依次尝试四种颜色，判断当然选择的颜色是否和相邻的国家相同。若都不相同，则将此国家填上当前的颜色。若存在相同，则取下一种颜色继续尝试。若四种颜色都不能填上，则退回上一个国家并选择下一种颜色继续尝试。当最后一个国家也被填色后就找到一组可行解。,int s50; /sj 记录第j号国家的颜色，用1.4表示a.d四种颜色bool map51
8、51; /map存国家的邻接关系，mapxy=1表示相邻,void search(int x) / 搜索第x个国家, 即讨论第x个国家涂什么颜色 int j,k; if(x n) /总共n个国家，若已全部着色，则输出结果 for(j = 1;j=n;j+)couts j; coutendl; else / 还未全部填色，继续涂色 for(j = 1;j=4;j+) / 依次用四种颜色对当前第x号国家填色 k = 1; / 从第一个国家开始检查是否冲突 while(k x) j+) 会继续搜索其他可行方案 ,选数（choose） noip2002初中组问题描述:已知 n 个整数 x1,x2,xn
9、，以及一个整数 k（kn）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。例如当 n=4，k3，4 个整数分别为 3，7，12，19 时，可得全部的组合与它们的和为：3712=2237192971219383121934。现在，要求你计算出和为素数共有多少种。例如上例，只有一种的和为素数：371929）。 输入：键盘输入，格式为：n , k （1=n=20，kn）x1,x2，,xn （1=xi=5000000）输出：屏幕输出，格式为：一个整数（满足条件的种数）。 输入输出样例:输入：4 33 7 12 19输出：1,输入数据:4 33 7 12 19,1,0,0,7,7,3,2,
10、1,3,2,0,0,12,12,12,12,3,2,10,3,1,3,3,1,7,3,0,0,19,19,19,19,19,19,19,19,4,3,22,4,2,10,4,2,15,4,1,3,4,2,19,4,1,7,4,1,12,4,0,0,5,3,29,5,3,34,5,3,15,5,2,22,5,1,3,5,3,38,5,2,19,5,2,26,5,1,7,5,2,31,5,1,12,5,2,26,5,0,0,5,2,10,当前讨论的数字的编号,之前已经选出的数字,之前选出的数字的总和,紫色线条：选择白色线条：不选,搜索例题四：工作安排 n个人从事n项工作，每人只能从事一项，求最佳安
11、排使效益最高。设有A，B，C，D，E五人从事J1，J2，J3，J4，J5五项工作，每人只能从事一项，他们的效益如下:当 A从事J5，B从事J3， C从事J4 ， D从事J1 ，E从事J2时收益最大值：50,输入：n和矩阵输出：最大效益和方案输入：513 11 10 4 713 10 10 8 55 9 7 7 415 12 10 11 510 11 8 8 4输出：501：52：33：44：15：2,#define maxn=11;int datamaxnmaxn,n,maxx; /工人的工作效率表int fmaxn,gmaxn; /g记录分配方案的最终结果，f用于临时记录方案bool pma
12、xn; /pi记录第i份工作是否已有人做，false表示没有,void try(int k,int t) / k表示第k个人，t表示前k-1个人的总效率 int i; if(k=n+1) /n个人已全部分配工作 if(tmaxx) /判断当前这种方案的效率是否更优 /若当前方案效率更高,记录当前的效率（max）和方案(g) maxx=t; for(i=1;i=n;i+)gi=fi; return; for(i=1;i=n;i+) /工作未分配完，讨论当前k号人可做的工作 if(pi=false) /若i 号工作没人做则分配给k fk=i; /记录分配给k的工作编号 pi=true; /将i号工
13、作设置为已做 try(k+1,t+dataki); /搜索第k+1个人 pi=false; /当前总效率为前k-1个人的效率t加上k的效率datak,i ,作业2 麻将游戏一种“麻将”游戏在一个有WH格子的矩形平板上进行。 每个格子可放一个麻将牌，也可不放。玩家的目标是将所有可用一条路径相连的两张相同的牌从平板上移去。如果能将所有牌移出，则算过关。 游戏的关键问题是：两张牌之间是否可被一条路径连接，该路径满足以下两个特性： 1). 它由若干条线段组成，每条线段要么是水平方向，要么是垂直方向。 2). 这条路径不能横穿任何一个麻将牌 (但允许路径暂时离开平板)。编程序，检测两张牌是否能被一条符合
14、规定的路径所连接,样例输入：（mj.in） 输出(mj.out)5 4 4X X X X X 5X X -1X X X X X X X 33 2 3 53 1 4 43 2 4 3,输入：第一行两个整数w，h （1=w，h=75），表示平板的宽和高。 接下来h行，每行包含w个字符，如果某格子有牌，则这个格子上有个X，否则是一个空格。 平板左上角格子的坐标为（1,1）最右下角格子的坐标为（h,w）. 接下来的m行，每行有四个数x1， y1， x2， y2 ，表示两张牌的坐标输出：输出文件中，每一对牌输出占一行，为连接这一对牌的路径最少包含的线段数（穿过一个格子的线段长度为1）。 如果不存在路径则输出-1。,bool a7777; /表示游戏平板，false为可走int dx4=-1,0,0,1; /增量数组，用于四个方向的判断int dy4=0,-1,1,0;int w,h, n,x1,y1,x2,y2,step=0,min=0;bool flag; /是否找到路径的标记,void findway(int x,int y) /以点x,y为起点，搜索下一步 int i,e,f; for(i=0;i=0) ,
