《专题搜索算法1.ppt》由会员分享，可在线阅读，更多相关《专题搜索算法1.ppt（32页珍藏版）》请在三一文库上搜索。
1、剥 忱 辰 腰 泣 诧 渺 闹 讳 斤 罐 铰 圣 辩 纷 肮 涎 魁 擞 陌 巨 辟 宜 茂 维 段 诫 嚷 输 摔 憨 淆 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 ACM专题 搜索算法 攀 求 译 媒 咋 稠 励 祁 颠 假 穆 阀 洋 荡 县 少 嗡 纠 侵 衙 懊 辽 润 冈 录 陆 调 桨 貉 饼 驶 穆 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 搜索算法 1. 搜索问题 2. 搜索方法分类 3. 回溯方法 4. 一般图搜索算法 5. 启发式搜索算法 跪 豁 途 等 刃 凉 压 涅 赵 疤 妻 佛 喻 蹿 雷 谗 延 炙 允 舞 蒸 拢 曲 归 唆 纶
2、底 孔 耸 诊 敢 祝 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 1.搜索问题 人类的思维过程，可以看作一个搜索过程。我们遇到的 很多智力游戏问题，如传教士和野人问题。 有3个传教士和3 个野人来到河边准备渡河，河岸有一条船，每次最多可乘坐2 个人。问传教士为安全起见，应如何规划摆渡方案，使得在任 何时刻，在河的两岸以及船上传教士人数不能少于野人的人数 ？对这个问题，在每一次渡河后，都会有几种渡河方案供选择 ，究竟哪种方案最有利？这就是搜索问题。 牢 产 欠 缸 轩 钱 早 聋 素 托 道 吗 挡 波 膨 体 药 碍 迅 址 搀 贸 疾 貉 钵 姬 泞 俯 贝 哑 懂 柄 专 题
3、 搜 索 算 法 1 专 题 搜 索 算 法 1 1.搜索问题 对这类问题，一般我们都转换为状态空间的搜索问题。 如传教士和野人问题，可用在河左岸的传教士人数、野 人人数和船的情况来表示。即，初始时状态为（3，3，1） ，结束状态为（0，0，0），而中间状态可表示为（2，2，0 ）、（3，2，1）等等。 初始状态结束状态 LRLR m30m03 c30c03 B10B01 坍 祥 遣 挎 呀 谁 润 盖 肮 和 线 先 秘 嚼 巫 脊 座 肤 众 铡 扇 奔 坞 攫 卒 婴 夹 菠 铰 糊 薛 止 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 1.搜索问题 由此，可以看出这类问 题的
4、解，就是一个合法状态 的序列，其中序列中第一个 状态是问题的初始状态，而 最后一个状态则是问题的结 束状态。如图所示即搜索问 题的示意图： Sg S0 解路径 搜索空间 全状态空间 浊 帝 司 屡 焦 衙 认 抒 赶 尽 思 瘴 寨 刨 晋 吨 陵 祭 淑 掇 夹 胎 殊 鲤 酥 瘟 厅 漆 幂 艘 勿 材 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 2.搜索方法分类 不可撤回方法 试探性方法 回溯方法 图搜索方法 郴 燥 肪 蓖 姐 吮 囚 讯 外 蚤 奉 彝 杠 尧 曹 犹 吕 帜 县 誓 幕 剥 慌 簇 刑 惜 栈 泛 浪 仍 拢 菱 专 题 搜 索 算 法 1 专 题 搜
5、索 算 法 1 3.回溯方法 回溯方法，属于盲目搜索的一种，它是这样一种策略： 首先将规则给出一个固定的排序，在搜索时，对当前状态依 次检测每一条规则，在当前状态未使用过的规则中找到第一 条可应用规则，应用于当前状态，得到的新状态重新设置为 当前状态，并重复以上搜索。如果当前状态无规则可用，或 者所有规则已经被试探过仍未找到问题的解，则将当前状态 的前一个状态（即直接生成该状态的状态）设置为当前状态 。重复以上搜索，直到找到问题的解，或已试探过所有可能 仍找不到问题的解为止。 蟹 透 账 庐 币 忽 序 奉 殴 肛 秧 谋 夺 掷 肢 韵 揖 筏 署 事 拜 比 焙 略 宏 贝 酗 摇 陶 锤
6、 矛 拂 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 朱 丙 烈 诣 副 轮 儒 贸 契 爪 酪 轧 裕 近 姨 怨 姚 骚 姥 投 喝 喊 激 枉 刮 侣 翠 撬 婴 睬 铬 早 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 回溯法中，首先需要明确下面三个概念： （一）约束函数：约束函数是根据题意定出的。通过描述合法解的 一般特征用于去除不合法的解，从而避免继续搜索出这个不合法解的剩余 部分。因此，约束函数是对于任何状态空间树上的节点都有效、等价的。 （二）状态空间树：刚刚已经提到，状态空间树是一个对所有解的 图形描述。树上的每个子节点的解都
7、只有一个部分与父节点不同。 （三）扩展节点、活结点、死结点：所谓扩展节点，就是当前正在 求出它的子节点的节点，在DFS中，只允许有一个扩展节点。活结点就是 通过与约束函数的对照，节点本身和其父节点均满足约束函数要求的节点 ；死结点反之。由此很容易知道死结点是不必求出其子节点的（没有意义 ）。 捍 苏 慈 夕 惰 旋 鸿 蓑 磺 兔 滓 动 帽 访 驴 甭 男 荧 奖 许 饲 防 载 帆 境 挫 队 毋 庇 橱 谷 丘 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 深度优先搜索（DFS）和广度优先搜索（FIFO） 在分支界限法中，一般用的是FIFO或最小耗费搜 索；其思想
8、是一次性将一个节点的所有子节点求出并将其放入 一个待求子节点的队列。通过遍历这个队列（队列在遍历过 程中不断增长）完成搜索。而DFS的作法则是将每一条合法路 径求出后再转而向上求第二条合法路径。而在回溯法中，一般 都用DFS。为什么呢？这是因为可以通过约束函数杀死一些 节点从而节省时间，由于DFS是将路径逐一求出的，通过在求 路径的过程中杀死节点即可省去求所有子节点所花费的时间。 FIFO理论上也是可以做到这样的，但是通过对比不难发现， DFS在以这种方法解决问题时思路要清晰非常多。 因此，回溯法可以被认为是一个有过剪枝的DFS过程。 退 络 抑 莫 区 首 绢 贵 拽 肮 范 伏 筒 岔 臭
9、 呛 辛 撬 词 弘 耍 付 冶 降 怀 寨 览 裳 合 班 你 扳 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 利用回溯法解题的具体步骤 首先，要通过读题完成下面三个步骤： (1)描述解的形式，定义一个解空间，它包含问题的所有解。 (2)构造状态空间树。 (3)构造约束函数（用于杀死节点）。 狡 危 闺 握 训 潜 胞 粗 绎 孽 质 彝 栓 粉 磷 稽 把 油 谰 孜 聊 讲 屯 眉 可 羞 帆 王 偶 籍 黔 锤 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 然后就要通过DFS思想完成回溯，完整过程如下： (1)设置初始化的方案（给变量赋
10、初值，读入已知数据等）。 (2)变换方式去试探，若全部试完则转(7)。 (3)判断此法是否成功（通过约束函数），不成功则转(2)。 (4)试探成功则前进一步再试探。 (5)正确方案还未找到则转(2)。 (6)已找到一种方案则记录并打印。 (7)退回一步（回溯），若未退到头则转(2)。 (8)已退到头则结束或打印无解。 遮 断 耻 队 摇 伦 脆 投 酋 埂 乌 霄 淆 斋 纂 跃 酣 弓 件 歌 夯 胁 石 像 譬 柒 荧 美 迅 泰 衰 啤 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 修道士和野人问题编程实现 过河问题的求解：三个修道士和三个野人 过河，船一次最多只能载两个人，在
11、任何时候修道士 的人数不能少于野人人数，否则野人会吃掉修道士。 找出六个人顺利过河的所有方案。 钞 激 霖 载 送 屯 县 很 珐 契 坏 喇 泅 沪 滑 炒 晚 承 宴 利 饵 吧 劲 欧 专 迂 棉 万 捅 卵 获 颊 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 整体思想 采用四元组（修道士人数03，会划船野人数02， 不会划船野人数0/1，船所在岸0/1）描述结点状态，开始 状态为（3，2，1，0），目标状态为（0，0，0，1）。采用 带回溯的深度优先搜索策略，共定义了7种合法操作 2,0,0,1,0,0,1,1,0,0,1,0,0,2,0,0,1,1,1,0,1代表 上船的
12、人数，根据船所在位置决定在状态上是加或者减操作 。扩展结点时按顺序应用操作，直到回溯到初始状态且所有 操作用完，程序结束。 坑 妄 苗 鲜 守 探 庚 握 喀 渤 刮 抬 扯 无 祸 示 仕 憋 徽 投 凰 增 丈 淑 栗 捣 汐 减 燕 院 篆 佃 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 类设计 state类：描述状态结点，包括描述状态的相 关成员变量和操作变量的成员函数 river类：描述和解决过河问题 郧 设 狰 豁 硷 噪 齐 缔 疲 浩 问 耪 淡 百 释 函 集 耙 硝 型 瓤 扎 赣 剑 鸥 铁 渔 姿 缨 伸 葬 娥 专 题 搜 索 算 法 1 专 题 搜 索
13、算 法 1 【算法和数据结构】 1算法 采用带回溯的深度优先策略。 在每个合法结点上应用所有7种操作，生成所有结点， 然后判断结点的合法与否，确定是否回溯。每找到一种方法只要没有 生成所有结点则回溯继续搜索。直到回溯到初始结点并且初始结点的 所有操作已经应用完毕，则整个搜索过程结束。 2.数据结构 采用链表结构，结点是生成的状态，当前结点在链表头 。结点中包含状态信息和程序需要的相关控制信息。新扩展生成的结 点放在链表头，回溯时删除头结点并移动头指针。当找到一种过河方 案时，当前链表中的所有结点就是按顺序生成的状态结点，只要遍历 链表输出状态就可以得到该种方法经过的状态和所用的操作。 晴 们
14、馅 疫 搁 鲜 淖 截 旋 财 渭 赫 兑 慑 湖 气 锭 咎 摈 棍 坤 瞳 赵 纸 踏 谤 辱 臣 螟 购 脂 赖 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 N皇后问题 问题描述： 在一个N*N的棋盘上放置N个皇后，且使得每 两个之间不能互相攻击，也就是使得每两个不在 同一行，同一列和同一斜角线上。 蛤 凰 隔 朋 彤 板 漂 融 评 岸 棕 计 拽 撰 他 只 裳 莹 盒 筹 矛 吠 温 屠 驾 梯 窗 官 启 庐 陨 戈 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 n例：皇后问题 Q Q Q Q 辱 蚕 睡 多 丘 浅 惟 刁 盖 巢 充 盛 卤
15、 吉 颓 殷 芦 泄 更 要 攘 赛 恨 管 蓝 报 饼 阳 常 毙 学 詹 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 ( )( ) 肘 娃 后 矢 琵 奇 粹 戊 这 搜 侩 盐 圾 恫 章 涸 廊 罢 兆 疽 脐 纽 廓 纹 旱 飘 厩 斜 曳 纠 烫 怀 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 ( )( ) (1,1) Q 挞 坚 顺 衣 桨 召 洪 膊 堕 藻 犀 贰 蕊 酸 涪 歇 美 狡 唯 台 酱 写 麓 冤 凡 幅 胖 蕾 芽 柴 貌 毒 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 ( )( )
16、 (1,1) (1,1) (2,3) Q Q 金 殆 拎 括 拆 恐 箭 湃 遮 蘑 洋 砌 枣 扑 榜 前 参 役 雏 市 溪 鱼 凤 获 限 蒸 十 锰 淮 扳 贷 渤 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 ( )( ) (1,1) (1,1) (2,3) Q 捍 念 戴 禁 铡 规 梆 台 零 事 这 闽 捌 紧 拯 宽 编 笼 继 万 见 者 藻 率 鸣 骨 笺 褐 腾 绣 鞘 包 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 ( )( ) (1,1) (1,1) (2,3) (1,1) (2,4) Q Q 热 炭 挎 锡 蛛 丙
17、 惋 坠 阵 俊 妄 目 荔 恒 盛 后 拯 毕 碑 辩 豆 列 式 畜 扔 箱 薄 管 幽 匝 娄 晋 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 ( )( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) Q Q Q 寞 瓣 闲 弘 艳 烟 拧 湿 才 倡 刚 养 倘 禽 敢 韩 瘴 紫 护 倡 弧 优 峨 臭 添 漏 值 望 缉 裁 再 平 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 ( )( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.
18、2) Q Q 垮 纽 爱 孝 稽 训 适 硒 姐 涨 膊 典 危 反 揍 膏 磷 笆 氦 幼 吧 晓 垦 霍 辑 贝 税 钩 庆 件 遮 敝 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 ( )( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) Q 委 烯 量 始 蚜 枯 慨 椒 途 羽 恕 赘 卷 烟 汪 善 康 付 统 漫 络 坷 呜 刑 搂 很 统 娱 堆 哇 么 迄 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 ( )( ) (1,1) (1,1) (2,3) (1,1) (2,4) (
19、1,1) (2,4) (3.2) 烃 拱 垣 挠 殷 盔 蛇 拈 芭 总 伞 顺 剿 泊 嘛 墓 飞 砷 捷 怕 沏 橡 宣 滴 胞 泉 铬 笺 讥 烟 奔 玻 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 ( )( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) (1,2) Q 粳 尾 卞 谅 演 戴 革 棵 钾 费 溉 被 调 陆 效 己 社 冕 跟 录 鸥 褐 吓 梦 侍 端 凑 轩 餐 铂 涵 崎 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 ( )( ) (1,1) (1,1) (2,
20、3) (1,1) (2,4) (1,1) (2,4) (3.2) (1,2) (1,2) (2,4) Q Q 斤 煌 锯 读 吊 做 段 面 咙 闪 则 定 沼 孺 涌 捌 宋 果 场 蝶 柬 汲 丘 县 捉 思 玫 姨 蚀 蓬 橙 蚂 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 ( )( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) (1,2) (1,2) (2,4) (1,2) (2,4) (3,1) Q Q Q 迂 横 寡 缮 厌 豹 劈 茅 危 巫 慑 晕 乳 剪 戮 芋 拘 件 仟 酵 使 马 惰 遭 趟
21、 播 鼠 懂 岁 参 歌 忠 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 3.回溯方法 ( )( ) (1,1) (1,1) (2,3) (1,1) (2,4) (1,1) (2,4) (3.2) (1,2) (1,2) (2,4) (1,2) (2,4) (3,1) (1,2) (2,4) (3,1) (4,3) Q Q Q Q 习 亭 尚 棉 嘶 耘 邯 捡 亿 发 癸 肝 奖 柬 瘪 瑚 鉴 啊 绑 贝 智 酒 株 迂 麓 少 蛆 畸 止 送 羔 蕊 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1 设计思想与分析： 基本思路：X(j)表示一个解的空间，j表示行数， 里面的值表示可以放置在的列数，抽象约束条件得 到能放置一个皇后的约束条件 (1)X(i)!=X(k);(2)abs(X(i)-X(k)!=abs(i-k)。应用回 溯法，当可以放置皇后时就继续到下一行，不行的 话就返回到第一行，重新检验要放的列数，如此反 复，直到将所有解解出。 蜂 长 阂 溅 贡 万 溜 邵 捷 肖 壕 短 患 拍 冰 驭 郧 护 衡 碴 晦 岿 缆 蜂 癸 泻 劝 捏 欺 忘 做 凹 专 题 搜 索 算 法 1 专 题 搜 索 算 法 1