当前位置:首页 >> 计算机软件及应用 >>

回溯算法


淮海工学院计算机工程学院 实验报告书
课 程 名 : 题 目: 《算法分析与设计》 实验 4 回溯算法

班 学 姓

级: 号: 名:

软件 142 2014122886 杨志远

评语:

成绩:

指导教师: 批阅时间: 年 月 日

《 算法分析与设计》实验报告

-1-

实验 4 回溯算法
实验目的和要求 (1)掌握回溯法的设计思想; (2)掌握解空间树的构造方法,以及在求解过程中如何存储求解路径; (3)考察回溯法求解问题的有效程度。 (4)设计可能解的表示方式,构成解空间树; (5)设计回溯算法完成问题求解; (6)设计测试数据,统计搜索空间的结点数; 实验内容 给定 n 种物品和一个容量为 C 的背包,物品 i 的重量是 wi,其价值为 vi,0/1 背包问题 ? ak 是如何选择装入背包的物品(物品不可分割),使得装入背包中物品的总价值最大? 实验环境 Turbo C 或 VC++ 实验学时 2 学时,必做实验 数据结构与算法
k ?i j

核心源代码

1、递归算法:
#include "stdio.h" #include "stdlib.h" #define m 10 int content=20; int n=6; int x[100]; int weight[m]={0,5,3,2,10,4,2}; int price[m]={0,11,8,15,18,12,6}; int currentWeight=0; int currentPrice=0; int bestPrice=0; int bestAnswer[m];

《 算法分析与设计》实验报告

-2-

void Print() { int i; for(i=1;i<n;i++) { printf("%d",x[i]); } printf("%d\t 最大价值为:%d\n",x[i],currentPrice); } void Backtracking(int i) { if(i>n) { Print(); if(currentPrice>bestPrice) { bestPrice=currentPrice; for(int j=1;j<=n;j++) { bestAnswer[j]=x[j]; } } return; } if(currentWeight+weight[i]<=content) { x[i]=1; currentWeight+=weight[i]; currentPrice+=price[i]; Backtracking(i+1); currentWeight-=weight[i]; currentPrice-=price[i];

《 算法分析与设计》实验报告

-3-

} x[i]=0; Backtracking(i+1); } int main() { Backtracking(1); printf("最优解为:"); for(int i=1;i<n;i++) { printf("%d",bestAnswer[i]); } printf("价值为:%d\n",bestPrice); return 0; }

2、迭代法:
# include <stdio.h> int content; //背包容量 int m; //物品数 int x[100]; int weight[100]; //物品重量 int price[100]; //物品价值 int bestprice=0; int bestAnswer[100]; //当前最优解 void beibestAnswero(int n) { int i,k; for (i=1; i<=n; i++) x[i]=0; k=1; while (k>=1) { //初始化

《 算法分析与设计》实验报告

-4-

x[k]=x[k]+1;

//第 k 个物品放入背包

if (x[k]<=2&& k==m) { //得到一个解,输出 int currentWeight=0; //当前重量 int currentPrice=0; //当前价值 for (i=1; i<=n; i++) { if(x[i]==1) { currentWeight += weight[i]; currentPrice += price[i]; } } if(currentWeight<=content) { if(currentPrice>bestprice) { bestprice=currentPrice; for (int j=1; j<=n; j++) { if(x[j]==2) bestAnswer[j]=x[j]-2; else bestAnswer[j]=x[j]; } } } } else if (x[k]<=2 && k<m) k=k+1; else //放置下一个物品

《 算法分析与设计》实验报告

-5-

{ x[k]=0; k=k-1; } } } //拿走第 k 个物品,重置 x[k],回溯

void main() { int i; printf("请输入物品的数量:"); scanf("%d",&m); printf("请输入背包的容量:"); scanf("%d",&content); printf("请依次输入%d 个物品的重量:",m); for(i=1;i<=m;i++) scanf("%d",&weight[i]); printf("请依次输入%d 个物品的价值:",m); for(i=1;i<=m;i++) scanf("%d",&price[i]); beibestAnswero(m); printf("\n 最优解为"); for(i=1;i<m;++i) printf("%d,",bestAnswer[i]); printf("%d}\t 背包获得的最大价值为:%d\n",bestAnswer[i],bestprice); }

《 算法分析与设计》实验报告

-6-

实验结果

1、递归算法:

2、迭代法:

实验体会
通过这次实验我了解了回溯法的基本思想,从解空间树深度优先策略搜素满足约束条件的解。 在搜索至树中的某结点时, 先判断该结点对应的部分解是否满足约束条件, 如果肯定不包含最优解, 则跳过该结点为根的子树,否则进入该结点为根的子树,继续按照深度优先策略进行搜索。 算法分析对于我来说还是有一定的难度的。不仅需要理解各个方法的基本思想和解题思路,还 要将所学知识运用到编程当中去。在编程过程中,我会遇到很多问题,这让我体会到了还需巩固以 前所学的编程知识,否则很难实现问题的解决。


相关文章:
回溯算法原理和几个常用的算法实例.doc
IT技术| 算法| 回溯算法原理和几个常用的算法实例_IT/计算机_专业资料。回溯算法,八皇后问题,迷宫问题,骑士周游问题,幂集问题的算法原理和程序 回溯...
回溯算法(C++版).doc
回溯算法(C++版) - 一、回溯算法的定义: 回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是: 从一条路往前走,能进则进,不能进...
算法设计与分析:回溯法-实验报告.doc
算法设计与分析:回溯法-实验报告 - 应用数学 学院 姓名 实验题目 信息安全 专业 班 学号 回溯算法 实验评分表 序 评分项目 号 1 指导教师评分标准 完成度 评分...
算法分析_回溯法(很不错).ppt
? 回溯法回溯算法是所有搜索算法中最为基本的一种算法,是一 种能避免不必要搜索的
回溯算法_图文.ppt
回溯算法_学科竞赛_高中教育_教育专区。回溯算法2016冬令营第4讲 1 ?
回溯算法实例一.doc
回溯算法实例一 - 【问题】 填字游戏 问题描述: 在 3×3 个方格的方阵中要
回溯算法的一些例题.doc
回溯算法的一些例题 - 回溯算法 搜索与回溯是计算机解题中常用的算法, 很多问题
搜索与回溯算法.doc
29 回溯算法一、回溯法的思想在求解一些问题(如走迷宫、地图着色等问题)时,题目
回溯算法.doc
回溯算法 - 回溯算法 一、介绍: 回溯算法实际上一个类似枚举的搜索尝试过程,主
深度优先搜索与回溯算法_图文.ppt
深度优先搜索与回溯算法 - 深度优先搜索与回溯算法 回溯是计算机解题中常用的算法
回溯算法(含代码).doc
回溯算法(含代码) - 回溯算法 引言 寻找问题的解的一种可靠的方法是首先列出所
回溯算法的应用(DOC).doc
回溯算法的应用(DOC) - 回溯算法的应用 课程名称: 院系: 算法设计与分析
算法8_回溯法_图文.ppt
算法8_回溯法 - 第8章 回溯法 学习要点: ? ? ? ? 理解回溯法的深度优先搜索策略 理解剪枝函数(约束函数和限界函数)的作用 掌握回溯法解题的算法框架 (1)...
回溯算法_图文.ppt
回溯算法 - 回溯算法 JSOI 2008 夏令营(丹阳) 江苏省苏州中学 张信
回溯算法-八皇后_图文.ppt
回溯算法-八皇后 - 经典回溯算法 八皇后问题 八皇后问题-1850年高斯 ?
回溯算法_图文.ppt
回溯算法 - 回溯算法 奥赛暑假培训班专题之一 双十中学 庄晓芳 2006.7 回溯算法是所有搜索算法中最为基本的一种算法,是一种 能避免不必要搜索的穷举式的搜索...
回溯算法的应用.doc
回溯算法的应用_计算机软件及应用_IT/计算机_专业资料。回溯算法的应用回溯算法的应用 课程名称: 院系: 算法设计与分析 *** *** *** 学生姓名: 学号: 专业班...
哈密顿回路问题的回溯算法.doc
哈密顿回路问题的回溯算法 - ● 哈密顿回路问题: ● 解空间: A={ (x1
数学建模回溯法_图文.ppt
数学建模回溯法 - 第5章 回溯法 1 ? ? ? ? ? 学习要点 理解回溯法的深度优先搜索策略。 掌握用回溯法解题的算法框架 (1)递归回溯 (2)迭代回溯 ? ? (3...
算法分析复习题目及答案.doc
算法分析复习题目及答案 - 一。选择题 1、二分搜索算法是利用( A、分治策略 A )实现的算法。 C、贪心法 A D、回溯法 )。 D、定义最优解 B、动态规划法...
更多相关标签: