迷宫生成算法 回溯法

第 页 共 页 华北水利水电学院 数据结构与算法分析 实验报告

2009 ～2010 学年 第 1 学期 2009 级 计算机 专业

班级： 200915326 学号： 200915326 姓名： 郜莉洁

一、 实验题目：

分别用回溯法和分支限界法求解0-1背包问题

二、 实验内容：

0-1背包问题： 给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?

在选择装入背包的物品时，对每种物品i只有2种选择，即装入背包或不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。

三、 程序源代码：

A:回溯法：

// bag1.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include

#define MaxSize 100 //最多物品数

int limitw; //限制的总重量

int maxwv=0; //存放最优解的总价值

int maxw;

int n; //实际物品数

int option[MaxSize]; // 存放最终解

int op[MaxSize]; //存放临时解

struct {

int weight;

int value;

}a[MaxSize]; //存放物品数组

void Knap( int i, int tw, int tv) //考虑第i个物品

应用数学 学院 信息安全 专业 班 学号

姓名

实验题目 回溯算法

实验评分表

指导教师评分标准 序号 评分项目 评分标准 满分 打分

1 完成度 按要求独立完成实验准备、程序调试、实验报告撰写。 20

2 实验内容 （1） 完成功能需求分析、存储结构设计；

（2） 程序功能完善、可正常运行；

（3） 测试数据正确，分析正确，结论正确。

30

3 实验报告 内容齐全，符合要求，文理通顺，排版美观。 40

4 总结 对实验过程遇到的问题能初步独立分析，解决后能总结问题原因及解决方法，有心得体会。 10

实验报告

一、实验目的与要求

1、理解回溯算法的基本思想；

2、掌握回溯算法求解问题的基本步骤；

3、了解回溯算法效率的分析方法。

二、实验内容

【实验内容】

最小重量机器设计问题：设某一个机器有n个部件组成，每个部件都可以m个不同供应商处购买，假设已知 表示从j个供应商购买第i个部件的重量， 表示从j个供应商购买第i个部件的价格，试用回溯法求出一个或多个总价格不超过c且重量最小的机器部件购买方案。

【回溯法解题步骤】

1、确定该问题的解向量及解空间树；

2、对解空间树进行深度优先搜索；

3、再根据约束条件（总价格不能超过c）和目标函数（机器重量最小）在搜索过程中剪去多余的分支。

4、达到叶结点时记录下当前最优解。

5、实验数据n,m, ]][[jiw,]][[jic的值由自己假设。

三、算法思想和实现

【实现代码】

【实验数据】

假设机器有3个部件，每个部件可由3个供应商提供（n=3，m=3）。

总价不超过7（c<=7）。

部件重量表：

重量 供应商1 供应商2 供应商3

部件1 2 3 3

部件2 1 2 2

部件3 3 4 1

部件价格表：

价格 供应商1

供应商2 供应商3

1

算法与数据结构

课程设计

课题：求解迷宫通路的图形界面演示程序

作者：***

QQ：328035823

2

目录

1.题目及需求分析········································4

2.概要设计··············································4

3.详细设计·············································10

4.调试分析·············································39

5.课程设计总结·········································42

3

1．题目及需求分析

1.1题目

编制一个求解迷宫通路的图形界面演示程序。

1.2需求分析

1. 输入一个任意大小的迷宫，任设起点、终点、障碍，用栈求出一条走出迷宫的路径，并显示在屏幕上；

2. 根据用户界面提示，用键盘输入，Home键设置迷宫起点，End键设终点，上下左右箭头键移动，Enter键添加墙，Del键删除墙，完成后按F9键演示，演示完毕后可F5刷新题图，重新对地图的起点、终点、障碍进行设置，Esc键退出；

3. 本程序要求至少得出一条成功的通路，也可求得全部路径。此外，也可尝试保存或载入测试文件（此功能不做强行要求）。

4. 当未输入起点时，消息显示“Error： You must set the START.”；未输入终点时，显示“Error： You must set the END.”；找到路径时，屏幕显示足迹，并在消息框出现Path found，否则消去足迹，显示Path not found。

5. 用户可以通过界面上提供的菜单选项，选择“帮助”查看操作说明。

6. （算法选优）用户可以通过界面上提供的菜单选项，选择“A*算法求最短路径”演示求解迷宫最短路径。

实用标准文案

文档大全 1、回溯法

(1)描述:回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。

(2)原理: 回溯法在问题的解空间树中，按深度优先策略，从根结点出发搜索解空间树。算法搜索至解空间树的任意一点时，先判断该结点是否包含问题的解。如果肯定不包含，则跳过对该结点为根的子树的搜索，逐层向其祖先结点回溯；否则，进入该子树，继续按深度优先策略搜索。

回溯法的基本做法是搜索，或是一种组织得井井有条的，能避免不必要搜索的穷举式搜索法。这种方法适用于解一些组合数相当大的问题。有许多问题，当需要找出它的解集或者要求回答什么解是满足某些约束条件的最佳解时，往往要使用回溯法。

(3)问题的解空间

问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式。

显约束：对分量xi的取值限定。

隐约束：为满足问题的解而对不同分量之间施加的约束。

解空间：对于问题的一个实例，解向量满足显式约束条件的所有多元组，构成了该实例的一个解空间。 实用标准文案

文档大全

注意：同一个问题可以有多种表示，有些表示方法更简单，所需表示的状态空间更小（存储量少，搜索方法简单）。

例1：n=3的0——1 背包问题的回溯法搜索过程。W=[16,15,15] p=[45,25,25] C=30

例2：旅行售货员问题。某售货员要到若干城市去推销商品，已知各城市之间的路程（旅费），他要选定一条从驻地出发，经过每个城市一遍，最后回到驻地的路线，使总的路程（总旅费）最小。

实用标准文案

文档大全 (4)生成问题状态的基本方法

扩展结点:一个正在产生儿子的结点称为扩展结点。