文档介绍：计算机常用算法
安吉实验初中
7、动态规划
1、穷举法(枚举法)
2、递归法
3、回溯法
4、模拟法
6、分治法
5、贪心法
枚举法[穷举法]
枚举法(通常也称为穷举法)是指在一个有穷的可能的解的集合中,枚举出集合中的每一个元素,用题目给定的约束条件去判断其是否符合条件,若满足条件,则该元素即为整个问题的解;否则就不是问题的解。枚举的思想往往是最容易想到的一种解题策略,枚举法从本质上说是一种搜索的算法,但适用枚举法解题必须满足下列条件:
1)可预先确定解元素的个数n,且问题的规模不是特别大;
2)对于每个解变量A1,A2,。。。An的可能值必须为一个连续的值域。
枚举法的算法流程:设ai1为解变量Ai的最小值;aik为解变量的最大值;其中1 ≤ i ≤ n.
A1∈{a11,a12,…,a1K}
A2∈{a21,A22,…,A2K}
……
Ai∈{ai1,Ai2,…,AiK}
……
An∈{an1,An2,…,AnK}
我们称解变量为枚举变量。例如某问题的枚举变量有三个: A1, A2, A3。
A1∈{1,2}, A2∈{2,3,4}, A3∈{5,6,7}
则问题的可能解为( A1 ,A2, A3 ) ∈
{(1,2,5),(1,2,6),(1,2,7),(1,3,5),
(1,3,6),(1,3,7),(1,4,5),(1,4,6),
(1,4,7),(2,2,5),(2,2,6),(2,2,7),
(2,3,5),(2,3,6),(2,3,7),(2,4,5),
(2,4,6),(2,4,7)}
在上述18个可能解的集合中,满足问题给定的检验条件的解元素即为问题的解。
枚举法的优化方法:
1)减少枚举的变量,在使用枚举法之前,先考虑一下解元素之间的关联,将一些非枚举不可的解元素列为枚举变量,其他元素通过计算得出解元素的可能值。
例1、巧妙填数。
将1—9这9个数字填入到9个空格中。每一横行的三个数字组成一个三位数。如果要使第二行的三个三位数是第一行的2倍,第三行的三位数是第一行的三倍,应怎样填数。如图
1
9
2
3
8
4
5
7
6
2)减少枚举变量的值域
3)分解约束条件,将拆分的约束条件嵌套在相应的循环体间。
本题目有9个格子,要求填数,如果不考虑问题给出的条件,共有9!=362880种方案,在这些方案中符合条件的即为解。因此可以用枚举法。
但仔细分析问题,显然第一行的数不会超过400,实际上只要确定第一行的数就可以根据条件算出其他两行的数了。这样仅需枚举400次。
例2、有四个学生,上地理课时提出我国四大淡水湖的排序如下:
甲:洞庭湖最大,洪泽湖最小,鄱阳湖第三;
乙:洪泽湖最大,洞庭湖最小,鄱阳湖第二,太湖第三;
丙:洪泽湖最小,洞庭湖第三;
丁:鄱阳湖最大,太湖最小,洪泽湖第二,洞庭湖第三;对于各个湖泊应处的地位,每个人只说对了一个。根据以上情况,编程序判断各个湖泊应处的地位。
[算法分析]:本题是一个逻辑判断题,一般的逻辑判断题都采用枚举法进行解决。四个湖的大小分别可以有4!=24种排列可能,因为24比较小,因此我们对每种情况进行枚举,然后根据给定的条件判断哪些符合问题的要求。
源程序
例3、最佳游览路线。
某旅游区的街道成网格状。其中东西向的街道都是旅游街,南北向的街道都是林阴道。由于游客众多,旅游街被规定为单行道,游客在旅游街上只能从西向东走,在林阴道上则既可从南向北走,也可以从北向南走。
阿龙想到这个旅游街游玩,他的好友阿福给了他一些建议,用分值表示所有旅游街相邻两个路口之见的街道值得游览的程度,分值是从-100到100的整数,所有林阴道不打分。所有分值不可能全是负分。如图:
-50
-47
36
-30
-23
17
-19
-34
-13
-8
-42
-3
-43
34
-45
北
南
东
西
输入数据:,之间用一个空格隔开,m表示有多少条旅游街(1≤m≤100 ),n 表示有多少条林阴道(1≤n≤20001 )。接下来的m行依次给出了由北向南每条旅游街的分值信息。每行有n-1个整数,依次表示了自西向东旅游街每一小段的分值。同一行相邻两个数之间用一个空格隔开。
输出数据:。文件只有一行,是一个整数,表示你的程序找到的最佳游览线路的总分值。
3 6
-50 –47 36 –30 –23
17 –19 –34 –13 –8
-42 –3 –43 34 -45
84