运筹学基础 课件 第2章.pptx

第2章朴素优化范式;

2.1生成测试范例;

;

例2-2(八皇后问题)在国际象棋8×8的棋盘上,要摆放8个皇后,但是要保证没有任意两个皇后可以相互攻击,也即要求没有任意两个皇后处在相同的行、列或对角线上。如图2-1所示,如果深色方格代表为皇后选择的位置,则图2-1(a)所示的为一个可行的方案,而图2-1(b)所示的是不可行的方案,因为不符合任意两个皇后都不能处在同一对角线上的约束。;

;

对于八皇后问题来讲,基本的解决范式就是生成测试范例,也就是生成一个解决方案,判断是否可行,如果可行,算法结束,否则再生成另外一个解决方案。不同的解决方案之间并无优劣之分,问题的目标只是要找到一个满足条件的解决方案。;

2.2枚举法;

例2-3(人民币组合问题)假设我们有8种不同面值的人民币{1,5,10,50,100,200,500,1000},单位为分,用这些面值的人民币组合构成一个给定的数值n。例如,n=3000,问总共有多少种可能的组合方式?

如果假设8种人民币的数量分别为xi(i=1,…,8),则可以确定各个变量的取值范围如表2-1所示。;

使用枚举的方法需要搜索的状态空间中包含的解的数量为各个维度状态数量的乘积,也即4.5991e+14,这样的状态空间规模使用一般的计算机尚可在忍受的时间范围内完成。

例如,在处理器为Intel(R)Core(TM)i77500UCPU@2.70GHz,内存为8GB的联想笔记本电脑上,使用Matlab计算n=30000的人民币组合问题,花费时间为2285.5秒,代码如下:;;

;

然而对于很多实际问题的搜索状态空间,枚举法多数是不可忍受的。当然,枚举法在很多情况下计算时间的不可忍受也是可被利用的,否则,密码可被暴力破解,网上银行和保密通信就有麻烦了。;

例2-4(n皇后问题)针对例2-2的八皇后问题,将其一般化后就是n皇后问题,在一个n×n的棋盘上摆放n个皇后保证相互没有攻击可能。请问n皇后问题有多少种可行的方案?

对于n皇后问题,需要检查的组合数量为n!。对于八皇后问题,可以使用枚举的办法统计可行方案的数量。但是对于数量越大的n皇后问题,枚举法就越不可行,因为需要枚举的方案的数量呈指数级增长。例如,n=20,需要检查的组合数量为20!=2.433×1018,使用枚举???来检查已经不现实了。;

2.3深度优先搜索;

;

例2-5(拼图问题)对于一个2×2拼图问题来讲,给定初始排列和目标排列如图23所示,要想从初始排列达到目标排列,请问要进行怎样的操作才可以达到目的?

为了描述问题更加方便,将拼图的一个排列称为拼图的一个状态,对拼图的操作抽象为四种操作:空格上移、空格下移、空格右移、空格左移。;

;

步骤1:初始状态为s0,按照顺序通过操作集中的某种操作后,状态转移关系如图2-4所示,因此状态s0的下级节点有2个。;

步骤2:按照深度优先搜索的规则,当前状态点s0往下走的时候,优先选择第一个未走过的下级节点s11,也就是如

图2-5所示的状态转移关系。;

步骤3:当前状态s11与目标状态不同,则按照操作集判

断下一个阶段状态,如图2-6所示。;

步骤4:按照深度优先搜索的规则,当前状态点s11往下走的时候,优先选择第一个未走过的下级节点s21,也就是如图2-7所示的状态转移关系。

;

以此类推,直到算法停止,搜索过程如图2-8所示。;

;

2.4广度优先搜索;

;

步骤1:初始状态为s0,按照顺序通过操作集中的某种操作后,状态转移关系如图2-10所示,因此状态s0的下级节点有2个。;

步骤2:初始状态点s0的下级状态节点包括s11和s12,按照广度优先搜索的规则,优先搜索同级的状态节点,也就是如图2-11所示的状态转移关系。;

步骤3:从状态s11开始,按照操作集判断下一个阶段状态,如图2-12所示,因此当前状态s11的下级节点只有s21。;

步骤4:从状态s12开始,按照操作集判断下一个阶段状态,如图2-13所示,因此当前状态的下级节点只有s22。;

步骤5:按照广度优先搜索的规则,搜索的状态转移如图2-14所示(从上往下、从左至右的生成顺序)。;

步骤6:以此类推,直到搜索到的某个状态和目标状态相同,算法停止,搜索过程如图2-15所示。;

;

2.5贪婪算法;;

例2-8有三种物品A、B、C,单位物品的重量分别为1、2、3,单位物品的价值分别为15、33、50,背包的最大载重为4,请问可装入背包的物品的最大价值是多少?

按照贪婪算法的思想,要想装入物品的总价值最高,那么单位价值应该也比较高,因此,计算三种物品的单位价值分别为;;

因此,贪