- 浏览: 287192 次
- 性别:
- 来自: 武汉
文章分类
最新评论
-
zh1159007904:
大侠,你这个程序的递归部分看不懂,能不能麻烦解释一下递归的思路 ...
求21位水仙花数(C语言实现) -
shenma_IT:
我是一楼的神马_CS哦 再次表示感谢!!
求21位水仙花数(C语言实现) -
shenma_IT:
好 万分感谢 !!
求21位水仙花数(C语言实现) -
Touch_2011:
shenma_CS 写道你好! 我看了你的代码 有好多让我佩服 ...
求21位水仙花数(C语言实现) -
Touch_2011:
乘法是模拟数学上两个数相乘,但在处理进位方面可能有点不同。比如 ...
求21位水仙花数(C语言实现)
1、回溯法的基本思想
(1)在确定解空间的组织结构后,回溯法从开始结点(根结点)出发,以深度优先方式搜索整个解空间。这个开始结点成为活结点,同时也成为当前的扩展结点。
(2)在当前扩展结点处,搜索向纵深方向移至一个新结点。这个新结点成为新的活结点,并成为扩展结点。
(3)如果在当前扩展结点处不能再向纵深方向移动,则当前扩展结点就成为死结点。此时,应往回移动(回溯)到最近的活结点处,并使该结点成为当前的扩展结点。
(4)回溯法按上述方式递归地在解空间中搜索,直到找到所要求的解或返回至根结点为止。
2、两种类型的解空间树
子集树:当所给的问题是从n个元素的集合S中找出S满足某种性质的子集时,相应的解空间树被称为子集树。
排列树:当所给问题是确定n个元素满足某种性质的排列时,相应的解空间树被称为排列树。
3、例题分析
(1)背包问题:给定n种物品和1个背包,物品i的重量是wi,其价值为vi,背包的容量为C。要求选择装入背包的物品,使得装入背包中物品的总价值最大。
分析:从n种物品中选择若干种物品放入背包。加入一个物品,把背包里的物品看成一个集合,则这个集合是含n种物品的集合的子集.所以这是一个子集树的空间树.从物品的角度来看,每一种物品只有两种选择,放入背包或者不放入背包。设有m种物品,所以可以确定有物品的个数(假设m种全放入背包,当然为0其实是没有放入的)。这样的话就是排列树。减枝函数是基于不能超过背包的最大容量来减少搜索次数。
核心代码:
//回溯搜索解
void search(int n)
{
int i,j,temp;
int sum=0;
if(n==m)
return;
//选择物品
for(i=0;i<2;i++){
temp=remark[n];
remark[n]=i;
if(!overWeight(n)){//减枝
sum=0;
for(j=0;j<=n;j++)
sum+=cost[j]*remark[j];
if(sum>allValue)
allValue=sum;
search(n+1);
//注意回溯时返回上一个值
remark[n]=temp;
}
}
}
(2)问题描述:1000元购物卷购买m种不同价格的东西,刚好用完1000元的解决方案
分析:这个题目跟背包问题很相似.采用子集树的解空间树.搜索的时候有两种方式:如这题我是先搜索到叶子结点,判断是否满足要求,然后在回溯到上一个状态继续搜索.这样的话代码里面不需要保存上一个状态的值。上一题我的做法是搜索到一个结点就判断是否满足条件,不满足马上返回。这样的话要保存上一个状态的值。
核心代码:
//递归寻找符号条件的方案
void calculate(int index)
{
int i,sum=0;
if(index==m){//递归出口
for(i=0;i<m;i++)
sum+=count[i]*price[i];
if(sum==MONEY){//找到一种方案,记录下当时的各类商品个数
for(i=0;i<m;i++)
remark[k][i]=count[i];
k++;
}
return;
}
for(i=0;i<=max_count[index];i++){
count[index]=i;
calculate(index+1);//递归
}
}
(3)农夫过河问题:有一个农夫,带着一只狼、一只羊、一颗白菜过河。其中农夫不在的时候狼会吃羊,羊会吃白菜。只有一只船,且每次农夫最多只能带一样物品过河。求解决方案。
分析:这个问题是子集树问题,因为我们无法确定要走多少步才能全部过河。用for循环来选一个跟农夫一起过河或农夫单独过河。然后检查当前状态是否安全。不安全则返回.
当搜索完某一个状态的所有下一个状态时回溯.
核心代码:
//狼单独过河或者选择一个一起过河.i=0表示农夫单独过河
for(i=0;i<4;i++){
if(sign[i]==dir)
continue;
sign[0]=dir;
if(i)
sign[i]=dir;
if(safe()){
remark[step][0]=sign[0];
remark[step][1]=sign[1];
remark[step][2]=sign[2];
remark[step++][3]=sign[3];
dir=dir==0;//注意改变方向
cross();//递归
//注意回溯时返回上一个状态变量的值
step--;
dir=dir==0;
}
sign[0]=sign[0]==0;
if(i)
sign[i]=sign[i]==0;
}
(4)其他例题:
倒水问题:(每次两个桶互相倒水)
http://touch-2011.iteye.com/admin/blogs/1038893
马的遍历:(传入的是坐标(i,j))
http://touch-2011.iteye.com/admin/blogs/1044260
八皇后问题:
http://touch-2011.iteye.com/admin/blogs/1038918
迷宫求解:
http://touch-2011.iteye.com/admin/blogs/1033585
青蛙互换位置游戏:
/** * 背包问题 * **/ #include<stdio.h> #define CAPACITY 30 //背包总容量 #define MAX_NUM 10 //最多输入的物品数量 int weight[MAX_NUM];//物品重量 int cost[MAX_NUM]; //物品价值 int remark[MAX_NUM]={0};//记录各个物品的个数 int allValue=0; int m; //输入的物品个数 //初始化背包信息 void init() { int i; printf("输入物品数量:\n"); scanf("%d",&m); printf("依次输入物品:\n重量 价值\n"); for(i=0;i<m;i++) scanf("%d%d",&weight[i],&cost[i]); } //判断是否超重 int overWeight(int n) { int i; int sum=0; for(i=0;i<=n;i++) sum+=remark[i]*weight[i]; return sum>CAPACITY; } //回溯搜索解 void search(int n) { int i,j,temp; int sum=0; if(n==m) return; //选择物品 for(i=0;i<2;i++){ temp=remark[n]; remark[n]=i; if(!overWeight(n)){//减枝 sum=0; for(j=0;j<=n;j++) sum+=cost[j]*remark[j]; if(sum>allValue) allValue=sum; search(n+1); //注意回溯时返回上一个值 remark[n]=temp; } } } void main() { int i; init(); search(0); printf("总价值:%-4d\n",allValue); printf("物品个数:\n"); for(i=0;i<m;i++) printf("%-4d",remark[i]); printf("\n"); }
/** * 农夫过河问题 **/ #include<stdio.h> #define MAX_STEP 50 //记录农夫、狼、羊、白菜是否过河。为0表示没过河,为1表示已经过河 int sign[4]={0}; //记录各个状态 int remark[MAX_STEP][4]={0,0,0,0}; int step=1; //指示下一个要走的方向,0表示回来,1表示过河 int dir=1; //判断当前状态是否安全 int safe() { int i; //狼羊单独呆一起 if(sign[1]==sign[2] && sign[2]!=sign[0]) return 0; //羊白菜单独呆一起 if(sign[3]==sign[2] && sign[2]!=sign[0]) return 0; for(i=0;i<step;i++) //这个状态出现过 if(remark[i][0]==sign[0] && remark[i][1]==sign[1] && remark[i][2]==sign[2] && remark[i][3]==sign[3]) return 0; return 1; } //过河 void cross() { int i; //全部过河 if(remark[step-1][0] && remark[step-1][1] && remark[step-1][2] && remark[step-1][3]){ for(i=0;i<step-1;i++){ if(remark[i+1][0]-remark[i][0]>0) printf("第%d步:农夫过河 ",i+1); else if(remark[i+1][0]-remark[i][0]<0) printf("第%d步:农夫回来 ",i+1); if(remark[i+1][1]-remark[i][1]>0) printf("狼过河 ",i+1); else if(remark[i+1][1]-remark[i][1]<0) printf("狼回来 ",i+1); if(remark[i+1][2]-remark[i][2]>0) printf("羊过河 ",i+1); else if(remark[i+1][2]-remark[i][2]<0) printf("羊回来 ",i+1); if(remark[i+1][3]-remark[i][3]>0) printf("白菜过河 ",i+1); else if(remark[i+1][3]-remark[i][3]<0) printf("白菜回来 ",i+1); printf("\n"); } printf("finish\n"); return ; } //狼单独过河或者选择一个一起过河.i=0表示农夫单独过河 for(i=0;i<4;i++){ if(sign[i]==dir) continue; sign[0]=dir; if(i) sign[i]=dir; if(safe()){ remark[step][0]=sign[0]; remark[step][1]=sign[1]; remark[step][2]=sign[2]; remark[step++][3]=sign[3]; dir=dir==0;//注意改变方向 cross();//递归 //注意回溯时返回上一个状态变量的值 step--; dir=dir==0; } sign[0]=sign[0]==0; if(i) sign[i]=sign[i]==0; } } void main() { cross(); }
- 购物卷问题代码.zip (1.3 KB)
- 下载次数: 9
- 回溯法分析.zip (10.7 KB)
- 下载次数: 12
- 回溯法ppt详细讲解.zip (429 KB)
- 下载次数: 19
- 背包问题代码.zip (955 Bytes)
- 下载次数: 6
- 农夫过河代码.zip (1.1 KB)
- 下载次数: 6
发表评论
-
二叉查找树(二叉排序树)的详细实现
2011-10-22 13:18 1312博客地址: http://blog.csdn.net/tou ... -
确定参赛者名单(C语言实现)
2011-07-10 10:39 1583/* 2011第二届国信蓝点 ... -
整数划分(C语言实现)
2011-07-10 10:35 4983/* 整数的划分问题。 如,对于正整数n=6,可以分划为 ... -
几种全排列的算法(C语言实现)
2011-07-07 00:14 6327/* * 几种排列组合的算法 */ #incl ... -
Playfire加密算法(C语言实现)
2011-07-06 10:13 2991这是C语言选拔赛最后一题,题目如下: /* ... -
浅析贪心算法
2011-07-05 17:46 13811.基本思路: a.顾名思义,贪心算法总是作出在当前看来最好 ... -
浅析动态规划算法
2011-07-05 15:30 17901、 ... -
浅析递归
2011-07-02 20:40 20591.递归的思想: 设计一个递归函数,明确这个递归函数的定义, ... -
浅析分治法
2011-07-02 13:54 22741、分治法思想: 将一个难以直接解决的大问题,分割成一些规模 ... -
高精度计算
2011-06-27 14:06 10381.大整数加法 2.大整数减法 3.大整数乘法 4.大整 ... -
浅析模拟算法
2011-06-27 07:58 18711.描述 有些问题难以找到公式或规律来解决,可以按 ... -
农夫过河的四种解法
2011-06-25 14:21 6932/* * 题目描述:有一个农夫,带着一只狼、一只羊、一颗白 ... -
各种排序算法的实现(C语言实现)
2011-06-17 22:31 1716/* * 各种基本排序算法实现(以由小到大为例) */ ... -
二叉查找树(C语言实现)
2011-06-15 23:47 2574/* * 构造一颗二叉查找树,实现树的插入、删除等基本操作 ... -
哈希表查找(C语言实现)
2011-06-15 13:38 11431/* * 题目:给定一个全部由字符串组成的字典,字符串全部 ... -
索引查找之英语词典(C语言实现)
2011-06-14 22:48 5521/* * 题目:英语词典。所有的单词存放在dictionary ... -
求最短路径的两种算法(C语言实现)
2011-06-11 11:23 28397求这个有向网中任意两点的最短路径 /* ... -
拓扑排序(C语言实现)
2011-06-10 23:09 3157对这个有向图进行拓扑排序 /* * 拓扑排序(采用邻 ... -
最小生成树(C语言实现)
2011-06-10 21:30 8841求这个网的最小生成树 /* * 普里姆算法和克鲁斯卡 ... -
邻接表存储的有向图的基本操作(C语言实现)
2011-06-06 11:47 13950/* * 邻接表存储的有向图的基本操作 */ #in ...
相关推荐
浅析MAML算法1
Visual Basic文件浅析及算法分析
浅析遗传算法在电力系统中的应用.pdf
浅析遗传算法在智能组卷系统中的应用.rar
浅析遗传算法在智能组卷系统中的应用.pdf
浅析C语言递归算法
浅析算法合谋的规制路径 .docx浅析算法合谋的规制路径 .docx
浅析算法合谋的规制路径 .pdf浅析算法合谋的规制路径 .pdf
浅析C语言递归算法.pdf
随机迷宫生成算法浅析 随机迷宫生成算法浅析
算法合集之《由图论问题浅析算法优化》.ppt
从《鹰蛋》一题浅析对动态规划算法的优化.ppt
很早就对Google的PageRank算法很感兴趣,但一直没有深究,只有个轮廓性的概念。前几天趁团队outing 的机会,在动车上看了一些相关的资料(PS:在动车上看看书真是一种享受),趁热打铁,将所看的东西 整理成此文。 ...
浅析何谓分水岭算法(WatershedAlgorithm).pdf
算法学习:BM25算法浅析