运筹学基础 课件 第2章

第2章朴素优化范式2.1生成测试范例2.2

枚举法2.3深度优先搜索2.4广度优先搜索2.5贪婪算法2.6启发式算法2.7拓展应用:玻璃球硬度测试实验设计问题

2.1生成测试范例

在最直观的决策模式中,我们会构造一个解决方案并检测是否满足约束条件,如果不满足约束条件,就再构造一个解决方案,直到找到一个满足约束条件的解决方案为止,这样的为问题找到解决方案的决策思路称为生成测试范例。这适合于寻找可行解的问题,可行解之间无优劣之分。

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

图2-1八皇后问题的生成测试范例

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

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深度优先搜索

深度优先搜索(Deep-FirstSearch,DFS)是一种基于图数据结构的枚举法。可以这样理解,图中的节点都有一定的层次关系,所有的从同一个点a出发通过弧能够直接一步到达的点bi∈B是同级的,这是广度上的衡量,而a称为bi的上级,bi称作a的下级,如图2-2所示。所谓深度优先,就是当前点往下走的时候,优先选择第一个未走过的下级节点,不优先到达一个未走过的同级节点。

图2-2-节点的层次结构及深度和广度衡量

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

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

图2-3拼图问题的初始排列和目标排列

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

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

图2-5所示的状态转移关系。图2-5拼图问题步骤2

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

断下一个阶段状态,如图2-6所示。图2-6拼图问题步骤3

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

图2-7拼图问题步骤4

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

图2-8深度优先搜索用于拼图问题的搜索序列

2.4广度优先搜索

例2-6(拼图问题)同样,对于一个2×2拼图问题来讲,给定初始状态和目标状态如图2-9所示,要想从初始状态达到目标状态,也可以使用广度优先搜索的办法寻找解决方案。

图2-92×2拼图问题的初始状态和目标状态

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

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

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

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

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

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

图2-15广度优先搜索用于2×2拼图还原的搜索序列

2.5贪婪算法

贪婪算法是指,在对问题求解的每个子阶段或者步骤中,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,所做出的是在某种意义上的局部最优解。

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

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

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

因此,贪婪算法不一定能保证得到最优解。关于背包问题,可以建立线性规划模型求解,也可以利用动态规划求解(参见5.4节)。

贪婪算法看起来有点只顾眼前不顾长远,甚至有人形容其为“饮鸩止渴”。但是在许多情况下,贪婪算法简单直接并且好用,很多问题使用贪婪算法可以得到令人满意的解。如果再进一步优化,往往要花费较大的建设成本和付出艰辛的努力,并且个体的努力还依赖于整体信息化计算环境的支持。因此,在现实中,贪婪算法非常好用,在许多粗放式管理与

运用中,运筹学的很多优良的算法被束之高阁。

2.6启发式算法

所谓启发式算法,指的是受物理生物运行进化规律(如模拟退火算法、烟花算法、遗传算法)、生物智能(如蚁群算法、蜂群算法、狼群算法等)、人类解决问题的“经验”“知识”的启发(如旅行商问题的最近邻算法和插入算法等、运输问题的最小元素法和伏格尔法等),通过模仿寻优规则、模式而得出来的算法。启发式算法一般能比较快速地找到满意解,对于很多复杂问题虽然不能保证给出最优解,但是起码能给出不错的解。其缺点是不能保证得到最优解,甚至对解的质量通常也很难做出判断。

例2-9对于如图2-16所示的迷宫问题,请使用扶墙算法找到一条从入口到出口的路。所谓扶墙算法,就是从入口处开始,假设人在行进的过程中,始终要左手(或者右手)扶着墙不能离开。扶墙算法就借鉴了人类的知识和经验:“顺藤摸瓜”。

图2-16迷宫问题

例2-10对于如图2-16所示的迷宫问题,请使用随机老鼠算法求解从入口到出口的路。所谓随机老鼠算法,就是从入口处开始往前走,每当走到分岔口的时候,就随机决定往哪个方向走。随机老鼠算法模仿了自然界中的老鼠的行为,最终也能找到出口,但是一般花费的时间相对较长。

2.7拓展应用:玻璃球硬度测试实验设计问题

有一栋100层高的大楼,给你两个完全相同的玻璃球。假设从某一层开始往上,丢下玻璃球会摔碎,现在要测试这个临界层数,作为玻璃球硬度的度量。那么怎么利用手中的两个球,用最少的测试次数,测试玻璃球的硬度呢?假如只有一个球,那么很显然,只有一个办法:从第一层开始投,如果没碎再试第二层、第三层等,也就是只能使用枚举法进行实验。其实验次数的分布与玻璃球实际硬度之间的关系如图2-17所示。

图2-17枚举法实验次数与实际硬度之间的关系

现在有两个球,当然也可以使用枚举法,但是实验次数没有降低。我们使用生成测试范例的办法明显可以找到一个实验次数更少的方案:第一个球在50层往下扔,如果碎了,说明玻璃球的硬度小于50,无须再测试50以上的楼层,如果玻璃球没碎,则只需要测试50以上的楼层,通过这样简单的二分法可以降低有可能的实验次数。其最坏情况下实验次数的分布与玻璃球实际硬度之间的关系如图2-18所示。

图2-18二分法的实验次数与实际硬度之间的关系

为了使最坏