最优加工顺序 问题描述 现在有3个机器零件{J1,J2,J3}，在第一台机器上的加工时间分别为2、5、4，在第二台机器上的加工时间分别为3、1、6.如何安排零件加工顺序，使第一个零件从机器1上加工开始到最后一个零件在机器2上加工完成，所需的总加工时间最短？ 问题分析 我们通过分析可以发现，第一台机器可以连续加工，而第二台机器开始加工的时间是当前第一台机器的下线时间和第二台机器下线时间的最大值。 实际上就是找到n个机器零件的一个排列，使总的加工时间最短。 算法设计 定义问题的解空间。解的形式为n元组：{x1,x2,.…

着色问题 问题分析 假设地图共有7个区域，分别是A/B/C/D/E/F/G，对上面顺序进行编号，每个区域用一个结点表示，相邻的区域有连线，那么地图就转化成一个无向连接图。 算法设计 定义问题的解空间。图的m着色问题解空间形式为n元组{x1,x2,...,xi,...,xn}，每个分量取值为1,2,3,...,m，即问题的解是一个n元向量。由此可得，问题的解空间为{x1,x2,...,xi,...,xn}，其中显约束为xi=1,2,...,m。 确定解空间的组织结构：一颗满m叉树，树的深度为n。 搜索解空间 约束条件…

回溯法 回溯法的思想是：能进则进，进不了换，换不了退。 隐约束指对能否得到问题的可行解和最优解做出的约束。隐约束包括约束函数和限界函数。 关键步骤是： 1. 定义解空间； 2. 确定解空间的组织结构（子集树、排列数、m叉树等）； 3. 搜索解空间。 回溯法阶梯的关键是设计有效的显约束和隐约束。 大卖场购物（0-1背包问题） 问题举例 每个物品重量w和价值v如下表所示，购物车容量为W，求不超过购物车重量的最大价值。 w[] 1 2 3 4 2 5 4 2 w[] 1 2 3 4 6 3 5 4 问题分析 解空间={x…