0028算法笔记——【回溯法】批作业调度问题和符号三角形问题

1 批作业调度问题 1 问题描述问题描述 给定 n 个作业的集合 J1 J2 Jn 每个作业必须先由机器 1 处理 然后由机器 2 处理 作业 Ji 需要机器 j 的处理时间为 tji 对于一个确 定的作业调度 设 Fji 是作业 i 在机器 j 上完成处理的时间 所有作业 在机器 2 上完成处理的时间和称为该作业调度的完成时间和 批处理作业调度问题要求对于给定的批处理作业调度问题要求对于给定的n个作业 制定最佳作业调度方案 使其完成时间个作业 制定最佳作业调度方案 使其完成时间 和达到最小和达到最小 例 设 n 3 考虑以下实例 这 3 个作业的 6 种可能的调度方案是 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 它们所相应的完成时间和 分别是 19 18 20 21 19 19 易见 最佳调度方案是 1 3 2 其 完成时间和为 18 2 算法设计算法设计 批处理作业调度问题要从 n 个作业的所有排列中找出具有最小完成 时间和的作业调度 所以如图 批处理作业调度问题的解空间是一颗 排列树排列树 按照回溯法搜索排列树的算法框架 设开始时 x 1 2 n 是 所给的 n 个作业 则相应的排列树由 x 1 n 的所有排列构成 算法具体代码如下 cpp view plain copy 1 include stdafx h 2 include 3 using namespace std 4 5 class Flowshop 6 7 friend int Flow int M int n int bestx 8 private 9 void Backtrack int i 10 11 int M 各作业所需的处理时间 12 x 当前作业调度 13 bestx 当前最优作业调度 14 15 f2 机器 2 完成处理时间 16 f1 机器 1 完成处理时间 17 f 完成时间和 18 19 bestf 当前最优值 20 n 作业数 21 22 23 int Flow int M int n int bestx 24 25 template 26 inline void Swap Type 27 28 int main 29 30 int n 3 bf 31 int M1 4 3 0 0 0 0 2 1 0 3 1 0 2 3 32 33 int M new int n 1 34 35 for int i 0 i n i 36 37 M i new int 3 38 39 cout M i j 值如下 endl 40 41 for int i 0 i n i 42 43 for int j 0 j 3 j 44 45 M i j M1 i j 46 47 48 49 int bestx 4 50 for int i 1 i n i 51 52 cout 53 for int j 1 j 3 j 54 cout M i j 55 cout 56 57 58 bf Flow M n bestx 59 60 for int i 0 i n i 61 62 delete M i 63 64 delete M 65 66 M 0 67 68 cout endl 最优值是 bf endl 69 cout 最优调度是 70 71 for int i 1 i n i 72 73 cout bestx i 74 75 cout n 82 83 for int j 1 j n j 84 85 bestx j x j 86 87 bestf f 88 89 else 90 91 for int j i j f1 f2 i 1 f1 M x j 2 96 97 f f2 i 98 if f bestf 剪枝 99 100 Swap x i x j 101 Backtrack i 1 102 Swap x i x j 103 104 f1 M x j 1 105 f f2 i 106 107 108 109 110 int Flow int M int n int bestx 111 112 int ub 30000 113 114 Flowshop X 115 X n n 116 X x new int n 1 117 X f2 new int n 1 118 119 X M M 120 X bestx bestx 121 X bestf ub 122 123 X f1 0 124 X f 0 125 126 for int i 0 i n i 127 128 X f2 i 0 X x i i 129 130 X Backtrack 1 131 delete X x 132 delete X f2 133 return X bestf 134 135 136 template 137 inline void Swap Type 140 a b 141 b temp 142 由于算法 Backtrack 在每一个节点处耗费 O 1 计算时间 故在最坏 情况下 整个算法计算时间复杂性为 O n 程序运行结果如下 2 符号三角形问题 1 问题描速问题描速 下图是由 14 个 和 14 个 组成的符号三角形 2 个同号下面都是 2 个异号下面都是 在一般情况下 符号三角形的第一行有 n 个符号 符号三角形问题 要求对于给定的 n 计算有多少个不同的符号三角形 使其所含的计算有多少个不同的符号三角形 使其所含的 和和 的个数相的个数相 同同 2 算法设计算法设计 解向量解向量 用 n 元组 x 1 n 表示符号三角形的第一行 当 x i 1 时表示 符号三角形第一行的第 i 个符号为 当 i 0 时 表示符号三角形第 一行的第 i 个符号为 1 x n 由于 x i 是二值的 所以可以用一 棵完全二叉树完全二叉树来表示解空间 可行性约束函数可行性约束函数 在符号三角形的第一行前 i 个符号 x 1 i 确定后 就确 定了一个由 i i 1 2 个符号组成的符号三角形 下一步确定 x i 1 的值 后 只要在前面已确定的符号三角形的右边加一条边 就可以扩展为 x 1 i 1 所相应的符号三角形 最终由 x 1 n 所确定的符号三角形中包 含 号个数与 个数同为 n n 1 4 因此 当前符号三角形所包含的 个数与 个数均不超过 n n 1 4 无解的判断无解的判断 对于给定的 n 当 n n 1 2 为奇数时 显然不存在包含 的 号个数与 号个数相同的符号三角形 此时 可以通过简单的判 断加以处理 程序的具体代码如下 cpp view plain copy 1 include stdafx h 2 include 3 using namespace std 4 5 class Triangle 6 7 friend int Compute int 8 private 9 void Backtrack int i 10 int n 第一行的符号个数 11 half n n 1 4 12 count 当前 号个数 13 p 符号三角矩阵 14 long sum 已找到的符号三角形数 15 16 17 int Compute int n 18 19 int main 20 21 for int n 1 n 10 n 22 23 cout n n 时 共有 Compute n 24 cout 个不同的符号三角形 half t t 1 2 count half 32 33 return 34 35 36 if t n 37 38 sum 39 40 else 41 42 for int i 0 i 2 i 43 44 p 1 t i 第一行符号 45 count i 当前 号个数 46 47 for int j 2 j t j 48 49 p j t j 1 p j 1 t j 1 p j 1 t j 2 50 count p j t j 1 51 52 Backtrack t 1 53 for int j 2 j t j 54 55 count p j t j 1 56 57 count i 58 59 60 61 62 int Compute int n 63 64 Triangle X 65 X n n 66 X count 0 67 X sum 0 68 69 X half n n 1 2 70 if X half 2 1 return 0 71 X half X half 2 72 73 int p new int n 1 74 75 for int i 0 i n i 76 77 p i new int n 1 78 79 80 for int i 0 i n i 81 82 for int j 0 j n j 83 84 p i j 0 85 86