回溯算法设计2008-05-29 10:15 P.M.[实验目的]
1. 掌握回溯法解题的基本思想；
2. 掌握回溯算法的设计方法；
3. 针对子集和数问题，熟练掌握回溯递归算法、迭代算法的设计与实现。
[预习要求]
1. 认真阅读教材或参考书, 掌握回溯法解题的基本思想, 算法的抽象控制策略；
2. 了解子集和数问题及解向量的定长和变长状态空间表示；
3. 针对解向量的定长表示, 设计状态空间树节点扩展的规范(限界)函数及实现方法；
4. 分析深度优先扩展状态空间树节点或回溯的条件；
5. 分析和设计生成解向量各分量可选值的实现方法；
6. 设计和编制回溯算法的递归和迭代程序。
[参考数据类型或变量]
float s; // 表示有可能抵达答案节点的子路径上的元素之和；
float r; // 尚未测试的剩余集合元素之和；
float w[n]; // 存储原始集合的n个元素, 根据问题实例初始化；
int x[n]; // 定长表示的解向量, 各元素初始值为0；
[参考子程序接口与功能描述]
void RecursiveSubset(float s, float r, int k)
功能: 针对问题实例的递归回溯算法。
void IterativeSubset(int m)
功能: 针对问题实例的迭代回溯算法。
void InitializeInstanse(void)
功能: 问题实例的初始化函数, 初始化子集和数M , w, x向量, s, r。
[实验步骤]
1. 录入、修改并测试你的程序，直至正确为止；
2. 针对问题实例，实录运行时的输入、输出界面；
3. 将你的程序和实录的界面存盘备用。
[实验报告要求]
1. 阐述实验目的和实验内容；
2. 提交模块化的实验程序源代码；
3. 简述程序的测试过程，提交实录的输入、输出界面；
4. 鼓励对实验内容展开讨论，鼓励提交思考与练习题的代码和测试结果。
[思考与练习]
1. 试针对解向量的变长表示设计回溯算法，上机测试正确性。
2. 试针对0/1背包问题设计回溯算法，比较与子集和数问题的算法差异。
#include
#define n 3
float s; /*表示有可能抵达答案节点的子路径上的元素之和；*/
float r; /*尚未测试的剩余集合元素之和；*/
float w[n]={2,3,4}; /*存储原始集合的n个元素, 根据问题实例初始化；*/
int x[n]; /*定长表示的解向量, 各元素初始值为0；*/
int M;
int k;
void RecursiveSubset(float s, float r, int k)/*针对问题实例的递归回溯算法*/
{int i;
x[k-1]=1;
if(s+w[k-1]==M)
{for(i=0;i
printf("\n");}
else if(((s+r)>=M)&&((s+w[k-1]+w[k]<=M)))
RecursiveSubset(s+w[k-1],r-w[k-1],k+1);
if((s+r-w[k-1]>=M)&&((s+w[k])<=M))
{x[k-1]=0;
RecursiveSubset(s,r-w[k-1],k+1);
}
}
void IterativeSubset(int m)/*针对问题实例的迭代回溯算法*/
{int i;
for(i=0;i
while(k>0)
{--x[k-1];
if(x[k-1]==0)
{if((s+r-w[k-1]>=M)&&(s+w[k]<=M))
{s+=x[k-1]*w[k-1];
r-=w[k-1];
k++;
continue;
}
else{
--k;
s-=x[k-1]*w[k-1];
r+=w[k-1];
for(i=k;i
continue;
}
}
if(s+w[k-1]==M)
for(i=0;i
else if((s+r>=M)&&(s+w[k-1]+w[k]<=M))
{s+=w[k-1];r-=w[k-1];k++;}
}
printf("\n");
}
void InitializeInstanse(void) /*问题实例的初始化函数, 初始化子集和数M , w, x向量, s, r*/
{int i;
printf("Enter M:");
scanf("%d",&M);
for(i=0;i
main()
{InitializeInstanse();
RecursiveSubset(s,r,k);
IterativeSubset(n);
system("pause");
算法的子集和数问题
找不到啊 ， 等我知道了就告诉你啊。
内容全部来源于网络收集，如有侵权，请联系网站删除：QQ：24596024