文档介绍：:..《算法设计与分析》课程实验报告专业:一-班级: 学号: 姓名: 日期■■2013年12月11日、实验题目回溯法二、。、解向量、显式约朿条件、隐式约朿条件以及子集树与排列树的递归算法结构等内容。。三、,其屮集装箱i的重量为wi,且Ewi<Cl+C2。装载问题要求确定是否有一个合理的装载方案可将这个集装箱装上这2艘轮船。如果有,找出一种装载方案。。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的祺子。n后问题等价于在nXn格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。。用这些颜色为阁G的各顶点着色,每个顶点着一种颜色。是否有一种着色法使G屮每条边的2个顶点着不同颜色。这个问题是阁的m可着色判定问题。!L>实验步骤1、装载问题【问题分析】例如,当n=3,cl=c2=50,Mw=[l0,40,40]时,可将集装箱1和集装箱2装上一艘轮船,而将集装箱3装在第二艘轮船;如果w=[20,40,40],则无法将这3个集装箱都装上轮船。容易证明,如果一个给定的装载问题有解,则采用如T的策略可以得到最优装载方案。••艘轮船尽可能装满。。将第一艘轮船尽可能的装满等价于选取全体集装箱的子集,使该子集屮集装箱的重兑之和最接近cl。因此,等价于一个特殊的0-1背包问题。因此是一棵子集树。max(wlxl+w2x2+...+wixi)(wlxl+w2x2+•…+wixi)<=cl;xi@{0,1},l<=i<=n用回溯法解装载问题时,用子集树表示其解空间显然是最合适的。可行性约束函数可剪去不满足约束条件((wlxl+w2x2+...+wixi)<=cl)的子树。在子集树的第j+1层的节点Z处,用cw记当前的装载重量,即cw=(wlxl+w2x2+...+wjxj〉,当cw〉cl时,以Vf点Z为根的子树中所有节点都不满足约束条件,因而该子树中解均为不可行解,故可将该子树剪去。下而的解装载问题的回溯屮,算法MaxLoading返回不超过C的最大子集和,但并未给出达到这个最大子集和的相应子集。稍后加以完善。算法Maxloading调用递归函数Backtrack(1)实现冋溯搜索。Backtrack(i)搜索子集树中第i层子树。类Loading的数据成语。记录子集树中结点信息,以减少传给Backtrack的参数。cw记录当前结点所相应的装载重量,bestw记录当前最大装载重量。在算法Backtrack中,当i>n时,算法搜索至叶节点,其相应的装载重量为cw。如果cw〉bestw,则表示当前解优丁•当前最优解,此时应更新bestw。当i<=n时,当前扩展结点Z是子集树巾的内部节点。该结点有x[i]=l和x[i]=0两个儿子结点。其左儿子结点表示x[i]=l的情形,仅当cw+w[i]<=c吋进入左子树,对左子树进行递归搜索。其右儿子结点表示x[i]=o的情形。由于可行