将n个集装箱装上载重量为c1和c2的轮船，其中集装箱总重量 二、实验流程图： input.txt output.txt 四、源程序： package javaapplication1; import java.io.*; public class Main { static int n; static int []w; static int c1,c2; static int cw; static int bestw; static int r; static int []x; static int []bestx; public static int maxloading(int[]ww,int cc,int[]xx){ w=ww; c1=cc; bestw=0; cw=0; x=new int[n+1]; bestx=xx; r=0; for(int i=1;i<=n;i++) r+=w[i]; backtrack(1); return bestw; } private static void backtrack(int i){ if(i>n){ if(cw>bestw){ for(int j=1;j<=n;j++) bestx[j]=x[j]; bestw=cw; } return; } r-=w[i]; if(cw+w[i]<=c1){ x[i]=1; cw+=w[i]; backtrack(i+1); cw-=w[i]; } if(cw+r>bestw){ x[i]=0; backtrack(i+1); } r+=w[i]; } public static void main(String[] args) throws IOException { BufferedReader read =new BufferedReader(new InputStreamReader(new FileInputStream("input.txt"))); String a=new String(); a=read.readLine(); n=Integer.parseInt(a); System.out.println("集装箱个数: "+n); x=new int[n+1]; String[]b=new String[n]; a=read.readLine(); System.out.println("集装箱重量: "+a); b=a.split(","); w=new int[n+1]; for(int i=1;i<=n;i++){ w[i]=Integer.parseInt(b[i-1]); } a=read.readLine(); c1=Integer.parseInt(a); a=read.readLine(); c2=Integer.parseInt(a); System.out.println("轮船载重量: "+c1+","+c2); int result= maxloading(w,c1,x); int max,temp; for(int i=1;i<3;i++){ for(int j=2;j<3;j++){ if(w[i]>w[j]){ temp=w[i]; w[i]=w[j]; w[j]=temp; } } } if((w[3]>c1)&&(w[3]>c2)){ System.out.println("都不可装"); } else{System.out.println("轮船1装载的集装箱："); for (int u=1;u if(bestx[u]==1) System.out.println(u+" "); if(r>(result+c2)) System.out.println("轮船1可装："+result+" "+"轮船2装不完."); else{ System.out.println("轮船2装载的集装箱："); for (int u=1;u if(bestx[u]==0) System.out.println(u+" "); System.out.println("最优装载--轮船1:"+result+" "+"轮船2:"+(r-result)); } } PrintWriter print=new PrintWriter(new OutputStreamWriter(new FileOutputStream("output.txt"))); if((w[3]>c1)&&(w[3]>c2)){ print.println("都不可装。"); } else{ print.println("轮船1装载的集装箱："); for (int u=1;u if(bestx[u]==1) print.println(u+" "); if(r>(result+c2)) print.println("轮船1可装："+result+" "+"轮船2装不完。"); else{ print.println("轮船2装载的集装箱："); for (int u=1;u if(bestx[u]==0) print.println(u+" "); print.println("最优装载--轮船1:"+result+" "+"轮船2:"+(r-result)); } } read.close(); print.close(); } } 0-1背包动态规划解决问题 一、问题描述： 有n个物品，它们有各自的重量和价值，现有给定容量的背包，如何让背包里装入的物品具有最大的价值总和？ 二、总体思路： 根据动态规划解题步骤（问题抽象化、建立模型、寻找约束条件、判断是否满足最优性原理、找大问题与小问题的递推关系式、填表、寻找解组成）找出01背包问题的最优解以及解组成，然后编写代码实现。 原理： 动态规划与分治法类似，都是把大问题拆分成小问题，通过寻找大问题与小问题的递推关系，解决一个个小问题，最终达到解决原问题的效果。但不同的是，分治法在子问题和子子问题等上被重复计算了很多次，而动态规划则具有记忆性，通过填写表把所有已经解决的子问题答案纪录下来，在新问题里需要用到的子问题可以直接提取，避免了重复计算，从而节约了时间，所以在问题满足最优性原理之后，用动态规划解决问题的核心就在于填表，表填写完毕，最优解也就找到。 过程： a) 把背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第i个物品选或不选），V i表示第i个物品的价值，W i表示第i个物品的体积（重量）； b) 建立模型，即求max(V1X1+V2X2+…+VnXn)； c) 约束条件，W1X1+W2X2+…+WnXn 动态规划法、回溯法解0-1背包问题 2012级计科庞佳奇 一、问题描述与分析 1.动态规划算法通常用于求解具有某种最优性质的问题。在这类问题中，可能会 有许多可行解。每一个解都对应于一个值，我们希望找到具有最优值的解。动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。若用分治法来解这类问题，则分解得到的子问题数目太多，有些子问题被重复计算了很多次。如果我们能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，这样就可以避免大量的重复计算，节省时间。我们可以用一个表来记录所有已解的子问题的答案。 不管该子问题以后是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划法的基本思路。具体的动态规划算法多种多样，但它们具有相同的填表格式。 多阶段决策问题中，各个阶段采取的决策，一般来说是与时间有关的，决策依赖于当前状态，又随即引起状态的转移，一个决策序列就是在变化的状态中产生出来的，故有“动态”的含义，称这种解决多阶段决策最优化问题的方法为动态规划方法。任何思想方法都有一定的局限性，超出了特定条件，它就失去了作用。同样，动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。1.最优化原理（最优子结构性质）最优化原理可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。简而言之，一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。2.无后效性将各阶段按照一定的次序排列好之后，对于某个给定的阶段状态，它以前各阶段的状态无法直接影响它未来的决策，而只能通过当前的这个状态。换句话说，每个状态都是过去历史的一个完整总结。这就是无后向性，又称为无后效性。3.子问题的重叠性动态规划将原来具有指数级时间复杂度的搜索算法改进成了具有多项式时间复杂度的算法。其中的关键在于解决冗余，这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术，它在实现的过程中，不得不存储产生过程中的各种状态，所以它的空间复杂度要大于其它的算法。 01背包是在M件物品取出若干件放在空间为W的背包里，每件物品的体积为W1，W2……Wn，与之相对应的价值为P1,P2……Pn。求出获得最大价值的方案。 2.回溯法（探索与回溯法）是一种选优搜索法，按选优条件向前搜索，以达到目 标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根结点出发深度探索解空间树。当探索到某一结点时，要先判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果该结点不包含问题的解，则逐层向其祖先结点回溯。（其实回溯法就是对隐式图的深度优先搜索算法）。若用回溯法求问题的所有解时，要回溯到根，且根结点的所有可行的子树都要已被搜索遍才结束。 迷宫求解问题 摘要：用矩阵表示迷宫，将矩阵表示的迷宫转换成无向图，用邻接表存储。对无向图从入口结点开始广度优先搜索，用一个一维数组存储各个结点的前驱结点的编号，通过出口结点Vn找到其前驱结点Vn-1,再通过Vn-1找到Vn-2，依次类推直到找到出口结点。 关键字：矩阵迷宫求解 一、需求分析 1.程序题目： 迷宫求解问题。迷宫是一个如下所示的m行n列的0-1矩阵，0表示无障碍，1表示有障碍。设入口为（1，1），出口为（m，n），每次移动只能从一个无障碍的单元移到周围8个方向的任意一个无障碍的单元，编写程序给出一条通过迷宫的路径或者报告一个“无法通过”的信息。 入口->(0，0，0，1，0，0，0，1，0，0，0，1，0，0，1) (0，1，0，0，0，1，0，1，0，0，0，1，1，1，1) (0，1，1，1，1，1，0，1，0，0，1，1，1，0，1) (1，1，0，0，0，1，1，0，1，1，0，0，1，0，1) (1，0，0，1，0，1，1，1，1，0，1，0，1，0，1) (1，0，1，0，0，1，0，1，0，1，0，1，0，1，0) (1，0，1，1，1，1，1，0，0，1，1，1，1，0，0) (1，1，1，0，1，1，1，1，0，1，0，1，0，1，0) (1，0，1，0，1，0，1，1，1，0，1，0，0，0，1) (0，1，0，1，0，1，0，0，0，1，1，0，0，1，0)->出口 2．程序说明及任务： 迷宫问题要求寻找一条从入口到出口的路径。路径是由一组位置构成的，每个位置上都没有障碍，且每个位置（第一个除外）都是前一个位置的东、南、西或北的邻居，如图C。 计算机走迷宫的方法是，采取一步一步试探的方法。每一步都从东开始，按顺时针对8个方向进行试探，若某方向上maze（x，y）=0，表示可以通行，则走一步；若maze（x，y）=1，表示不可以通行，须换方向再试，直到8个方向都试过；若maze （x，y）均为1，说明此步已无路可走，需退回一步，在上一步的下一个方向重新开始探测。为此，需设置一个栈，用于记录所走过的位置和方向（i,j,dir）。当退回一步时，从栈中退出一个元素，以便在上一个位置的下一个方向上探测，如又找到一个行进方向，则把当前位置和方向重新进栈，并走到新的位置。 //回溯法之N皇后问题当N>10，就有点抽了~~ /*结果前total行每行均为一种放法，表示第i行摆放皇后的列位置，第total+1行，输出total*/ #include 0-1背包问题 计科1班朱润华 2012040732 方法1：回溯法 一、回溯法描述： 用回溯法解问题时，应明确定义问题的解空间。问题的解空间至少包含问题的一个（最优）解。对于0-1背包问题，解空间由长度为n的0-1向量组成。该解空间包含对变量的所有0-1赋值。例如n=3时，解空间为：｛（0，0，0），（0，1，0），（0，0，1），（1，0，0），（0，1，1），（1，0，1），（1，1，0），（1，1，1）｝然后可将解空间组织成树或图的形式，0-1背包则可用完全二叉树表示其解空间给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问:应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 形式化描述：给定c >0, wi >0, vi >0 , 1≤i≤n.要求找一n元向量(x1,x2,…,xn,), xi∈{0,1}, ? ∑ wi xi≤c,且∑ vi xi达最大.即一个特殊的整数规划问题。 二、回溯法步骤思想描述： 0-1背包问题是子集选取问题。0-1 背包问题的解空间可以用子集树表示。在搜索解空间树时，只要其左儿子节点是一个可行节点，搜索就进入左子树。当右子树中有可能含有最优解时，才进入右子树搜索。否则，将右子树剪去。设r是当前剩余物品价值总和，cp是当前价值；bestp是当前最优价值。当cp+r<=bestp时，可剪去右子树。计算右子树上界的更好的方法是将剩余物品依次按其单位价值排序，然后依次装入物品，直至装不下时，再装入物品一部分而装满背包。 例如：对于0-1背包问题的一个实例，n=4,c=7,p=[9,10,7,4],w=[3,5,2,1]。这4个物品的单位重量价值分别为[3,2,3,5,4]。以物品单位重量价值的递减序装入物品。先装入物品4，然后装入物品3和1.装入这3个物品后，剩余的背包容量为1，只能装0.2的物品2。由此得一个解为[1,0.2,1,1]，其相应价值为22。尽管这不是一个可行解，但可以证明其价值是最优值的上界。因此，对于这个实例，最优值不超过22。 在实现时，由Bound计算当前节点处的上界。类Knap的数据成员记录解空间树中的节点信息，以减少参数传递调用所需要的栈空间。在解空间树的当前扩展节点处，仅要进入右子树时才计算上界Bound,以判断是否可将右子树剪去。进入左子树时不需要计算上界，因为上界预期父节点的上界相同。 三、回溯法实现代码： #include "stdafx.h" #include #include 河南科技大学 课程设计报告 课程名称：算法设计与分析 设计题目：罗密欧与朱丽叶迷宫求解问题 院系：电子信息工程学院 专业：计算机科学与技术 班级：计算机092班 学生姓名: 学号:09************ 起止日期: 2011年5月28日 - 2011年6月3日指导教师:孙士保、张明川、冀治航 课程设计题目罗密欧与朱丽叶的迷宫问题 姓名*** 学号091040602** 班级092班系别电子信息工程学院专业计算机科学与技术 组别1人组长*** 组员*** 指导教师姓名孙士保、张明川、冀治航 课程设计目的 进一步巩固C程序设计和算法设计与分析的基础知识，提升结构化程序、模块化程序设计的方法和能力，深入理解数据结构的基本理论，掌握数据存储结构的设计方法，掌握基于数据结构的各种操作的实现方法，训练对基础知识和基本方法的综合运用能力，增强对算法的理解能力，提高软件设计能力。在实践中培养独立分析问题和解决问题的作风和能力。 设计环境1. PC兼容机 2．Windows 2000/XP操作系统3．TC集成开发环境或其他C语言开发环境 课程设计要求和任务要求：1．熟练掌握回溯法，能够利用回溯法解决实际问题； 2．使用文件进行存储和管理。程序启动时可从文件中读取信息，或从键盘输入信息；运行过程中也可对文件进行存取；退出前可选择将部分信息保存 到文件中； 3．不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。 4．对系统进行功能模块分析、画出总流程图和各模块流程图； 5．用户界面要求使用方便、简洁明了、美观大方、格式统一。所有功能可以反复使用，最好使用菜单； 6．通过命令行相应选项能直接进入某个相应菜单选项的功能模块； 7．所有程序需调试通过。 任务：完成罗密欧与朱丽叶的迷宫问题.设计内容包括： 1．确定能对给定的任何位置的罗密欧都能够找到一条通向朱丽叶的路线； 2．程序能够演示一条罗密欧找到朱丽叶的路线过程等。 课程设计工作进度计划 序号起止日期工作内容 1 下发任务书，分组，选定课题，查阅相关资料 2 总体设计，划分模块 3 编制源程序 4 上机调试，修改、完善系统 5 程序检查 6 撰写说明书 深圳大学实验报告 课程名称：算法分析与复杂性理论 实验项目名称：八皇后问题 学院：计算机与软件学院 专业：软件工程 指导教师：杨烜 报告人：学号：班级：15级软工学术型 实验时间：2015-12-08 实验报告提交时间：2015-12-09 教务部制 一．实验目的 1.掌握选回溯法设计思想。 2.掌握八皇后问题的回溯法解法。 二．实验步骤与结果 实验总体思路： 根据实验要求，通过switch选择八皇后求解模块以及测试数据模块操作，其中八皇后模块调用摆放皇后函数模块，摆放皇后模块中调用判断模块。测试数据模块主要调用判断模块进行判断，完成测试。用一维数组保存每行摆放皇后的位置，根据回溯法的思想递归讨论该行的列位置上能否放置皇后，由判断函数Judge()判断，若不能放置则检查该行下一个位置。相应结果和过程如下所示（代码和结果如下图所示）。 回溯法的实现及实验结果： 1、判断函数 代码1： procedure BTrack_Queen(n) 皇后问题 2.测试数据0.退出**"< 1、实验目的 （1）掌握回溯法设计策略。 （2）通过0-1背包问学习回溯法法设计技巧2.实验内容 源程序： #include } if(cw+w[i]<=c) //搜索左子树 { cw+=w[i]; cp+=p[i]; Backtrack(i+1); cp-=p[i]; cw-=w[i]; } if(bound(i+1)>bestp)//搜索右子树 Backtrack(i+1); } double Knapsack (double pp[],double ww[],double d) { int i; double TP=0,TW=0; cw=0.0;cp=0.0;bestp=0.0;//计算所有物品的重量及价值 for(i=1;i<=n;i++) { TP=TP+pp[i]; TW=TW+ww[i]; } if(TW<=d)//所有物品装入背包 bestp=TP; else { Backtrack(1); } return bestp; }; int main() { 算法设计与分析课程设计罗密欧与朱丽叶的迷宫问题设计分析测试报告 程序算法设计说明书 一、前言 1、题目：罗密欧与朱丽叶的迷宫问题。 罗密欧与朱丽叶身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8 个方向进入未封闭的房间。罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计和实现一个算法帮助罗密欧找出这些道路。 2、程序编制环境相关说明 硬件：装有windows操作系统的计算机 软件：Visual C++ 2008 二、程序主要算法设计分析说明 1、算法设计思路 用回溯法解迷宫问题时，用排列树表示其解空间比较合适。可行性约束函数减去不满足约束条件（x,y,z）已越界的子树。在排列树的第i+1层节点z处用board[z][x][y]记载所在的房间。当bool stepok(int x,int y,int z)返回为false时，以z为根的子树中所有子树都不满足约束条件，因而该子树中的解均为不可行解，故可将该子树剪枝。 算法调用递归方法void backtrack(int dep,int x,int y,int di)实现回溯搜索。void backtrack (int dep,int x,int y,int di)搜索排列树中第dep层子树。数组board[0][x][y]记录排列树中的节点信息。dirs记录当前节点对应的转弯数， best记录最少转弯数。 在算法void backtrack (int dep,int x,int y,int di)中，当i>n时，算法搜索至叶节点，其相应的转弯数dirs。如果dirs>best,则表示当前解优于最优解，此时更新best。当i≤n时，当前扩展节点位于是排列树的第i-1层。此时算法选择下一个要搜索的方向，以深度优先的方式递归地对相应子树进行搜。对于不满足上界约束的节点，则减去相应子树。 算法void backtrack (int dep,int x,int y,int di)动态地生成问题的解空间树。 时间复杂度为整个状态空间，即迷宫大小，O(m*n) 算法分析与设计实验报告第六次实验 附录： 完整代码（回溯法） //回溯算法递归回溯n皇后问题#include { friend int nQueen(int); //定义友元函数，可以访问私有数据 private: bool Place(int k); //判断该位置是否可用的函数 void Backtrack(int t); //定义回溯函数 int n; //皇后个数 int *x; //当前解 long sum; //当前已找到的可行方案数 }; int main() { int m,n; for(int i=1;i<=1;i++) { cout<<"请输入皇后的个数："; //输入皇后个数 cin>>n; cout<<"皇后问题的解为："< 实验4 回溯法解0-1背包问题 一、实验要求 1．要求用回溯法求解0-1背包问题； 要求交互输入背包容量，物品重量数组，物品价值数组；2．要求显示结果。3． 二、实验仪器和软件平台 仪器：带usb接口微机 软件平台：WIN-XP + VC++ 三、实验源码 #include \ #include { bag[i].flag=0; bag[i].kk=i; bag[i].fl=*bag[i].v/bag[i].w; } }void Backtrack(int i){cw+=bag[i].w;if(i>=n) <=c) lag=1; cp+=bag[i].v; Backtrack(i+1); cw-=bag[i].w; cp-=bag[i].v; } if(Bound(i+1)>bestp)lag=0; Backtrack(i+1); }}<=cleft){; b+=bag[i].v; i++; } /bag[i].w * cleft; return b; } void Knapsack() k]=bag[k].flag; lag*bag[k].v; //价值累加 } cout< 课程设计说明书 课程名称＿＿软件专题训练＿＿＿＿ 题目罗密欧与朱丽叶迷宫求解问题＿ 院系＿电子信息工程学院计算机系＿ 班级＿计算机科学与技术103班＿＿ 学生姓名＿＿＿＿＿＿＿＿＿＿＿ 指导教师＿孙士保、冀治航＿＿ 日期＿ 2012.5.21—2012.5.27＿＿ 课程设计任务书 课程名称＿＿算法设计与分析＿＿＿ 题目＿罗密欧与朱丽叶的迷宫问题 院系＿电子信息工程学院计算机系＿ 班级＿＿＿计算机103班＿＿＿＿＿ 学生姓名＿＿＿＿魏鹏超＿＿＿＿＿＿ 指导教师＿孙士保、冀治航＿＿ 日期＿ 2012.5.21—2012.5.27＿＿ 河南科技大学 课程设计报告 课程名称＿＿软件专题训练＿＿＿＿ 题目＿罗密欧与朱丽叶的迷宫问题 院系：电子信息工程学院计算机系 专业：计算机科学与技术 班级：计算机10级 学生姓名:学号: 起止日期: 2012年5月21日~ 2012年5月27日指导教师:孙士保、冀治航 目录 第一章需求分析 (4) 1.1课程设计题目 (4) 1.2 课程设计任务及要求 (4) 1.3运行环境及开发工具 (4) 第二章概要设计 (5) 2.1系统流程图 (5) 第三章详细设计 (6) 3.1函数划分 (6) 3.2函数之间的关系 (6) 第四章系统调试与操作说明 (7) 4.1系统调试及操作说明 (7) 第五章课程设计总结体会 (8) 5.1课程设计总结 (8) 5.2致谢 (8) 5.3参考文献 (8) 第一章需求分析 1.1课程设计题目 罗密欧与朱丽叶的迷宫问题 1.2 课程设计任务及要求 1、对于给定的罗密欧与朱丽叶的迷宫，编程计算罗密欧通向朱丽 叶的所有最少转弯道路 2、程序能够演示一条罗密欧找到朱丽叶的路线过程等 罗密欧与朱丽叶的迷宫。罗密欧与朱丽叶身处一个m×n的迷宫中，如图所示。每一个方格表示迷宫中的一个房间。这m×n个房间中有一些房间是封闭的，不允许任何人进入。在迷宫中任何位置均可沿8 个方向进入未封闭的房间。罗密欧位于迷宫的(p，q)方格中，他必须找出一条通向朱丽叶所在的(r，s)方格的路。在抵达朱丽叶之前，他必须走遍所有未封闭的房间各一次，而且要使到达朱丽叶的转弯次数为最少。每改变一次前进方向算作转弯一次。请设计一个算法帮助罗密欧找出这样一条路。 1.3运行环境及开发工具 硬件：装有windows操作系统的计算机 软件：Visual C++6.0 算法分析与设计实验报告 实验内容：N皇后问题 实验时间：2013.12.3 姓名：杜茂鹏 班级：计科1101 学号：0909101605 一、实验内容及要求 在n×n格的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。 二、实验目的 1.巩固和加深对回溯法的理解 2.了解递归和迭代法在回溯法中的应用 三、算法分析 1.理解皇后不被攻击的条件：n后问题等价于在n*n格的棋盘上放置n个皇后，任何两个皇后不能放在同一行或同一列或同一斜线上。 2.算法模块简要分析 用数组存储皇后的位置，将i设置为0. Int place(*x,n) :数组x[] 用来表示列数，n为皇后个数，用来判断皇后是否被攻击，判断的条件是（x[i]-x[n]==i-n||x[i]-x[n]==n-i||x[i]==x[n]）即用来判断“同一行或同一列或同一斜线上”。 Int print(*x,n):打印皇后解的空间。 Int iniprint(*x,n):初始化打印函数，相当于对棋盘初始化。将可以放皇后的位置记为“1”，不放皇后的位置记为“0”。 Int Nqueen(int n):n皇后问题求解，如果满足一组可行解，sum++。Int i=0,如果x[i]>=n的时候即进行下一行，i++；当i=n时， sum++；输出该组可行解的个数和位置的矩阵。并且i--，回溯到上一层继续搜索可行解。 四、运行结果及分析 1、三皇后没有可行解 2、 2.4个皇后有2个可行解 3.5皇后有10个可行解 五、源代码 #include 回溯法是一个既带有系统性又带有跳跃性的搜索算法。它在包含问题的所有解的解空间树中按照深度优先的策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一节点时，总是先判断该节点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该节点为根的子树的系统搜索，逐层向其原先节点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。 运用回溯法解题通常包含以下三个步骤： ?针对所给问题，定义问题的解空间； ?确定易于搜索的解空间结构； ?以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索； 在0／1背包问题中，容量为M的背包装载。从n个物品中选取装入背包的物品，物品i的重量为Wi，价值为Pi。最佳装载指装入的物品价值最高，即∑PiXi(i=1..n)取最大值。约束条件为∑WiXi ≤M且Xi∈[0,1](1≤i≤n)。 在这个表达式中，需求出Xi的值。Xi=1表示物品i装入背包，Xi＝0表示物品i不装入背包。 ?即判断可行解的约束条件是：∑WiXi≤M（i=0..n），Wi>0,Xi∈[0,1](1≤i≤n) ?目标最大值：max∑PiXi（i=0..n-1）,Pi>0,Xi=0或1（0≤i 回溯法解八皇后问题 在N * N 格的棋盘上放置彼此不受攻击的N 个皇后。N个皇后问题等价于在N * N 格的棋盘上放置N 个皇后，任何2个皇后不在同一行或同一列或同一斜线上。当N等于8，就是著名的八皇后问题。 此问题是通过C语言程序编写的，在Turboc环境下完成实现的。输出结果见（输出结果。TXT文件） 详细代码为： /*///////////////////////////////////////////////////////////////////// /// /////The programming is a complex problem about the ways of queens./////// /////Programmer: Luo Xiaochun /////// /////Completed date: 2007.12 //////// /////V ersion number: Turboc 2.0 //////// /////////////////////////////////////////////////////////////////////// /*/ #include 用回溯法解决3种可选择物品的0-1背包问题当n=3时，其解空间是 {（0,0,0）（0,1,0），（0,0,1），（1,0,0），（0,1,1），（1,0,1），（1,1,0），（1,1,1）}n=3时的0-1背包问题： w=[16,15,15]p=[45,25,25]c=30 开始时，Cr=C=30，V=0，A为唯一活结点，也是当前扩展结点 扩展A，先到达B结点 Cr=Cr-w1=14，V=V+v1=45 此时A、B为活结点，B成为当前扩展结点 扩展B，先到达D Cr Cr=30，V=0，活结点为A、C，C为当前扩展结点 扩展C，先到达F Cr=Cr-w2=15，V=V+v2=25，此时活结点为A、C、F，F成为当前扩展结点扩展F，先到达L Cr=Cr-w3=0，V=V+v3=50 L是叶结点，且50>45，皆得到一个可行解x=(0,1,1)，V=50 L不可扩展，成为死结点，返回到F 再扩展F到达M M是叶结点，且25<50，不是最优解 M不可扩展，成为死结点，返回到F F没有可扩展结点，成为死结点，返回到C 再扩展C到达G Cr=30，V=0，活结点为A、C、G，G为当前扩展结点 扩展G，先到达N，N是叶结点，且25<50，不是最优解，又N不可扩展，返回到G 再扩展G到达O，O是叶结点，且0<50，不是最优解，又O不可扩展，返回到G G没有可扩展结点，成为死结点，返回到C C没有可扩展结点，成为死结点，返回到A A没有可扩展结点，成为死结点，算法结束，最优解X=(0,1,1)，最优值 V=50 算法分析与设计论文论文题目：回溯法解迷宫问题 作者姓名陈相艺 任课教师王松 学院班级计算机学院计自1101班 学号201126100404 提交日期2013年6月10日 回溯法解迷宫问题 陈相艺 （计算机+自动化1101 201126100404） 摘要：迷宫的存储结构以二维数组来存储，用0，1表示通或不通。表面上似乎迷宫问题是一种特殊问题的解决方法，其实迷宫问题是一种特殊形式图的问题，因此，迷宫总量可转化为图的问题来解决。设计一个计算机程序对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论.本文采用回溯法求解迷宫路径，算法用到数据结构中的栈。 关键词：迷宫；二位数组；回溯法；栈；矩阵。 1.前言 迷宫实验是取自心理学的一个古典实验.在该实验中,把一只老鼠从一个无顶大盒子放入,在盒中设立了许多墙,对行进方向形成了多处阻挡.盒子仅有一个出口处放置一快奶酪,吸引老鼠在迷宫中寻找道路以到达出口.对同一老鼠重复进行上述实验,一直到老鼠从入口到出口,而不走错一步.老鼠经多次试验终于得到它学习走通迷宫的线路.设计一个计算机程序对任意设定的迷宫,求出一条从入口到出口的通路,或得出没有通路的结论. 回溯法(探索与回溯法)是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。 2.迷宫问题的算法思想及研究 迷宫问题中，在寻找路径时，采用的方法通常是：从入口出发，沿某一方向向前试探，若能走通，则继续向前进；如果走不通，则要沿原路返回，换一个方向再继续试探，直到所有可能的能跟都试探完成为止。为了保证在任何位置上都能沿原路返回（回溯），要建立一个后进先出的栈来保存从入口到当前位置的路径。而且在求解迷宫路径中，所求得的路径必须是简单路径。即在求得的路径上不能有重复的同一块通道。 为了表示迷宫，设置一个数组，其中每个元素表示一个方块的状态，为0时表示对应方块是通道，为1时表示对应方块为墙，数组如下所示： int mg[10][10] = { {1,1,1,1,1,1,1,1,1,1}, {1,0,0,1,1,0,0,1,0,1}, {1,0,0,1,0,0,0,1,0,1}, {1,0,0,1,0,1,1,0,0,1}, {1,0,1,1,1,0,0,0,0,1}, {1,0,0,0,1,0,0,0,0,1}, {1,0,1,0,0,0,1,0,0,1}, {1,0,1,1,1,0,1,1,0,1}, {1,1,0,0,0,0,0,0,0,1}, {1,1,1,1,1,1,1,1,1,1}}; （可根据自己喜好，改变迷宫的大小和通道安排。） 对于迷宫中每个方块，都有上下左右四个方块相邻，第i行第j列的当前方块的位置为(i,j)， 算法分析与设计实验报告第三次附加实验 附录： 完整代码（回溯法） //回溯算法递归回溯n皇后问题#include { friend int nQueen(int); //定义友元函数，可以访问私有数据 private: bool Place(int k); //判断该位置是否可用的函数 void Backtrack(int t); //定义回溯函数 int n; //皇后个数 int *x; //当前解 long sum; //当前已找到的可行方案数 }; int main() { int m,n; for(int i=1;i<=1;i++) { cout<<"请输入皇后的个数："; //输入皇后个数 cin>>n; cout<<"皇后问题的解为："<动态规划与回溯法解决0-1背包问题
算法分析与程序设计动态规划及回溯法解背包问题
迷宫求解问题资料
回溯法之N皇后问题(C语言)
回溯法和分支限界法解决0-1背包题
用回溯法解决0-1背包问题
算法实验报告：罗密欧与朱丽叶迷宫求解
算法实验 递归回溯解八皇后问题
回溯算法之0-1背包问题
迷宫问题
回溯法实验(n皇后问题)
回溯法解0 1背包问题实验报告
罗密欧与朱丽叶迷宫求解问题
n皇后问题算法实验报告
回溯法解决01背包问题
回溯法解八皇后问题
(原创精品)n=3时的0-1背包问题(回溯法)
回溯法解迷宫问题
回溯法实验(n皇后问题)(迭代法)
相关主题
文本预览