穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从众找出那些符合要求的候选解作为问题的解。<o:p></o:p>
【问题】 将A、B、C、D、E、F这六个变量排成如图所示的三角形,这六个变量分别取[1,6]上的整数,且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。<o:p></o:p>
程序引入变量a、b、c、d、e、f,并让它们分别顺序取1至6的证书,在它们互不相同的条件下,测试由它们排成的如图所示的三角形三条边上的变量之和是否相等,如相等即为一种满足要求的排列,把它们输出。当这些变量取尽所有的组合后,程序就可得到全部可能的解。细节见下面的程序。<o:p></o:p>
【程序1】<o:p></o:p>
# include <stdio.h><o:p></o:p>
void main()<o:p></o:p>
{ int a,b,c,d,e,f;<o:p></o:p>
for (a=1;a<=6;a++)<o:p></o:p>
for (b=1;b<=6;b++) {<o:p></o:p>
if (b==a) continue;<o:p></o:p>
for (c=1;c<=6;c++) {<o:p></o:p>
if (c==a)||(c==b) continue;<o:p></o:p>
for (d=1;d<=6;d++) {<o:p></o:p>
if (d==a)||(d==b)||(d==c) continue;<o:p></o:p>
for (e=1;e<=6;e++) {<o:p></o:p>
if (e==a)||(e==b)||(e==c)||(e==d) continue;<o:p></o:p>
f=21-(a+b+c+d+e);<o:p></o:p>
if ((a+b+c==c+d+e))&&(a+b+c==e+f+a)) {<o:p></o:p>
printf(“%6d,a);<o:p></o:p>
printf(“%4d%4d”,b,f);<o:p></o:p>
printf(“%2d%4d%4d”,c,d,e);<o:p></o:p>
scanf(“%*c”);<o:p></o:p>
}<o:p></o:p>
}<o:p></o:p>
}<o:p></o:p>
}<o:p></o:p>
}<o:p></o:p>
}<o:p></o:p>
按穷举法编写的程序通常不能适应变化的情况。如问题改成有9个变量排成三角形,每条边有4个变量的情况,程序的循环重数就要相应改变。<o:p></o:p>
对一组数穷尽所有排列,还有更直接的方法。将一个排列看作一个长整数,则所有排列对应着一组整数。将这组整数按从小到大的顺序排列排成一个整数,从对应最小的整数开始。按数列的递增顺序逐一列举每个排列对应的每个整数,这能更有效地完成排列的穷举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为1,2,4,6,5,3,并令其对应的长整数为124653。要寻找比长整数124653更大的排列,可从该排列的最后一个数字顺序向前逐位考察,当发现排列中的某个数字比它前一个数字大时,如本例中的6比它的前一位数字4大,这说明还有对应更大整数的排列。但为了顺序从小到大列举出所有的排列,不能立即调整得太大,如本例中将数字6与数字4交换得到的排列126453就不是排列124653的下一个排列。为了得到排列124653的下一个排列,应从已经考察过的那部分数字中选出比数字大,但又是它们中最小的那一个数字,比如数字5,与数字4交换。该数字也是从后向前考察过程中第一个比4大的数字。5与4交换后,得到排列125643。在前面数字1,2,5固定的情况下,还应选择对应最小整数的那个排列,为此还需将后面那部分数字的排列顺序颠倒,如将数字6,4,3的排列顺序颠倒,得到排列1,2,5,3,4,6,这才是排列1,2,4,6,5,3的下一个排列。按以上想法编写的程序如下。<o:p></o:p>
【程序2】<o:p></o:p>
# include <stdio.h><o:p></o:p>
# define SIDE_N 3<o:p></o:p>
# define LENGTH 3<o:p></o:p>
# define VARIABLES 6<o:p></o:p>
int A,B,C,D,E,F;<o:p></o:p>
int *pt[]={&A,&B,&C,&D,&E,&F};<o:p></o:p>
int *side[SIDE_N][LENGTH]={&A,&B,&C,&C,&D,&E,&E,&F,&A};<o:p></o:p>
int side_total[SIDE_N];<o:p></o:p>
main{}<o:p></o:p>
{ int i,j,t,equal;<o:p></o:p>
for (j=0;j<VARIABLES;j++)<o:p></o:p>
*pt[j]=j+1;<o:p></o:p>
while(1)<o:p></o:p>
{ for (i=0;i<SIDE_N;i++)<o:p></o:p>
{ for (t=j=0;j<LENGTH;j++)<o:p></o:p>
t+=*side[j];<o:p></o:p>
side_total=t;<o:p></o:p>
}<o:p></o:p>
for (equal=1,i=0;equal&&i<SIDE_N-1;i++)<o:p></o:p>
if (side_total!=side_total[i+1] equal=0;<o:p></o:p>
if (equal)<o:p></o:p>
{ for (i=1;i<VARIABLES;i++)<o:p></o:p>
printf(“%4d”,*pt);<o:p></o:p>
printf(“\n”);<o:p></o:p>
scanf(“%*c”);<o:p></o:p>
}<o:p></o:p>
for (j=VARIABLES-1;j>0;j--)<o:p></o:p>
if (*pt[j]>*pt[j-1]) break;<o:p></o:p>
if (j==0) break;<o:p></o:p>
for (i=VARIABLES-1;i>=j;i--)<o:p></o:p>
if (*pt>*pt[i-1]) break;<o:p></o:p>
t=*pt[j-1];* pt[j-1] =* pt; *pt=t;<o:p></o:p>
for (i=VARIABLES-1;i>j;i--,j++)<o:p></o:p>
{ t=*pt[j]; *pt[j] =* pt; *pt=t; }<o:p></o:p>
}<o:p></o:p>
}<o:p></o:p>
从上述问题解决的方法中,最重要的因素就是确定某种方法来确定所有的候选解。下面再用一个示例来加以说明。<o:p></o:p>
【问题】 背包问题<o:p></o:p>
问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。<o:p></o:p>
设n个物品的重量和价值分别存储于数组w[ ]和v[ ]中,限制重量为tw。考虑一个n元组(x0,x1,…,xn-1),其中xi=0 表示第i个物品没有选取,而xi=1则表示第i个物品被选取。显然这个n元组等价于一个选择方案。用枚举法解决背包问题,需要枚举所有的选取方案,而根据上述方法,我们只要枚举所有的n元组,就可以得到问题的解。<o:p></o:p>
显然,每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二进制数,且这些二进制数的取值范围为0~2n-1。因此,如果把0~2n-1分别转化为相应的二进制数,则可以得到我们所需要的2n个n元组。<o:p></o:p>
【算法】<o:p></o:p>
maxv=0;<o:p></o:p>
for (i=0;i<2n;i++)<o:p></o:p>
{ B[0..n-1]=0;<o:p></o:p>
把i转化为二进制数,存储于数组B中;<o:p></o:p>
temp_w=0;<o:p></o:p>
temp_v=0;<o:p></o:p>
for (j=0;j<n;j++)<o:p></o:p>
{ if (B[j]==1)<o:p></o:p>
{ temp_w=temp_w+w[j];<o:p></o:p>
temp_v=temp_v+v[j];<o:p></o:p>
}<o:p></o:p>
if ((temp_w<=tw)&&(temp_v>maxv))<o:p></o:p>
{ maxv=temp_v;<o:p></o:p>
保存该B数组;<o:p></o:p>
}<o:p></o:p>
}<o:p></o:p>
}
分享到:
相关推荐
算法设计是一件非常困难的工作,经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外,为了更简洁的形式设计和描述算法,在算法设计时又常常采用递归技术,用...
常用算法设计方法.一、迭代法;二、穷举搜索法;三、递推法;四、递归等等
C语言的一些常用算法设计方法,包括迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等
算法:迭代法\穷举搜索法\递推法\动态规划法等
算法设计是一件非常困难的工作,经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外,为了更简洁的形式设计和藐视算法,在算法设计时又常常采用递归技术,用...
算法设计是一件非常困难的工作,经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外,为了更简洁的形式设计和藐视算法,在算法设计时又常常采用递归技术,用...
编程常用算法,菜鸟级 (迭代法,穷举搜索法,递推法,递归,回溯法,分治法等)
迭代法、穷举搜索法、递推法、递归、回溯法、贪婪法、分治法、动态规划法
要使计算机能完成人们预定的工作,首先必须为如何完成预定的工作设计一个算法,然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述,其中程序的数据结构和变量用来描述问题的对象,...
算法设计是一件非常困难的工作,经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。
算法设计方法.rar 递归.txt 递推法.txt 迭代法.txt 动态规划法.txt 分治法.txt 回溯.txt 穷举搜索法.txt 贪婪法.txt 习题.txt
算法设计是一件非常困难的工作,经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等
算法设计的各种方法都有,如迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法,且有例子
Matlab常用算法大集合: Floyd算法.rar 免疫算法.rar 分治算法.rar 动态规划.rar 图论.rar 学习路线.png 搜索算法.rar 概率算法.rar 模拟退火算法.rar 灰色预测.rar 穷举法求解0-1整数规划的matlab程序.rar 类比法....
常用的算法设计技术有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法和动态规划法等。另外,为了以更简洁的形式设计和描述算法,在设计算法时常采用递归技术,用递归描述算法。 本讲中,主要介绍分治法。
经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外,为了更简洁的形式设计和藐视算法,在算法设计时又常常采用递归技术,用递归描述算法等。
所不同的是它在问题的整个可能解空间搜索,所设计出来的算法虽其时间复杂度比贪婪算法高,但它的优点是与穷举法类似,都能保证求出问题的最佳解,而且这种方法不是盲目的穷举搜索,而是在搜索过程中通过限界,可以...
1.2 穷举搜索法: 103 1.3 递推法: 104 1.4 递归法 106 1.5 贪婪法 111 1.6 分治法 113 1.7 动态规划法 115 1.8 回溯法 119 1.9 分支定界法: 120 2.几个重要的算法程序 121 2.1 堆排序 121 2.2 归并排序 122
的算法有:穷举搜索法、递归法、回溯法、贪 心法、分治法等。 3.算法分析 算法分析的任务是对设计出的每一个具体 的算法,利用数学工具,讨论各种复杂度,以 探讨某种具体算法适用于哪类问题,或某类问 题宜...