算法分析与设计实验三：回溯法

宁夏师范学院数学与计算机科学学院

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

实验序号： 实验项目名称：回溯法应用

学 号 15 姓 名 高军 专业、班 10计算机

实验地点 318 指导教师 马 涛 时间 2013.06.13

一、实验目的与要求

(1)、熟悉贪心算法和回溯算法的区别；

(2)、掌握0—1背包问题的回溯算法；；

(3)、进一步掌握回溯算法；

二、实验设备（环境）及要求

1、环境要求：

硬件：PC（PII以上，128M以上内存）、因特网接入；

软件：Windows XP操作系统、Office2003、多媒体播放软件。

三、实验内容与步骤

给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

(实验提示

template

Typep Knap::Bound(int i)

{// 计算上界

Typew cleft = c - cw; // 剩余容量

Typep b = cp;

// 以物品单位重量价值递减序装入物品

while (i <= n && w[i] <= cleft) {

cleft -= w[i];

b += p[i];

i++;

}

// 装满背包

if (i <= n) b += p[i]/w[i] * cleft;

return b;

程序：

#include

using namespace std;

class Knap

{

friend int Knapsack(int p[],int w[],int c,int n );

public:

void print()

{

for(int m=1;m<=n;m++)

{

cout<

}

cout<

};

private:

２０１２年９月　第１８卷第３期　安庆师范学院学报（自然科学版）　

Ｊｏｕｍａｌ　ｏｆ　Ａｎｑｉｎｇ　Ｔｅａｃｈｅｍ　Ｃｏｌｌｅｇｅ（Ｎａｔｕｒａｌ　Ｓｃｉｅｎｃｅ　Ｅｄｉｔｉｏｎ）　Ｓｅｐｔ．２０１２　ＶｏＩ．１８　ＮＯ．３　

《算法设计与分析》课程中“回溯法＂教学探讨　

冯学军，石冰　

（安庆师范学院计算机与信息学院，安徽安庆２４６１３３）　

摘要：《算法设计与分析》是计算机科学与技术专业居于核心地位的专业课程，其中“回溯法”因其较强的实用性　经常出现在各级计算机竞赛中，因此，本文从课堂教学及实践教学两个环节分别对“回溯法”的教学方法进行了探讨。　关键词：回溯法；算法设计与分析；教学探讨　中圈分类号：ＴＰ３０１．６　文献标识码：Ａ　文章编号：１００７—４２６０（２０１２）０３—０１１３—０４　

Ｏ引　言　《算法设计与分析》是计算机科学与技术专业的专业课。学习这门课使学生了解和掌握算法设计　

的基本方法和技术，学会算法性能分析中的具体方法和技巧，为计算机应用和科学研究工作中有效求解　

问题，以及今后进一步学习奠定基础。算法中蕴藏着人类的思想与智慧，如何将这些人类智慧的结晶传　

授给学生，鼓励学生运用算法知识解决各自学科的实际问题，培养他们的独立科研能力和理论联系实践　

的能力，是教授这门学科的教师所面对的主要问题。由于这门课程理论性较强，对学生的编程能力及对　

前期课程的掌握要求较高，所以，许多学生在初学时感叹“难，学不下去”。针对我校学生的实际情况，　

我们所选用的教材是王晓东《算法设计与分析》第二版。很多文献Ｈ　对这门课程的教改已做了探讨，　

本文从教学与实践两个环节针对该书的第五章“回溯法”谈谈教学体会。　

“回溯法”号称“通解”算法，虽有些夸张，但有许多问题，当需要找出它的解集或者要求回答什么是　

满足某些约束条件的最佳解时，往往要使用回溯法。回溯法的基本做法是搜索，是一种组织得井井有　

条，非蛮力式搜索法。这种方法适用于解一些组合数相当大的问题。回溯法在问题的解空间树中，按深　

算法设计与分析-回溯法

【待求解问题描述】

有n个人和m项课题任务（n≥m），其中第i个人承担了第j项课题任务的经费消耗记作COST(i,j)，

总体经费消耗情况有m×n的COST矩阵给定。应用回溯法策略求解此问题，安排每项课题任务只能由一

个人来承担，且使完成这m项课题任务的总经费消耗为最小。可以借助问题的解空间树并以深度优先

搜索的方式遍历此树，从而获得问题的解。

【要求完成】

⑴算法描述⑵写出程序代码⑶完成调试⑷过程

与结果分析。

*/

#include

#include

#include

#include

#include

const int ROL=10; //人数

const int ROW=7; //任务数

float M[ROW][ROL]; //矩阵存储信息

int x[ROW];

float icost=1000; //保存最小经费消耗

class huisu //构造一个huisu类

{

public:

huisu(); //构造函数

~huisu(); //析构函数

void init(); //初始化函数 void finish(); //结束化函数

protected:

void nhuisu(int k); //回溯法求解函数

bool place(int k,int i); //条件判断函数

bool read(); //读文件函数

float cost; //总经费消耗

int count; //设置计数器

};

huisu::huisu()

{

count=0; //计数器初始化

cost=0;

huisu::~huisu()

{}

void huisu::init() //初始化函数

{

read(); //读文件操作

nhuisu(0);

}

void huisu::finish() //结束提示函数

{

cout<<" 一共测试"<

cout<

}

bool huisu::place(int k,int i) //条件判断函数

算法设计与分析--回溯法

回溯算法的应⽤

课程名称：算法设计与分析院系：

学⽣姓名：

学号：

专业班级：

指导教师：2013年12⽉27⽇

回溯算法的应⽤

摘要：回溯法是⼀个既带有系统性⼜带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索⾄解空间树的任⼀结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的⼦树的系统搜索，逐层向其祖先结点回溯。否则，进⼊该⼦树，继续按深度优先的策略进⾏搜索。回溯法在⽤来求问题的所有解时，要回溯到根，且根结点的所有⼦树都已被搜索遍才结束。⽽回溯法在⽤来求问题的任⼀解时，只要搜索到问题的⼀个解就可以结束。这种以深度优先的⽅式系统地搜索问题的解的算法称为回溯法，它适⽤于解⼀些组合数较⼤的问题。

回溯法在⽤来求问题的所有解时，要回溯到根，且根结点的所有可⾏的⼦树都已被搜索遍才结束。⽽回溯法在⽤来求问题的任⼀解时，只要搜索到问题的⼀个解就可以结束。这就是以深度优先的⽅式系统地搜索问题解的回溯算法，它适⽤于解决⼀些类似n 皇后问题等求解⽅案问题，也可以解决⼀些最优化问题。

在做题时，有时会遇到这样⼀类题⽬，它的问题可以分解，但是⼜不能得出明确的动态规划或是递归解法，此时可以考虑⽤回溯法解决此类问题。回溯法的优点在于其程序结构明确，可读性强，易于理解，⽽且通过对问题的分析可以⼤⼤提⾼运⾏效率。关键词：回溯法深度优先搜索递归

⽬录

第1章绪论 (1)1.1 回溯算法的背景知识 (1)

1.2 回溯法的前景意义 (1)

第2章回溯算法的理论知识 (2)2.1 回溯算法设计过程 (2)

2.2 回溯算法框架 (2)

2.3 回溯算法的⼀般性描述 (4)

第3章找n个数中r个数的组合问题 (5)3.1 问题描述 (5)

3.2 问题分析 (5)

3.3 算法设计 (5)

3.4 测试结果与分析 (6)

第4章流⽔作业车间调度问题 (8)4.1 问题描述 (8)4.2 问题分析 (8)