资源描述：
《算法设计与分析--回溯法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、回溯算法的应用课程名称：算法设计与分析院系：计算机科学与信息工程学院学生姓名：学号：201003010079专业班级：计算机科学与技术（信息技术）11-1指导教师：冯慧玲2013年12月27口回溯算法的应用扌商要：回溯法是一个既带有系统性又带有跳跃性的的搜索算法。它在包含问题的所有解的解空间树屮，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树,继续按深度优先的策略进行搜索。回溯法在用來
2、求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一个解就可以结束。这种以深度优先的方式系统地搜索问题的解的算法称为回溯法，它适用于解一些组合数较大的问题。在做题吋，有时会遇到这样一•类题目，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此时可以考虑用回溯法解决此类问题。回溯法的优点在于其程序结构明确，可读性强，易于理解，而且通过对问题的分析可以大大提高运行效率。0/1背包问题是一个经典的问题，我们可以采用多种算法去求解0/1背包问题，比如动态规划法、分支限界法、贪心
3、算法、回溯法。在这里我们采用回溯法解决这个问题。关键词：回溯法0/1背包问题深度优先搜索节点第1章绪论41.1回溯算法的背景知识41.2回溯法的前景意义4第2章回溯算法的理论知识52.1问题的解空间树52.2回溯算法的一般性描述6第3章0/1背包问题73.1问题描述73.2问题分析73.3算法设计83.4测试结果与分析io第4章n皇后问题114.1问题描述114.2问题分析114.3算法设计124.4测试结果与分析13第5章结论14参考文献15附件15第1章绪论1.1回溯算法的背景知识回溯算法是尝试搜索算法中最为基本的算法，在递归算法中，其存在的
4、意义是在递归知道可解的最小问题后，逐步返回原问题的过程。实际上是一个类似于枚举的搜索尝试方法，他的主题思想是在搜索尝试的过程中寻找问题的解，当发现不满足条件时就回溯返冋，尝试别的路径。简单的说就是：从问题的某一种初始状态出发，依次搜寻每一种可能到达的情况，当走到这条路的“尽头”时，回过头到上一个情况，看这个情况是否还有没有走过的路,依次进行下去，直到遍历完所有的情况。回溯法实际上是一种深度优先搜索的方式。对于回溯法解决的问题，通常将其解空间组织成图或者树的形式。对于用冋溯法求解的问题，首先要将问题进行适当的转化，得出状态空间树。这棵树的每条完整路
5、径都代表了一种解的可能。通过深度优先搜索这棵树，枚举每种可能的解的情况；从而得岀结果。但是，回溯法中通过构造约束函数，可以大大提升程序效率，因为在深度优先搜索的过程中，不断的将每个解与约束函数进行对照从而删除一些不可能的解，这样就不必继续把解的剩余部分列出从而节省部分时间。1.2回溯法的前景意义在做题时，有时会遇到这样一类题口，它的问题可以分解，但是又不能得出明确的动态规划或是递归解法，此吋可以考虑用冋溯法解决此类问题。冋溯法的优点在于其程序结构明确，可读性强，易于理解，而H通过对问题的分析可以大大提高运行效率。通过运用回溯法，可以解决很多问题，
6、譬如我们所熟知的“八皇后问题”、“0/1背包问题”，这只是在教学阶段中的运用，在实际运用中回溯法也能起到很大的作用。回溯法适用于解决难以归纳一般规律解法的问题，其适用范围广，灵活性大，在解一些列举方法的问题吋尤其可用。但是，其缺点也是明显的，即吋间复杂度较大；因此在采用时我们应该因情况的不同而做出不同的选择。第2章回溯算法的理论知识2.1问题的解空间树对于0-1背包问题。给定n个物品，一个容量为w的背包，每个物品由重量叫和价值百描述(1=1,2,3,・n),每个物品可以选择放入或不放入背包，试求最佳方案：充分(不要求全部)利用背包的容量，尽可能装
7、入总价值量大的物品。n件物品的取舍数字化为：取标识为1,不取标识为0。则搜索的空间为n元一维数组(x,x,x,…，x,x),其值从(0,0,0,…，0,0)、(0,0,0,…，0,1)、(0,0,0,…，1,0)、(0,0,0,…，1,1)、…、(1,1,1,…，1,1)o这就是一棵子集数。例如：当n二3吋，其解空间可由2彳个长度为3的有序序列组成：{(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1)}其中，0表示不装入，1表示装入。上述解空间可以利用如下图所示的完全二叉
8、树表示：图2.1完全二叉树冋溯法是在包含问题的所有解的解空间树中，按照深度优先的策略，从根节点出发搜索解空间树。算法搜索至解空间树的任一
