文档介绍：实验四回溯法(4学时)
上机实验一般应包括以下几个步骤:
(1)、准备好上机所需的程序。手编程序应书写整齐,并经人工检查无误后才能上机。
(2)、上机输入和调试自己所编的程序。一人一组,独立上机调试,上机时出现的问题,最好独立解决。
(3)、上机结束后,整理出实验报告。实验报告应包括:题目、程序清单、运行结果、对运行情况所作的分析。
一、实验目的与要求
掌握回溯法的基本思想方法;理解回溯法的基本思想,理解回溯法算法的两个基本要素最优子结构性质和子问题的重叠性质。熟练掌握典型的回溯法问题。
了解适用于用回溯法求解的问题类型,并能设计相应回溯法算法;
掌握回溯法算法复杂性分析方法分析问题复杂性。
二、实验内容(以下题目要求采用回溯法算法完成):
1、N皇后问题
八皇后问题是十九世纪著名的数学家高斯于1850年提出的。问题是:在8×8的棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上。可以把八皇后问题扩展到n皇后问题,即在n×n的棋盘上摆放n个皇后,使任意两个皇后都不能处于同一行、同一列或同一斜线上。如下图所示:
其中图中的一个解为:4 6 8 2 7 1 3 5
N皇后问题(含八皇后问题的扩展,规则同八皇后):在N*N的棋盘上,放置N个皇后,要求每一横行每一列,每一对角线上均只能放置一个皇后,求解可能的方案及方案数。
,设计解决上述问题的算法,设计出用回溯法计算出在N*N的棋盘上,放置N个皇后,要求每一横行每一列,每一对角线上均只能放置一个皇后,并返回每个皇后的位置。
。
2、 0-1背包问题
给定n种物品和一背包。物品i的重量是wi>0,其价值为vi>0,背包的容量为c。问应如何选择装入背包中的物品,使得装入背包中物品的总价值最大? 利用回溯法试设计一个算法求出0-1背包问题的解,也就是求出一个解向量xi
(xi = 0 或1,xi = 0表示物体i不放入背包,xi =1表示把物体i放入背包),
3、装载问题
有两艘船,它们的可装载的货物重量分别为才c1,c2,给定一批货物,其重量保存在数组w【i】中了,问这批货物能否用此两艘船送出。
三、实验步骤
理解算法思想和问题要求;
编程实现题目要求;
上机输入和调试自己所编的程序;
验证分析实验结果;
整理出实验报告。
四、实验要求
1)上述题目任选两道做。
2)独立完成程序代码的编写
3)独立完成实验及实验报告
附:实验报告的主要内容
包含:数据结构与核心算法的设计描述、函数调用及主函数设计、主要算法流程图等
附录:程序清单(程序过长,只附主要部分)
五、实验原理
一、回溯法的基本思想:
有许多问题,当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时,往往要使用回溯法。
回溯法的基本做法是搜索,是一种组织得井井有条的,能避免不必要搜索的穷举式搜索法。
回溯法在问题的解空间树中,按深度优先策略,从根结点出发搜索解空间树。算法搜索至解空间树的任意结点时,先判断该结点是否包含问题的解:1) 如果肯定不包含,则跳过这个结点;2) 如果可