算法设计实验报告

华北电力大学 实实 验验 报报 告告 实验名称实验名称 算法设计与分析算法设计与分析综合实验综合实验 课程名称课程名称 算法设计与分析算法设计与分析 专业班级 学生姓名 学 号 成 绩 指导教师 实验日期 华 北 电 力 大 学 实 验 报 告 第 页 共 页 综合实验一综合实验一 分治策略分治策略 归并排序归并排序 一 实验目的及要求一 实验目的及要求 归并排序是一个非常优秀的排序方法 也是典型的分治策略的典型应用 实验要求 1 编写一个模板函数 template MergeSort T a int n 以及相应 的一系列函数 采用分治策略 对任意具有 bool operator const T比较运 算符的类型进行排序 2 与 STL 库中的函数 std sort 进行运行时间上的比较 给出比较结果 如 动 态生成 100 万个随机生成的附点数序列的排序列问题 给出所用的时间比较 二 所用仪器 设备二 所用仪器 设备 计算机 Visual C 软件 三 实验原理三 实验原理 分治原理 分治算法的基本思想是将一个规模为 N 的问题分解为 K 个规模较小的子问题 这 些子问题相互独立且与原问题性质相同 求出子问题的解 就可得到原问题的解 当我 们求解某些问题时 由于这些问题要处理的数据相当多 或求解过程相当复杂 使得直 接求解法在时间上相当长 或者根本无法直接求出 对于这类问题 我们往往先把它分 解成几个子问题 找到求出这几个子问题的解法后 再找到合适的方法 把它们组合成 求整个问题的解法 如果这些子问题还较大 难以解决 可以再把它们分成几个更小的 子问题 以此类推 直至可以直接求出解为止 这就是分治策略的基本思想 归并原理 归并排序是建立在归并操作上的一种有效的排序算法 该算法是采用分治法 Divide and Conquer 的一个非常典型的应用 将已有序的子序列合并 得到完全有序的序列 即先使每个子序列有序 再使子序列段间有序 若将两个有序表合并成一个有序表 称 为二路归并 四 实验方法与步骤四 实验方法与步骤 归并过程为 比较 a i 和 a j 的大小 若 a i a j 则将第一个有序表中的元素 a i 复制到 r k 中 并令 i 和 k 分别加上 1 否则将第二个有序表中的元素 a j 复制到 r k 中 并令 j 和 k 分别加上 1 如此循环下去 直到其中一个有序表取完 然后再将另一个有 序表中剩余的元素复制到 r 中从下标 k 到下标 t 的单元 归并排序的算法我们通常用递 归实现 先把待排序区间 s t 以中点二分 接着把左边子区间排序 再把右边子区间排 序 最后把左区间和右区间用一次归并操作合并成有序的区间 s t 实现时间计量 define CLOCK T DEFINED srand unsigned time 0 定义一数组 a n 对每一个赋予一值 a i rand 得到随即数 duration double finish start CLOCKS PER SEC start clock 将系统时间赋予 Start 以便以后进行比较 std sort b b 1000 系统执行 1000 个数据 Finish Start 为最终结果 五 实验结果与数据处理 实验结果截图 华 北 电 力 大 学 实 验 报 告 第 页 共 页 华 北 电 力 大 学 实 验 报 告 第 页 共 页 实验代码 include include include include include using namespace std template void MergSort Type a int n Type b new Type n int s 1 while s n MergPass a b s n s s MergPass b a s n s s template void MergPass Type x Type y int s int n int i 0 while i n 2 s Merg x y i i s 1 i 2 s 1 i i 2 s 华 北 电 力 大 学 实 验 报 告 第 页 共 页 if i s n Merg x y i i s 1 n 1 else for int j i j n 1 j y j x j template void Merg Type c Type d int l int m int r int i l j m 1 k l while i m q r q d k c q else for int q i q m q d k c q float randf float base float up return rand int up base RAND MAX float RAND MAX 产生随机数 void printArray float a int N for int i 0 i0 cout a i endl else cout a i void main int ArrayLen 5 cout 请输入元素个数 ArrayLen float array new float ArrayLen float arrays new float ArrayLen float mn ene 华 北 电 力 大 学 实 验 报 告 第 页 共 页 printf 数组已建立 n srand unsigned time NULL 设置随机数的 seed for int i 0 i ArrayLen i mn float rand 产生小数 ene randf 1 10000 mn arrays i ene array i ene cout 需要排序的归并数组 n printArray array ArrayLen int flag 1 while flag 0 cout n 输入需要显示的排序方法 endl cout 1 归并排序 2 std 排序 0 退出 flag switch flag case 0 break case 1 clock t s 0 e 0 s clock MergSort array ArrayLen e clock cout 排序后的序列为 endl printArray array ArrayLen cout nMergSort 运行了 e s ms endl break case 2 clock t start1 0 end1 0 start1 clock std sort end1 clock printArray array ArrayLen cout nstd sort 运行了 end1 start1 ms sFileName sFileName1 ifstream fin sFileName char ch 4 fin getline ch 4 int n1 atoi ch cout 节点数目 n1 n n1 this t new THaffmanNode 2 n1 1 this nNext n1 char ch1 for int i 0 i n1 i fin get ch1 t i c ch1 fin ignore 100 fin getline ch 4 t i f atoi ch for int i 0 i n i cout t i c t i f endl for int i 0 i 2 THaffmanNode nn nr nl nl PQ top PQ pop nr PQ top PQ pop nn f nl f nr f nn l nl idx nn r nr idx nn idx nNext t nl idx p nn idx t nr idx p nn idx t nn idx nn PQ push nn else t 2 n 2 p 1 break Huffman Huffman void void Huffman OutputTree for int i 0 i 2 n 1 i cout 权重 t i f cout 左孩子 t i l cout 右孩子 t i r cout 父节点 t i p cout 在数组的位置 t i idx endl 现在数组中存的是哈弗曼数 void Huffman OutputCode 用 stack 来依次记录各编码的 0 1 编码 std stack int std list sk THaffmanNode ntemp ntemp1 华 北 电 力 大 学 实 验 报 告 第 页 共 页 for int i 0 i n i ntemp t i while ntemp p 1 ntemp1 t ntemp p if t ntemp1 l idx ntemp idx sk push 0 ntemp ntemp1 else sk push 1 ntemp ntemp1 int i1 sk size cout t i f for int i 0 i i1 i cout sk top sk pop cout endl 实验结果截图 综合实验三综合实验三 用回溯方法求解用回溯方法求解 n n 后问题后问题 一 实验目的及要求一 实验目的及要求 问题 对任意给定的 n 求解 n 后问题 华 北 电 力 大 学 实 验 报 告 第 页 共 页 具体要求 1 封装 n 后问题为类 编写以下两种算法进行求解 1 递归回溯方法 2 迭代回溯方法 选 2 对任意给定的 n 要求输出其解向量 所有解 并输出其解数 3 构造 n 后问题的解数表格 由程序自动生成 n 后数解数第一个解 42 2 4 1 3 5 6 二 所用仪器 设备二 所用仪器 设备 计算机 Visual C 软件 三 实验原理三 实验原理 回溯原理 回溯算法也叫试探法 它是一种系统地搜索问题的解的方法 回溯算法的基本思想 是 从一条路往前走 能进则进 不能进则退回来 换一条路再试 用回溯算法解决问 题的一般步骤为 1 定义一个解空间 它包含问题的解 2 利用适于搜索的方法组织解空间 3 利用深度优先法搜索解空间 4 利用限界函数避免移动到不可能产生解的子空间 问题的解空间通常是在搜索问题的解的过程中动态产生的 这是回溯算法的一个重 要特性 四 实验方法与步骤四 实验方法与步骤 n 后问题等于在 n n 格的棋盘上放置 n 个皇后 任何 2 个皇后不放在同一行或同 一列或同一斜线上 即规定每一列放一个皇后 不会造成列上的冲突 当第 i 行被某个 皇后占领后 则同一行上的所有空格都不能再放皇后 要把以 i 为下标的标记置为被占 领状态 K 第 K 个皇后 也表示第 K 行 X i 第 K 个皇后在第 K 行的 第 i 列 皇后 k 在第 k 行第 x k 列时 x i x k 时 两皇后在同一列上 abs x i x k abs i k 时 两皇后在同一斜线上 两种情况两皇后都可相互攻击 返回 false 表示不符合条件 五 实验结果与数据处理五 实验结果与数据处理 实验结果截图 华 北 电 力 大 学 实 验 报 告 第 页 共 页 实验代码 include include class Queen friend int nQueen int private bool Place int k void Backtrack int t int n x 当前解 long sum 当前已找到的可行方案数 bool Queen Place int k for int j 1 jn sum 达到叶结点 for int i 1 i n i cout x i cout endl for i 1 i n i for int j 1 j n j if x i j cout else cout cout endl cout endl else for int i 1 i n i 搜索子结点 x t i 进入第 i 个子结点 if Place t Backtrack t 1 int nQueen int n Queen X 初始化 X X n n X sum 0 int p new int n 1 for int i 0 i n i p i 0 X x p X Backtrack 1 对整个解空间回溯搜索 delete p return X sum void main 华 北 电 力 大 学 实 验 报 告 第 页 共 页 int a 0 b 0 cout 欢迎进入皇后问题 endl int flag 1 while flag cout 请输入皇后数 a b nQueen a cout 方案个数 b endl cout 是否继续 1 为是 0 为否 flag 综合实验四综合实验四 背包问题的贪心算法背包问题的贪心算法 一 实验目的及要求一 实验目的及要求 问题 给定如下 n 种物品的编号 及其价值 背包重量为 c 求最佳装包方案 才能使其 装入背包的价值最大 物品编号12 n 重量w 1 w 2 w n 价值v 1 v 2 v n 具体要求 将背包问题进行类的封装 能对任意给定的 n 种物品的重量 价值及背包限重 输出以上表格 或纵向输出 输出背包问题的解 本题要求采用 STL 库中的排序算法数据进行排序 二 所用仪器 设备二 所用仪器 设备 计算机 Visual C 软件 三 实验原理三 实验原理 贪心算法解决背包问题有几种策略 1 一种贪心准则为 从剩余的物品中 选出可以装入背包的价值最大的物品 利用这种规则 价值最大的物品首先被装入 假设有足够容量 然后是下一个价值最 大的物品 如此继续下去 这种策略不能保证得到最优解 例如 考虑 n 2 w 100 10 10 p 20 15 15 c 105 当利用价值贪婪准则时 获得的解为 x 1 0 0 这种方案的总价值为 2 0 而最优解为 0 1 1 其总价值为 3 0 2 另一种方案是重量贪心准则是 从剩下的物品中选择可装入背包的重量最小 的物品 虽然这种规则对于前面的例子能产生最优解 但在一般情况下则不一定能得到 最优解 考虑 n 2 w 10 20 p 5 100 c 2 5 当利用重量贪婪策略时 获得的解为 x 1 0 比最优解 0 1 要差 3 还有一种贪心准则 就是我们教材上提到的 认为 每一项计算 yi vi si 即该 项值和大小的比 再按比值的降序来排序 从第一项开始装背包 然后是第二项 依次 类推 尽可能的多放 直到装满背包 华 北 电 力 大 学 实 验 报 告 第 页 共 页 四 实验方法与步骤四 实验方法与步骤 首先计算每种物品单位重量的价值 Vi Wi 然后依贪心选择策略 将尽可能多的单 位重量价值最高的物品装入背包 若将这种物品全部装入背包后 背包内的物品总重量 未超出 C 则选择单位重量价值次高的物品 并尽可能多的装入背包 依此策略一直进 行下去 直到背包装满为止 采用贪婪准则 每次选择 p w 最大的物品放入背包 注意在这之前的计算每种物品单位重量的价值 Vi Wi 后 进行排序 五 实验结果与数据处理 实验截图 主要代码如下 include define M 4 struct node float no 编号 float value float weight float wweight 若是最后一个的用量 int flag Node M temp float Value curvalue 0 float Weight curweight 0 按性价比排序 void sort int i j for i 0 i M 1 i for j i 1 j M j if Node i value float Node i weight Node j value float Node j weight temp Node i 华 北 电 力 大 学 实 验 报 告 第 页 共 页 Node i Node j Node j temp 可切割装载方法 void load2 int i for i 0 i M i if Node i weight curweight Weight curvalue Node i value Node i weight t curweight Weight Node i flag 2 Node i wweight t else Node i flag 0 进行结果的输出 void putout int i printf 选中物品的编号和重量分别为 printf n r for i 0 i M i if Node i flag 1 printf 2f Node i no printf printf 2f Node i weight printf n r else if Node i flag 2 printf 2f Node i no printf printf 2f Node i wweight printf n r 华 北 电 力 大 学 实 验 报 告 第 页 共 页 printf n 总价值为 2f curvalue int main int i static int p printf 请输入物品的重量和价值 n for i 0 i M i printf 请输入第 d 个物品的重量和价值 i 1 scanf f f f printf n 请输入背包容积 scanf f sort load2 putout return 0 综合实验综合实验 六六 选做选做 0 10 1 背包问题的求解背包问题的求解 一 实验内容 一 实验内容 0 1 背包问题有多种解法 如动态规划方法 回溯方法 分枝限界方法等 对于同 一种问题 请参照教材中的算法 给出相应的程序实现 注 0 1 背包问题 给定种物品和一个容量为的背包 物品 的重量是 其价 nCii w 值为 背包问题是如何使选择装入背包内的物品 使得装入背包中的物品的总价值最 i v 大 其中 每种物品只有全部装入背包或不装入背包两种选择 二 所用算法的基本思想及复杂度分析 二 所用算法的基本思想及复杂度分析 1 动态规划法求解动态规划法求解 0 1 背包问题 背包问题 1 基本思想 令表示在前个物品中能够装入容量为的背包中的物品 jiV 1 nii 1 Cjj 的最大值 则可以得到如下动态函数 0 0 0 jViV 1 1 max 1 iii i wjvwjiVjiV wjjiV jiV 按照下述方法来划分阶段 第一阶段 只装入前 1 个物品 确定在各种情况下的背 包能够得到的最大价值 第二阶段 只装入前 2 个物品 确定在各种情况下的背包能够 华 北 电 力 大 学 实 验 报 告 第 页 共 页 得到的最大价值 以此类推 直到第个阶段 最后 便是在容量为的背包中 n CnV C 装入个物品时取得的最大价值 n 2 代码 include include using namespace std define N 100 最多可能物体数 struct goods 物品结构体 int sign 物品序号 int w 物品重量 int p 物品价值 a N bool m goods a goods b return a p a w b p b w int max int a int b return a b b a int n C bestP 0 cp 0 cw 0 int X N cx N int KnapSack2 int n goods a int C int x int V N 10 N for int i 0 i n i 初始化第 0 列 V i 0 0 for int j 0 j C j 初始化第 0 行 V 0 j 0 for i 1 i n i 计算第 i 行 进行第 i 次迭代 for j 1 j C j if j0 i if V i j V i 1 j x i 1 1 j j a i 1 w else x i 1 0 华 北 电 力 大 学 实 验 报 告 第 页 共 页 return V n C 返回背包取得的最大价值 int main goods b N printf 物品种数 n scanf d 输入物品种数 printf 背包容量 C scanf d 输入背包容量 for int i 0 i n i 输入物品 i 的重量 w 及其价值 v printf 物品 d 的重量 w d 及其价值 v d i 1 i 1 i 1 scanf d d b i a i int sum2 KnapSack2 n a C X 调用动态规划法求 0 1 背包问题 printf 动态规划法求解 0 1 背包问题 nX for i 0 i n i cout X i 输出所求 X n 矩阵 printf 装入总价值 d n sum2 for i 0 i n i a i b i 恢复 a N 顺序 3 运行结果 4 复杂度分析 动态规划法求解 0 1 背包问题的时间复杂度为 CnOnT 华 北 电 力 大 学 实 验 报 告 第 页 共 页 2 回溯法求解回溯法求解 0 1 背包问题 背包问题 1 基本思想 回溯法 为了避免生成那些不可能产生最佳解的问题状态 要不断地利用限界函数 bounding function 来处死那些实际上不可能产生所需解的活结点 以减少问题的计算量 这种具有限界函数的深度优先生成法称为回溯法 对于有 n 种可选物品的 0 1 背包问题 其解空间由长度为 n 的 0 1 向量组成 可用子 集数表示 在搜索解空间树时 只要其左儿子结点是一个可行结点 搜索就进入左子树 当右子树中有可能包含最优解时就进入右子树搜索 2 代码 include include using namespace std define N 100 最多可能物体数 struct goods 物品结构体 int sign 物品序号 int w 物品重量 int p 物品价值 a N bool m goods a goods b return a p a w b p b w int max int a int b return an 1 if bestP cp for int k 0 k n k X k cx k 存储最优路径 bestP cp return bestP if cw a i w C 进入左子树 cw cw a i w cp cp a i p cx a i sign 1 装入背包 华 北 电 力 大 学 实 验 报 告 第 页 共 页 BackTrack i 1 cw cw a i w cp cp a i p 回溯 进入右子树 cx a i sign 0 不装入背包 BackTrack i 1 return bestP int KnapSack3 int n goods a int C int x for int i 0 i n i x i 0 a i sign i sort a a n m 将各物品按单位重量价值降序排列 BackTrack 0 return bestP int main goods b N printf 物品种数 n scanf d 输入物品种数 printf 背包容量 C scanf d 输入背包容量 for int i 0 i n i 输入物品 i 的重量 w 及其价值 v printf 物品 d 的重量 w d 及其价值 v d i 1 i 1 i 1 scanf d d b i a i int sum3 KnapSack3 n a C X 调用回溯法求 0 1 背包问题 printf 回溯法求解 0 1 背包问题 nX for i 0 i n i cout X i 输出所求 X n 矩阵 printf 装入总价值 d n sum3 for i 0 i n i a i b i 恢复 a N 顺序 3 运行结果 华 北 电 力 大 学 实 验 报 告 第 页 共 页 4 复杂度分析 最不理想的情况下 回溯法求解 0 1 背包问题的时间复杂度为 由 2 n OnT 于其对蛮力法进行优化后的算法 其复杂度一般比蛮力法要小 空间复杂度 有个物品 即最多递归层 存储物品信息就是一个一维数组 即 nn 回溯法求解 0 1 背包问题的空间复杂度为 nO 3 分支限界法求解背包问题 分支限界法求解背包问题 1 基本思想 分支限界法类似于回溯法 也是在问题的解空间上搜索问题解的算法 一般情况下 分支限界法与回溯法的求解目标不同 回溯法的求解目标是找出解空间中满足约束条件 的所有解 而分支限界法的求解目标则是找出满足约束条件的一个解 或是在满足约束 条件的解中找出使某一目标函数值达到极大或极小的解 即在某种意义下的最优解 首先 要对输入数据进行预处理 将各物品依其单位重量价值从大到小进行排列 在下面描述的优先队列分支限界法中 节点的优先级由已装袋的物品价值加上剩下 的最大单位重量价值的物品装满剩余容量的价值和 算法首先检查当前扩展结点的左儿子结点的可行性 如果该左儿子结点是可行结点 则将它加入到子集树和活结点优先队列中 当前扩展结点的右儿子结点一定是可行结点 仅当右儿子结点满足上界约束时才将它加入子集树和活结点优先队列 当扩展到叶节点 时为问题的最优值 2 代码 include include using namespace std define N 100 最多可能物体数 struct goods 物品结构体 int sign 物品序号 int w 物品重量 int p 物品价值 a N bool m goods a goods b 华 北 电 力 大 学 实 验 报 告 第 页 共 页 return a p a w b p b w int max int a int b return aH i 2 b swap H i H i 2 else done true i i 2 堆中元素下移 华 北 电 力 大 学 实 验 报 告 第 页 共 页 void mov down HEAP H int n int i bool done false if 2 i n while done if H i 2 b H i b swap H i 2 H i else done true 往堆中插入结点 void insert HEAP H HEAP x int H n x mov up H n 删除堆中结点 void del HEAP H int x H i y H n n if i x b mov up H i else mov down H n i 获得堆顶元素并删除 HEAP del top HEAP H int del H n 1 return x 华 北 电 力 大 学 实 验 报 告 第 页 共 页 计算分支节点的上界 void bound KNAPNODE node int M goods a int n int i node k float w node w float p node p if node w M 物体重量超过背包载重量 node b 0 上界置为 0 else while w a i w M 计算背包已装入载重 p a i p 计算背包已装入价值 if ib p M w a i p a i w else node b p 用分支限界法实现 0 1 背包问题 int KnapSack4 int n goods a int C int X int i k 0 堆中元素个数的计数器初始化为 0 int v KNAPNODE xnode ynode znode HEAP x y z heap heap new HEAP n n 分配堆的存储空间 for i 0 i n i a i sign i 记录物体的初始编号 sort a a n m 对物体按照价值重量比排序 xnode new KNAPNODE 建立父亲结点 for i 0 is1 i false xnode k xnode w xnode p 0 while xnode ks1 ynode k true 装入第 k 个物体 ynode w a ynode k w 背包中物体重量累计 ynode p a ynode k p 背包中物体价值