搜索1 - 搜索1-课件·PPT.ppt

文档介绍：搜索及其优化和应用
福州第三中学宋立林
搜
索
是
什
么
?
搜索
顾名思义,
把所有可能的情况用各种方法例举出来,
进行处理
是非常重要的解题方法
由于计算机的高速度,使得搜索成为可能
搜索方法的解题步骤
选择顺序
明确对象
确定方法
理解题意
搜索
预处理阶段
有序化
搜索阶段
有序化
编程实现
数
学
模
型
搜索
搜索
什么时候用搜索?
搜索策略
(回溯法)
一。枚举法
搜索

枚举法
基本思想
根据提出的问题,
枚举所有可能的状态,
并用问题给定的条件检验,
选择出需要的解,
使得命题成立
枚举法
满足条件
(1)可预先确定状态的数量,以及每个状态的元素个数
(2)状态元素a,b,…,的可能值为一个连续的值域
例如a1,a2,a3。。。
b1,b2,b3。。。
枚举法
格式
for a1 to ak1
for b1 to bk2
for c1 to ck3
……
if (状态a,b,c…)满足条件 then
输出问题的解
优点
不足
枚举法
(1)直观,易于理解
(2)正确性容易证明
效率可能比较低
枚举法
例
百钱买百鸡:今有钱100元,要买100只鸡,公鸡3元一只,母鸡1元一只,小鸡1元3只,若公鸡、母鸡和小鸡都至少要买1只,请编程求出恰好用完100元钱的所有的买鸡方案。