《信息学奥赛NOIP贪心深度优先搜索1复习课程.ppt》由会员分享，可在线阅读，更多相关《信息学奥赛NOIP贪心深度优先搜索1复习课程.ppt（21页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、信息学奥赛信息学奥赛NOIPNOIP贪心深贪心深度优先搜索度优先搜索1 1搜索 搜索（search）算法是利用计算机的高性能来有目的的穷举一个问题解空间的部分或所有的可能情况，从而求出问题的解的一种方法。路漫漫其修远兮，吾将上下而求索。-战国（楚）屈原离骚借问酒家何处有？牧童遥指杏花村。-唐 杜牧清明松下问童子，言师采药去。只在此山中，云深不知处。-唐 贾岛寻隐者不遇 众 里 寻 他 千 百 度。蓦 然 回 首，那 人 却 在，灯 火 阑 珊 处。-宋 辛弃疾 青玉案元夕 古人的搜索黑夜给了我黑色的眼睛，我却用它寻找光明。顾城 一代人撑着油纸伞，独自彷徨在悠长、悠长又寂寥的雨巷我希望逢着一个丁
2、香一样地结着愁怨的姑娘.-戴望舒 雨巷今人的搜索 搜索不是万能的，没有搜索是万万不能的。鸡兔同笼（NOI题库1752）【问题描述】一个笼子里面关了鸡和兔子（鸡有2只脚，兔子有4只脚，没有例外）。已经知道了笼子里面脚的总数a，问笼子里面至少有多少只动物，至多有多少只动物。【输入格式】一行，一个正整数a(a 32768)。【输出格式】一行，包含两个正整数，第一个是最少的动物数，第二个是最多的动物数，两个正整数用一个空格分开。如果没有满足要求的答案，则输出两个0，中间用一个空格分开。【样例输入】20【样例输出】5 10那些4位数()题目描述 那些4位数，只由1,2,3,4这4个数字组成。请编写程序，
3、输出这些4位数，先小后大，每行一个。输入无输出11111112.4444那些N位数题目描述 那些N位数只由1，2，3，.p这p个数字组成（p=9）。请编写程序输出这些4位数。先小后大，每行一个。输入：二个整数N（1 N 8）和p(p 9)输出：若干个N位数，每行一个样例输入：4 3样例输出：11111112.3333走迷宫（走迷宫（maze.in/out/pas/cpp）【问题描述】【问题描述】一个迷宫由一个迷宫由R行行C列格子组成，有的格子里列格子组成，有的格子里有障碍物，不能走；有的格子是空地，可以走。有障碍物，不能走；有的格子是空地，可以走。给定一个迷宫，求从左上角走到右下角最少需要给定
4、一个迷宫，求从左上角走到右下角最少需要走多少步走多少步(数据保证一定能走到数据保证一定能走到)。只能在水平方。只能在水平方向或垂直方向走，不能斜着走。向或垂直方向走，不能斜着走。【输入格式】【输入格式】第一行是两个整数，和（第一行是两个整数，和（1=R，C=40)，代表迷宫的长和宽。，代表迷宫的长和宽。走迷宫（走迷宫（maze.in/out/pas/cpp）接下来是行，每行个字符，代表整个迷宫。接下来是行，每行个字符，代表整个迷宫。空地格子用空地格子用.表示，有障碍物的格子用表示，有障碍物的格子用#表示。表示。迷宫左上角和右下角都是迷宫左上角和右下角都是.。【输出格式】【输出格式】输出从左上角
5、走到右下角至少要经过多少输出从左上角走到右下角至少要经过多少步（即至少要经过多少个空地格子）。计算步步（即至少要经过多少个空地格子）。计算步数要包括起点和终点。数要包括起点和终点。走迷宫（走迷宫（maze.in/out/pas/cpp）【输入样例】【输入样例】5 55 5.#.#.#.#.#.#.#.#.#.#.#.#.#.#.#.【输出样例】【输出样例】9 9走迷宫（走迷宫（maze.in/out/pas/cpp）状态分析：状态分析：1.1.初始状态初始状态 2.2.目标状态目标状态 3.3.状态转移状态转移走迷宫（走迷宫（maze.in/out/pas/cpp）实现：实现：1.1.深搜深搜
6、 2.2.宽搜宽搜 程序结构程序结构void Search(int k)for（所有的选择（所有的选择i）if （满足条件）（满足条件）保存结果保存结果;if（到目的地）输出解；（到目的地）输出解；else Search(k+1);恢复：保存结果之前的状态；恢复：保存结果之前的状态；/回溯一回溯一步步 程序结构程序结构void Search(int k)if (到目的地到目的地)输出解输出解;else for(所有的选择所有的选择i)if (满足条件满足条件)保存结果保存结果;Search(k+1,参数表参数表);恢复：保存结果之前的状态；恢复：保存结果之前的状态；/回溯一回溯一步步 搜索是计
7、算机程序设计中最基本、最常搜索是计算机程序设计中最基本、最常用的算法。用的算法。搜索是基于计算机高速运算的特点而使搜索是基于计算机高速运算的特点而使用的求解方法。用的求解方法。搜索可以用来求一个解、所有解、最优搜索可以用来求一个解、所有解、最优解。解。搜索的思想就是从问题的初始状态出搜索的思想就是从问题的初始状态出发，根据问题的约束条件，按照一定的控发，根据问题的约束条件，按照一定的控制策略，有序推进，不断深入，对于生成制策略，有序推进，不断深入，对于生成的所有目标状态，一一验证，从而获得符的所有目标状态，一一验证，从而获得符合条件的可行解，或根据评价函数选择出合条件的可行解，或根据评价函数选
8、择出最优解。最优解。搜索算法的思想搜索算法的思想一个状态空间：一个状态空间：状态的表示、状态集合、初始状态、目标状态的表示、状态集合、初始状态、目标状态状态举例：分油（举例：分油（10，7，3）：（）：（10，0，0）（5，5，0）一个产生式系统：包括一个综合数据库一个产生式系统：包括一个综合数据库（表示问题状态的数据结构）、一组产生（表示问题状态的数据结构）、一组产生式规则（式规则（ifelse语句）、一个控制系统语句）、一个控制系统（实现状态的有序转移，（实现状态的有序转移，BFS/DFS等）等）搜索算法的核心搜索算法的核心输出输出N的全排列的全排列 给定给定N（n=10)，输出，输出N的全排列。的全排列。如如N=3时，输出：时，输出：1 2 31 3 22 1 32 3 13 1 23 2 1组合组合 给定给定m,n（1=n=m=20)，输出从，输出从m个数中选个数中选n个数的情况个数的情况。如。如m=4,n=2时，时，输出：输出：1 2 1 31 42 32 43 4THANKS结束结束