计算机科学导论-计算思维程序实践 课件L10 算法：程序与计算系统的灵魂；L11 难解性问题求解-组合、随机与近似解

1第10章

算法：程序与计算系统之灵魂2本章导图3本章学习什么--理解算法类问题求解框架4一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择序列求和问题求解为例5算法---计算机与软件的灵魂。最早的算法：公元前3世纪，欧几里得《几何原本》，求最大公约数的辗转相除法算法是一个有穷规则的集合，它用规则规定了解决某一特定类型问题的运算序列，或者规定了任务执行或问题求解的一系列步骤。如音乐乐谱、太极拳谱等都可看作广义的算法什么是算法？6数字序列求和问题算法Input: n个具有先后次序的数字序列D={d1,d2,...,dn}；Output:

序列D的n个数字之和；Step1.

令一个变量sum的值为0，令一个变量i的值为1；Step2.将Di累加到sum，并将i增加1；Step3.

若i小于等于n转到Step2；否则输出sum，算法结束。算法的5个基本特征n

有穷性：一个算法在执行有穷步规则之后必须结束。n

确定性：算法的每一个步骤必须要确切地定义，不得有歧义性。n

输入：算法有零个或多个的输入。n

输出：算法有一个或多个的输出/结果，即与输入有某个特定关系的量。n

能行性：算法中有待执行的运算和操作必须是相当基本的(可以由机器自动完成)，并能在有限时间内完成。7一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择序列求和问题求解为例8u单位执行时间：执行一次基本运算所需的平均时间，用来做基本单位u时间复杂度:

如果一个问题的规模是n，求解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数，则T(n)称为这一算法的“时间复杂度”。ü基本参数

n——问题规模，表明输入数据的规模大小ü把复杂性或运行时间表达为n的函数。算法获得结果需要多长时间?时间复杂度算法的时间复杂度l 时间复杂度描述算法随输入数据规模增长时，运算次数的增长趋势。l 算法的时间复杂度与计算机的性能无关l 时间复杂度是衡量算法本身求解问题效率的一种度量标准。9时间复杂度描述算法随输入数据规模增长时，运算次数的增长趋势。

此处是线性增长趋势。时间复杂度分析示例算法10.1数字序列求和问题Input: n个具有先后次序的数字序列D[1...n]；Output:

序列D的n个数字之和；Step1.

令一个变量sum的值为0，令一个变量i的值为1；Step2.

将Di累加到sum，并将i增加1；Step3.

若i小于等于n转到Step2；否则输出sum，算法结束。Step1：2条赋值语句；Step2：2条加法语句（重复n次）；Step3：执行1条判断语句（重复n次），算法结束前，执行1条输出语句T(n)=2+2n+n+1=

3n+310u“大O记法”：渐进时间复杂度n越大，低阶项和系数的影响越小去掉低阶项和系数，再用O进行标记“O”表示量级

(order)，允许使用“=”代替“≈”，如3n2+4n+1

=Ο(n2)。O(f(n))渐进时间复杂度与大O记法算法10.1数字序列求和问题Input: n个具有先后次序的数字序列D[1...n]；Output: 序列D的n个数字之和；Step1.

令一个变量sum的值为0，令一个变量i的值为1；Step2.

将Di累加到sum，并将i增加1；Step3.

若i小于等于n转到Step2；否则输出sum，算法结束。T(n)=3n+3=

O(n)11指数量级：O(bn),

O(n!)多项式量级：O(1),O(log

n),O(n),O(n

log

n),O(nb)不同的时间复杂度量级以1百万个单位时间为1秒时间复杂度问题规模nn=10n=100n=1000O(1)常数0.001毫秒0.001毫秒0.001毫秒O(logn)对数0.003毫秒0.006毫秒0.0096毫秒O(n)线性0.01毫秒0.1毫秒1毫秒O(nlogn)线性对数0.03毫秒0.66毫秒9.97毫秒O(n2)平方0.1毫秒10毫秒1秒O(2n)指数1毫秒4*1016年3.4*10287年O(n!)阶乘3.6秒2.9*10144年1.3*102555年12一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择最大子序列和问题求解为例13数学建模是用数学语言描述实际现象的过程，即建立数学模型的过程。数学模型是对实际问题的一种数学表述，是对部分现实世界为某种目的而进行的一个抽象与简化的数学结构。算法类问题求解的第一步就是数学建模【示例】攀岩问题：小明在训练攀岩，下图记录了每分钟上升或下降的高度，共14分钟的数据，定义“连续时间上升高度”为某个时间点t1到另一个时间点t2之间上升与下降的数据总和，例如第7~10分钟内的上升高度为7+7-5+7=16，要求找出最大的“连续时间上升高度”。这个问题怎么求解呢?14攀岩问题：抽象成“最大子序列和问题”,

序列：一组具有先后顺序的整数。最优化问题：在给定的约束条件下,

求解最优的方案使得目标最大化或最小化的问题。这个问题是最优化问题。不同时间上升/下降高度--

整数序列连续时间上升高度--

子序列和将社会/自然问题

转化为

数学问题【示例】最大子序列和问题：已知一个数字序列，在其中找到一个连续的子序列，使得该子序列之和是所有的子序列和中的最大值。15最大子序列和问题的数学模型数学模型的四个核心要素：l 输入l 输出l 约束l 目标通过自然数及其下标将不同的数据关联起来，是算法类问题抽象的重要方法。16任何子序列可由di,di+1,...,dj表达，其中i和j分别为子序列的起点和终点。数学模型，可发现问题求解的基本思路任何子序列之和可用“数字序列求和算法”求出。所有可能的i和j的组合（1≤i≤j≤n）穷举了所有可能的子序列。所有可能的子序列之和的最大值是问题的解。穷举/遍历17一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择最大子序列和问题求解为例18(数据的)逻辑结构(数据的)存储结构操作反映逻辑语义关系为什么需要数据结构数据结构是数据的逻辑结构、存储结构及其操作的总称，它提供了问题求解/算法的数据操纵机制。u数据的逻辑结构描述数据之间的逻辑语意关系；u数据的存储结构是在反映数据逻辑关系的原则下，便于计算系统处理的物理结构为便于计算系统处理19数据的逻辑结构与存储结构用线性表描述攀岩问题用树描述家族谱系用图描述校园地图常见逻辑结构：线性表、树、图。线性表：n（n≥0）个具有相同特性的数据节点构成的有限序列树：一种逻辑上表现为一颗倒挂的树的结构图：一种由节点和连接节点的边构成的结构20u线性表（Linear

List）是一种由n（n≥0）个具有相同特性的数据节点构成的有限序列，可以记为a1,a2...an，除了首尾元素，线性表中的每个元素都有一个直接前驱和一个直接后继，第一个元素只有直接后继，最后一个元素只有直接前驱。u数据结构的目的是为算法提供数据操纵机制，这种操纵机制由数据结构的操作接口提供，表现形式为一批定义良好的函数集，这些函数集合构成了数据结构可供外部使用的操作接口。线性表及其操作接口l IS-EMPTY(L)

如果线性表L的长度为0，则返回1，否则返回0；l LENGTH(L)

获得线性表L中元素的个数；l L[i]或GET(L,

i)

获取线性表L中的第i个元素（1≤i≤n）；l PRIOR(L,

i)

获取线性表L第i个元素的前驱元素（2≤i≤n）；l NEXT(L,

i)

获取线性表L第i个元素的后继元素（1≤i≤n-1）；l L[i]←x或UPDATE(L,

i,

x)

将线性表L的第i个元素改为x；l INSERT(L,

i,

x)

在线性表L的位置i处插入元素x，原位置i及其后面的的元素都向后移动一个位置；l DELETE(L,

i)

从线性表L中删除位置i处的元素，原位置i+1及其后面的的元素都向前移动一个位置。线性表的操作接口21u用顺序表存储数据时，元素在内存中是连续的。u顺序表的元素在逻辑上的排列顺序和物理上是一致的，若i<j，元素aj在逻辑上和物理上都在ai之后。线性表的存储结构之一：顺序表22u

链表的每个元素除了存储数据，还有一个指针保存了下一个元素的地址（称为next指针）。u元素在内存中的位置不是连续的，访问元素时，只能从第一个元素开始，沿着next指针依次访问下一个元素

。线性表的存储结构之二：链表23u顺序表的元素存取效率很高，因为顺序表支持随机存取。u

随机存取：通过元素的逻辑地址直接计算元素的物理地址以便进行存取。u顺序表的存储操作所需时间与问题规模n无关。顺序表和链表在存取操作上的差异顺序表中元素的物理地址计算公式：元素的物理地址=顺序表开始物理地址+(元素逻辑地址-1)*元素占用字节数访问顺序表元素的时间复杂度：O(1)u链表的元素存储效率较低，因为链表仅支持顺序存取。u

顺序存取：给定逻辑地址i，只能先依次访问第1、2...i-1个元素，才能访问第i个元素。u链表的存取操作所需时间与问题规模n相关，n越大，访问后面的元素所需时间越长。链表中的元素地址无法直接计算，只能顺着链表元素去访问访问链表元素的时间复杂度：O(n)24u顺序表要保持物理存储位置上的连续性。u删除第i个元素后，必须将第i+1到第n个元素向前移动一个位置（通过内存拷贝操作），以填补因删除第i个元素而留下的空位。顺序表和链表在删除操作上的差异删除顺序表元素的时间复杂度：O(n)u链表的元素在物理存储上不要求是连续的。u链表删除第i个元素后，将第i-1个元素的next指针改为第i+1个元素的地址。删除链表元素的时间复杂度：O(1)25为最大子序列和问题选择合适的数据结构线性表与问题的输入高度吻合用顺序表的效率更高（1）以数学模型为基础，确定数据的组织结构；（2）根据组织结构选择一种合适的逻辑结构；（3）确定需要对数据进行哪些操作；（4）根据这些操作从备选的存储结构中选择一种能高效支持这些操作的存储结构。u问题的输入：

n个具有先后次序的数字组成的序列D={d1,d2,...,dn}

。u线性表：由n（n≥0）个具有相同特性的数据节点构成的有限序列。数据结构设计的方法。26一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择最大子序列和问题求解为例27ü分支结构：“如果Q成立，那么执行A，否则执行B”

，Q是某些逻辑条件，即按条件判断结果决定执行哪些规则或语句的一种结构

。ü循环结构：控制规则或语句多次执行的一种结构---迭代(iteration)u循环结构又分为有界循环结构和条件循环结构。ü有界循环：

“重复N次执行A”，其中N是一个整数。ü条件循环：某些时候称为无界循环，“重复执行A直到条件Q成立”或“当Q成立时反复执行A”，其中Q是条件。算法与程序的基本控制结构算法的控制结构描述了算法的操作步骤，控制结构的设计反映了算法的思想ü顺序结构：“执行A，然后执行B”，是按顺序执行一条条规则或语句的一种结构

。28流程图的基本表示符号ü矩形框：表示一组顺序执行的规则或者程序语句。ü菱形框：表示条件判断，并根据判断结果执行不同的分支。ü圆形框：表示算法或程序的开始或结束。ü箭头线：表示算法或程序的走向。算法的程序流程图表达方法描述算法的方法：自然语言描述法、流程图、伪代码29三种控制结构的流程图表达开始第1条规则或语句第n条规则或语句结束顺序结构的流程图算法的程序流程图表达方法开始条件成立否？是否条件成立时执行的规则或语句结束条件不成立时执行的规则或语句分支结构的流程图循环结构的流程图初始化部分开始循环控制条件成立？修改部分需循环执行的规则或语句。即：循环体结束是否循环结束30u可能解：解的取值空间中任何可能的一个值

。可能解与解空间最大子序列和问题的可能解：任意符合1≤i≤j≤n的i和j都形成一个可能解.例: D[2...6]、D[3...9]都是问题的可能解。u解空间：由问题的所有可能解构成的集合

。最大子序列和问题的解空间：所有可能的i和j的组合构成的子序列的集合。解空间大小:

Cn2=

n(n+1)/2问题求解的过程：在解空间中搜索符合问题约束以及优化目标的解。最基本的算法：遍历-计算-验证（穷举法）。31穷举法求最大子序列和问题的流程图穷举法：对问题的解空间进行遍历，对遍历中的每个可能解进行逐一验证，若某个可能解符合问题的约束条件和优化目标，则为该问题的最终解。【示例】最大子序列和问题的穷举法思想u

将任意可能解表达为D[i...j]，1≤i≤j≤n；将思想/策略u

将i设计为外层循环结构的循环变量，j为内层循

转变为“步骤”环结构的循环变量；u

在内循环中，用算法10.1求子序列D[i...j]之和；u

时间复杂度：O(n3)。不同数据结构设计给算法带来不同的性能；若使用链表存储序列D，算法时间复杂度将变为O(n4)。32算法的伪代码表达方法u伪代码：一种介于计算机语言和自然语言之间的语言，主要目的是以精确、简洁、易于理解的方式描述算法。u

比自然语言描述法更为精确，比流程图更简洁，更容易用程序设计语言实现。伪代码符号33穷举法求最大子序列和问题的伪代码算法10.2

最大子序列和问题的穷举算法Input:

大小为n的顺序表D[1...n]Output:

顺序表D的最大子序列和functionFIND-MAX-SUBSEQ-2(D[1...n])beginres←-∞;

//初值为负无穷大for

i←1tondo//i为子序列起点7 for

j←itondo//j为子序列终点8sum←0for

k←i

to

j

do

//子序列求和910sum←sum+D[k]endforres←MAX(res,sum)//MAX返回较大值endforendfor输出res16end

beginu计算学科的学生不仅能够设计算法，而且会描述和表达算法，更要能读懂算法。u最外层循环：枚举子序列起点。

u中间的循环：枚举子序列终点。u最内层循环：计算子序列之和。时间复杂度为：T(n)=

O(n3)34穷举法优缺点及其一般步骤u穷举法优点：思路简单易于实现，只要分析清楚如何遍历解空间，计算可能解，然后验证可能解，即可设计出相应的算法

。u穷举法缺点：因为需要遍历所有的可能解，若解空间很庞大，效率会很低

。设计穷举法的一般步骤（1）建立问题的数学模型，需要明确四要素：输入、输出、约束、优化目标；（2）以数学模型为基础，选择合适的数据结构，数据结构要便于控制结构的操作；（3）以数学模型为基础，分析问题的解空间形式；（4）设计控制结构对解空间进行遍历，对于每个可能解，使用数学模型中的约束和优化目标进行验证以便找到符合要求的解；35一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择优化思想之一：“累加和”相减36算法优化的基本方法是消除无效计算消除无效计算的三种手段：u消除不必要遍历：利用问题的约束条件来控制遍历的范围，停止对非必要部分的遍历。u消除重复计算：在遍历解空间的过程中，检查不同可能解的验证是否存在重复的计算，如果存在，则暂存已验证可能解的结果，将之用于另一个可能解的验证；u优化解空间搜索策略：不使用穷举法这种直接遍历解空间的控制结构，而是利用一些行之有效的算法策略，设计更高效的解空间搜索策略。学习算法的过程：学习如何在众多算法策略中选择适合特定问题求解的策略。37穷举法中的无效计算以i为起点的子序列：D[i...i]、D[i..i+1]、...、D[i...n]，每次都从第一个元素开始进行累加，存在大量重复运算。4

beginres←-∞;

//初值为负无穷大for

i←1

to

n

do

//i为子序列起点for

j←i

to

n

do

//j为子序列终点sum←09 for

k←itojdo

//子序列求和10 sum←sum+D[k]11end

forres←MAX(res,

sum)end

forend

for输出res16end

begin示例：D[1...13]之和与D[1...14]之和的重复计算38优化思想之一：“累加和”相减u累加和序列S[0...n]：元素S[i]为序列D[1...n]中前i个元素之和。u子序列D[i...j]之和

=

S[j]

-

S[i-1],

1≤i≤j≤n。为什么可以提高效率：一次循环O(n)时间完成序列S的构造，一次减法O(1)时间计算任意子序列之和39利用“累加和”的优化算法算法10.3

最大子序列和问题的优化算法一Input:大小为n的顺序表D[1...n]Output:

顺序表D的最大子序列和function

FIND-MAX-SUBSEQ-3(D[1...n])begin//i为子序列起点//构造序列S的第i个元素//初值为负无穷大//i为子序列起点forj←itondo //以i为起点的第2到最后一个子序列的循环5 初始化大小为n+1的序列S[0...n]

6 S[0]←07 fori←1ton

do8 S[i]←S[i-1]+D[i]end

forres←-∞fori←1ton

do12sum←S[j]-S[i-1]

//利用序列S计算子序列D[i...j]之和res←MAX(res,

sum)

//确保res为最大值end

forend

for输出res18end

begin构造“累加和”序列S“累加和”一次构造，多次使用时间复杂度为：T(n)=

O(n2)40算法10.3中的无效计算10 res←-∞//初值为负无穷大11 fori←1ton

do//i为子序列起点12for

j←iton

do//以i为起点的第2到最后一个子序列的循环1314sum←S[j]-S[i-1] //利用序列S计算子序列D[i...j]之和res←MAX(res,

sum)//确保res为最大值15end

for16 end

foru

遍历解空间是最基本的问题求解方法。u

有很多巧妙的算法策略，可以更高效地在解空间中搜索问题的解，不需要遍历整个解空间。依然是对解空间中所有可能解进行遍历的算法还有更好的办法吗41一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择优化思想之二：问题分解42优化思想之二：问题分解问题分解是一种将大的问题分解为若干个更小的子问题的方法，如果子问题的形式与原问题相同，可用递归方法完成子问题的求解。n 子问题规模必须要小于原问题n 如果子问题的形式与原问题相同，可以利用递归求解子问题n 要建立原问题与子问题之间的联系n 要分析清楚什么是可以直接求解的最小子问题43最大值子序列和问题的分解原问题的解只可能是下面的三种情况之一：u

“解”完全在左半部分即D[1...7]中，因此结果等于f(1,7);u

“解”完全在右半部分即D[8...14]中，因此结果等于f(8,14);u

“解”跨越了中线，一部分在左半部分，另一部分在右半部分，记为g(1,7,14)。f(1,7)、f(8,14)与f(1,14)属于同类问题；g(1,7,14)属于新问题求出3个子问题的解，其中的最大值就是原问题的解44跨越中线子问题g(1,7,14)的求解方法u

以中线位置为起点向左进行累加，在累加过程中筛选左半部分的最大值lsum；u

以中线位置为起点向右进行累加，在累加过程中筛选右半部分的最大值rsum;u

g(1,7,14)的最终结果为lsum+rsum=25。上述两个累加操作的时间复杂度为O(n)。45跨越中线子问题的伪代码算法10.4

最大子序列和问题的优化算法二Input:

子序列的起点i、终点j、中间位置kOutput:

跨越中线的最大的子序列和functiong(i,k,j)

//跨越中线的子问题beginlsum←-∞ //中线到左边的最大子序列sum←0fort←kdowntoi

dosum←sum+D[t]lsum←MAX(lsum,

sum)end

forrsum←-∞

//中线到右边的最大子序列sum←0fort←k+1toj

dosum←sum+D[t]rsum←MAX(rsum,

sum)end

forreturn

lsum+rsum18end

begin求左半部分最大值求右半部分最大值时间复杂度为：T(n)=

O(n)46自顶向下分解形成分解树f类问题一直分解下去，形成最小子问题，最小子问题只有一个元素，元素的值就是解。g类问题每层都有，实际累加计算都发生在g类问题中。47子问题的解自底向上合并形成更大子问题的解最底层的f类问题、以及所有的g类问题都可直接求解，求最大值后可依次合并出上一层的解；一直进行下去，合并出原问题（最顶层）的解。48基于“问题分解”的优化算法算法10.4最大子序列和问题的优化算法二Input: 子序列的起点i、终点jOutput:

子序列D[i...j]的最大的子序列和21

function

f(D[1...n],i,j)

//形式相同的子问题22

beginifi=j

then

//最小子问题returnD[i]endif26 k←⌊

(i+j)/2⌋ //计算中线位置27 returnMAX(f(i,k),f(k+1,j),

g(i,k,j)

) //从中线分解问题endbeginInput: 大小为n的顺序表D[1...n]Output:

顺序表D的最大子序列和function

FIND-MAX-SUBSEQ-4(D[1...n])beginres←f(1,n) //原问题输出res35end

begin最小子问题/递归函数出口问题分解与合并/递归调用调用递归函数求解问题时间复杂度是多少？49算法10.4的时间复杂度分析u算法的分解树共有logn层u每一层g函数处理的序列合并起来就是原序列，相当于对原序列进行了一次累加，是O(n)的操作。u总的时间复杂度是O(nlogn)50算法10.4是分治策略分治策略是一种利用问题分解求解问题的策略，其核心思想是分而治之，求解问题时采用分、治、合三个步骤：u

分：将复杂问题分解为与原问题形式相同的、规模更小的独立子问题，子问题可以一直分解下去；u

治：直接求解最小子问题；u

合：将已经求解的子问题的解进行逐层合并，最后得到原问题的解。算法10.4的“分”：将问题分解为2个形式相同的子问题和1个形式不同的子问题；算法10.4的“治”：求解最小的f类子问题，以及g类子问题的解；算法10.4的“合”：合并f类问题和g类问题的解，得到上一层子问题的解。51算法10.4中的无效计算u

分解树共有logn层u

共对原序列进行了logn次重复的累加还有更好的办法吗52一、算法的概念与特征二、算法的复杂度分析三、问题抽象与数学建模四、算法的数据结构及其操作五、算法的控制结构及其表达方法六、算法优化与策略选择优化思想之三：解空间划分53优化思想之三：解空间划分u将序列D[1...n]的所有子序列根据末尾元素的不同分为n个子集。例如，以D[3]结尾的子集为{D[3...3],

D[2...3],

D[1...3]}；u分别对每个子集进行遍历并求出最大子序列和，记为T[1]、T[2]、...、T[n]，例如T[3]是子集{D[3...3],D[2...3],D[1...3]}的最大子序列和，结果为max(-20,-12,1)=

1。u序列T[1...n]中的最大值就是问题的解，T[10]为25，是序列T的最大值，因此是问题的解。如何提高效率：如果生成序列T的效率高，算法的效率就很高54求序列T的方案一：穷举法u一个T[i]的计算方法：遍历所有“以第i个元素结尾的子序列”（起点为k=1，2，...i），分别计算其元素之和，然后取最大值为结果：

T[i]

=

max(S[i]

-

S[k-1]),

k=1,

2,

...

i，S[0...n]为“累加和”序列。u所有T[i]的计算方法：i从1循环到n，依次计算T[i]。求一个T[i]需要进行i次减法运算，时间复杂度为O(n)求所有T[i]的时间复杂度为O(n2)，比算法10.4更差55求序列T的方案二：优化方案uT[i]=max(S[i]-S[k-1]),

k=1,2,

...

i(k是子序列起点，i是终点)u若能找到所有S[k-1]中的最小值，即可得到S[i]-S[k-1]的最大值，即：T[i]

=

S[i]

-

min(S[k-1]),k=1,2,...

iu构造最小累加和序列M

，

令M[i]为序列S[0...i]的最小值，则M[i-1]为序列S[0...i-1]的最小值，即min(S[k-1])，则：T[i]=S[i]-

M[i-1]u

序列M的生成方式：M[i]=min(M[i-1],

S[i])M序列的生成可在O(n)时间内完成求一个T[i]需要进行1次减法运算，时间复杂度为：O(1)求所有T[i]的时间复杂度为O(n)，比算法10.4更优56基于“解空间划分”的优化算法构造序列T时间复杂度为：T(n)

= O(n)构造“累加和”序列S构造序列M序列T的最大值为问题的解算法10.5

最大子序列和问题的优化算法三1

Input:大小为n的顺序表D[1...n]2

Output:

顺序表D的最大子序列和function

FIND-MAX-SUBSEQ-5(D[1...n])begin//构造序列S的第i个元素初始化大小为n+1的序列S[0...n]和M[0...n]初始化大小为n的序列T[1...n]

7 S[0]←08 fori←1ton

do9 S[i]←S[i-1]+D[i]10 endfor

11 M[0]←0fori←1ton

doM[i]←MIN(M[i-1],S[i])

//构造序列M的第i个元素end

forfori←1ton

doT[i]←S[i]-M[i-1]

//利用序列S和序列M计算T[i]end

forres←-∞ //最终结果，初值为负无穷大fori←1ton

dores←MAX(res,

T[i])end

for输出res23end

begin57算法10.5的空间优化：省略序列Tu最终目的是找出所有T[i]中的最大值；u每次完成S[i]-M[i-1]计算时，不保存到T[i]

，直接与res竞争；去掉构造序列T的循环，并省略序列Tres←-∞fori←1ton

dores←MAX(res,

S[i]-M[i-1])end

for计算结果不保存到T[i]，直接与res竞争res←-∞fori←1ton

dores←MAX(res,

T[i])end

for58算法10.5的空间优化：省略序列Mu第i次循环时，仅需访问序列M的前一个元素M[i-1]，不需要访问更早的元素；u用变量msum保存前一次循环的运算结果，省略序列M；ures的更新需要M[i-1]，即前一次循环的值，

因此msum的更新在res的更新之后。msum←0,

res←-∞fori←1ton

dores←max(res,

S[i]-msum)msum←MIN(msum,

S[i])5 end

for去掉构造序列M的循环，并省略序列M计算结果不保存到M[i]，直接参与下一次循环的计算res←-∞fori←1ton

dores←MAX(res,

S[i]-M[i-1])end

for59算法10.5的空间优化：省略序列Su第i次循环只需要访问S[i]；u用变量sum保存S[i]的值；u合并构造序列S的循环；去掉构造序列S的循环，

并省略序列Ssum←0,msum←0,

res←-∞fori←1ton

dosum←

sum+D[i]res←MAX(res,sum-

msum)msum←MIN(msum,

sum)end

for计算结果不保存到S[i]，直接参与计算msum←0,

res←-∞fori←1ton

dores←max(res,

S[i]-msum)msum←MIN(msum,

S[i])5 end

for60空间优化后的算法时间复杂度为：T(n)

= O(n)只需要当前的“累加和”,即S[i]当前“累加和”与上一次循环

的

“

最

小

累

加

和

”

(

即M[i-1])相减，即T[i]计算下一个“最小累加和”，即M[i]算法10.6最大子序列和问题的优化算法四Input: 大小为n的顺序表D[1...n]Output:

顺序表D的最大子序列和function

FIND-MAX-SUBSEQ-6(D[1...n])beginsum←0,msum←0,

res←-∞fori←1ton

dosum←

sum+D[i]res←MAX(res,sum-

msum)msum←MIN(msum,

sum)end

for输出resend

begin61算法效率的比较不同的算法策略在求解同一个问题时有着巨大性能差异62设计算法的基本步骤算法设计是一种循序渐进、精益求精的过程u

对问题进行抽象和数学建模；u

以数学模型为基础设计数据结构，其中逻辑结构应以数学模型中数据的组织结构为基础，存储结构应以便于算法的控制结构操作数据为准则；u

以数学模型和数据结构为基础分析问题的解空间形式；u

设计控制结构对解空间进行遍历，对于每个可能解，使用数学模型中的约束和优化目标进行验证以便找到符合要求的解；u

分析算法是否存在无效计算，选择合适的算法策略去除无效计算。明白了吗？63第11章

难解性问题求解—组合、随机与近似解64本章导图P类问题NP类问题精确解近似解NPC类问题NPC类问题的解算法计算类比与借鉴生物界问题求解思维：过程化理解趋近于降低计算量算法复杂性计算复杂性可求解问题难求解问题概率与随机过程随机遍历/枚举-验证65难解性问题求解—组合、随机与近似解一、可求解与难解性问题二、难解性问题的基本求解策略三、遗传算法的缘起-生物学中的遗传与进化四、计算学科的遗传算法五、用遗传算法求解集合覆盖问题六、遗传算法的进一步探究66一个快递公司要在一个拥有8栋住宅楼的小区设立快递柜。可能的设立点有5处，每个点都有服务覆盖范围（50米）。已知每个快递柜能覆盖哪些住宅楼。问最少需要设立几个快递柜才能覆盖全部住宅楼？快递柜选址问题-贯穿本讲的案例67问：生活中有哪些最优化问题和决定性问题呢？最优化问题与决定性问题【最优化问题】在给定的约束条件下,

求解最优的方案使得目标最大化或最小化的问题。快递柜选址问题：约束条件为“覆盖全部住宅楼”，优化目标为“用最少的快递柜数目满足约束条件”。【决定性问题】回答是和否的问题。例，问题改为：能否建设k个快递柜来满足覆盖全部住宅楼的要求。68精确解的求解方法u对解空间中所有可能的解进行遍历，计算并验证每一个解是否符合约束条件。u依据优化目标选择最优的解。解空间与精确解解空间与最优化问题的精确解u

解空间是由所有可能的解组成的集合。u

最优化问题的精确解指的是所有可能的解中符合约束条件和优化目标的解。69更一般的问题：住宅楼总数为m，快递柜建设点总数为n。可能解的总数：2n。穷举法：对2n个可能解进行验证。时间复杂度：O(2n)。求解快递柜选址问题精确解的方法问：图中的问题解空间的大小是多少？70快递柜建设地点总数n方案总数需要时间5323.2毫秒201百多万100秒501千万亿3570年快递柜选址问题的计算复杂度注：计算机每秒运行百万次，假设验算一个方案需要执行100次基本运算，因此计算机每秒可验算1万个方案。问：试计算n为100时需要多长时间？现实世界中的问题分类l计算机在有限时间内能够求解的(可求解问题)l计算机在有限时间内不能求解的(难求解问题)l计算机完全不能求解的(不可计算问题)71指数级复杂度O(bn),O(n!)多项式复杂度O(1),O(logn),O(n),O(nlogn),

O(nb)可求解与难解性问题如何分类【可求解问题】存在多项式时间复杂度的求解算法的问题。【难解性问题】不存在多项式时间复杂度的求解算法的问题。【快递柜选址问题是难解性问题】快递柜选址问题到目前为止是不存在多项式时间复杂度算法。72【P类问题】多项式问题(Polynomial

Problem)，即：可以找出一个呈现O(na)复杂性算法求出精确解的问题，其中a为常数。P类问题是指计算机可以在有限时间内求出精确解的问题，【NP类问题】非确定性多项式问题(Non-deterministic

Polynomial)，即：可以找出一个呈现O(na)复杂性算法来验证一个解是否正确的非确定性问题。ü有些问题，其答案无法直接计算得到，但可通过间接的猜算/试算来得到，这就是非确定性问题(Non-deterministic)。ü虽然在多项式时间内难于求解，但给定一个解却不难在多项式时间内验证其正确性的问题，即是NP类问题。怎样以复杂性来划分问题73【NP-Hard问题】不仅不能在多项式时间内求精确解，而且不一定能在多项式时间内验证一个解的正确性【NPC类问题】完全非确定性多项式问题(NP-Complete)，即：如果NP问题的所有可能解都可以在多项式时间内进行正确与否的验算，且枚举所有可能解的时间复杂性为指数级别，则为NP-Complete问题。NP-Hard问题和NP类问题的交集是NPC类问题。怎样以复杂性来划分问题74难解性问题求解—组合、随机与近似解一、可求解与难解性问题二、难解性问题的基本求解策略三、遗传算法的缘起-生物学中的遗传与进化四、计算学科的遗传算法五、用遗传算法求解集合覆盖问题六、遗传算法的进一步探究75穷举法或称遍历法：对解空间中的每一个可能解进行计算并验证，直到所有的解都被验证是否正确，便能得到精确的结果---精确解可能是O(n!)或O(an)应该是O(na)近似解求解算法---近似解∆

=

|

近似解

–

精确解

|满意解：

∆充分小时的近似解快递柜选址问题的遍历算法快递柜选址问题的爬山法仿生学算法进化算法，遗传算法，蚁群算法，蜂群算法,

…难解性问题如何求解快递柜选址问题是NPC问题难解性问题76快递柜问题的数学模型快递柜选址问题的约束矩阵（m=8，n=5）住宅楼快递柜x5x4x3x2x1t800011t700010t611010t511000t401100t301100t200101t10000177约束矩阵的行编码行向量A1A2A3A4A5A6A7A8行编码0000100101011000110011000110100001000011快递柜选址问题的约束矩阵（m=8，n=5）住宅楼快递柜x5x4x3x2x1t800011t700010t611010t511000t401100t301100t200101t10000178【快递柜问题的解的编码】X5X

4X

3X

2X

1，Xi为1表示建设第i个快递柜，为0表示不建设。例：解01011表示建设第1、2、4个快递柜。可能解的总数：25=32可能解的编码及其验证【判断一个解X能否覆盖全部住宅楼的方法】u

解X与约束矩阵的行向量依次进行“位与”操作u

如果每一次运算结果都大于0，说明该编码解能覆盖所有住宅楼问：10101能否覆盖全部住宅楼？行向量A1A2A3A4A5A6A7A8行编码000010010101100011001100011010000100001179关于【解】的一组概念假设一个问题的解的形式为x，则：可能解：由x的取值空间/定义域给定的任何一个x值可行解：问题通常有很多约束。满足问题所有约束的x值，才是有效的、可行的近似解：由一个算法在任何一组可行解中求出的最优解满意解：符合用户期望的近似解精确解：所有可行解中的最优解，是问题的最优解【可能解】集合

【可行解】集合

【近似解】集合

【满意解】集合

【最优解/精确解】集合80【解】的质量评价方法：目标函数【例】

X=00111编码中有3个1，第一项的结果为3；00111与各个行编码的“位与”结果分别为00001、00101、00100、00100、00000、00010、00010、00011，结果（十进制）为0的总数是1，因此目标函数的结果为：F(00111)=3+1*8=

11行向量A1A2A3A4A5A6A7A8行编码000010010101100011001100011010000100001181快递柜选址问题的所有可能解的目标函数值82随机搜索策略【难解性问题难以求解的根本原因】解空间太庞大，无法在合理的时间内进行遍历。【什么是随机搜索策略】随机地在解空间中选择若干可能解构成一个子集，子集的大小以算法能在合理的时间内完成遍历为准；在子集中搜索最优的解。【随机搜索策略的本质】牺牲解的质量来换取求解问题的效率。【随机搜索策略的缺陷】最终近似解的质量完全取决于“运气”，是一种“瞎猫碰死耗子”的行为

。83提高随机解的质量【例】解10100，5个二进制位的任何一位的改变，会得到另一个不同的解。【如何提高随机解的质量】从一个可能解出发，沿着某个路径找到质量更高的解。【后继解】一个解的二进制编码中的某一位发生变化（0变1或1变0），结果称为后继解。84导向性随机搜索策略【什么是导向性随机搜索策略】从一个随机的可能解出发，在可到达的所有后继解中，选择质量最高（目标函数值最小）的解作为下一个解，一直迭代下去，直到无法找到质量更高的解，停止迭代

。也叫爬山法。【优点】随着迭代的进行，解的质量会越来越高

。【缺点】不一定能导向最优解

。最终解的质量受初始解的影响很大。85导向性群体随机搜索策略【什么是导向性群体随机搜索策略】随机选择多个可能解作为起点，这些可能解分别使用导向性随机搜索策略搜索近似解，得到一个近似解的集合，最后将集合中目标函数值最低的解作为最终的近似解

。【优点】有多条搜索路径，提高了找到满意解的概率。【缺点】不同的搜索路径是各自独立演化的，路径之间没有交流

。86难解性问题求解—组合、随机与近似解一、可求解与难解性问题二、难解性问题的基本求解策略三、遗传算法的缘起-生物学中的遗传与进化四、计算学科的遗传算法五、用遗传算法求解集合覆盖问题六、遗传算法的进一步探究87关于生物遗传进化的基本观点生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状；染色体是由基因及其有规律的排列所构成的，遗传和进化过程发生在染色体上；生物的繁殖过程是由其基因的复制过程来完成的；通过同源染色体之间的交叉或染色体的变异会产生新的物种，使生物呈现新的性状。对环境适应性好的基因或染色体经常比适应性差的基因或染色体有更多的机会遗传到下一代。遗传与进化 优胜劣汰生物学中的遗传和进化88繁衍后的种群种群新一代种群基因重组新个体的染色体个体A的染色体个体B的染色体染色体B的基因片段染色体A的基因片段个体对环境的适应性:优胜劣汰两个个体新个体染色体与基因将生物体的遗传与进化理解为【过程】89n

种群(Population)vs.

个体(Individual)vs.

染色体(chromosome)n染色体(chromosome)vs.基因(gene)n基因型(Genotype)vs.表现型(Phenotype)n个体的适应度(Fitness)n选择(Selection)n复制((Reproduction)n交配/杂交(Crossover)n

突变(Mutation)识别基本概念90生物学中的问题求解思想生物学中的问题求解过程与步骤计算学科中的问题求解过程与步骤难解性问题难解性问题的解过程/步骤中的设计技巧具体问题类比中创新问题求解的算法91难解性问题求解—组合、随机与近似解一、可求解与难解性问题二、难解性问题的基本求解策略三、遗传算法的缘起-生物学中的遗传与进化四、计算学科的遗传算法五、用遗传算法求解集合覆盖问题六、遗传算法的进一步探究92将生物学中的概念映射为计算学科中的概念生物学中的概念计算学科中的概念解释种群解集/种群若干可能解的集合个体解/个体一个可能解的表现型，本例中即是十进制的X染色体编码解/染色体一个可能解的基因型，本例即是X的二进制编码。X

=

X5X4X3X2X1，

其中Xi=0或1。基因基因解编码中的若干位的Xi适应度适应度对可能解的评价方式，本例直接使用目标函数计算适应度，函数值越小，适应度越高选择选择指从种群(解集)中依据适应度按某种条件选择某些个个体(可能解)复制复制将一个解从一个解集复制到另一个解集交配/杂交交叉即交配/杂交，是新可能解的一种形成方法，即是对两个可能解的编码通过交换某些编码位而形成两个新的可能解的遗传操作突变变异也是新可能解的一种形成方法，它是通过随机地改变一个可能解的编码的某些片段(或基因)而使一个可能解变为一新的可能解的遗传操作93【个体(可能解)的表现形式】X=

0,…,31个体(可能解)的基因形式：染色体X=X5X4X3X2X1,

其中Xi=0

or

1遗传算法求解快递柜选址问题【初始种群生成方式】随机生成6个0～31之间的数，构成大小为6的种群生成初始种群94遗传算法求解快递柜选址问题问：10111为什么被选择2次？【基于竞争的选择操作】以适应度为基础随机选择父本，直接用目标函数作为适应度适应度越高，被选择的概率越大【不能每次都选适应度最高的个体】都选最高的个体，下一代全是一对夫妻的后代，种群无法进化选择个体成为父本95遗传算法求解快递柜选址问题父本交叉产生子代【交叉操作】父本以较高概率（

0.2～0.8

）进行交叉交叉的父本形成新的子代（有性繁殖）未交叉的父本直接复制到子代（单性繁殖）96遗传算法求解快递柜选址问题【变异操作】子代以较小概率发生变异，产生新基因概率通常为0.01～0.201111变异为01101子代变异产生新基因97遗传算法求解快递柜选址问题【迭代与终止】新种群继续选择、交叉和变异，一轮轮迭代若达到终止条件，从种群中选出适应度最高的个体为问题的解最终解为：01011终止条件：找到了满意解或达到指定迭代次数新种群进行迭代或终止98遗传算法求解快递柜选址问题【完整求解过程】u

生成初始种群u

选择个体为父本u

父本交叉或直接复制形成子代u

子代进行变异u

形成新种群u

进行迭代或终止最终解为：01011完整过程图示99难解性问题求解—组合、随机与近似解一、可求解与难解性问题二、难解性问题的基本求解策略三、遗传算法的缘起-生物学中的遗传与进化四、计算学科的遗传算法五、用遗传算法求解集合覆盖问题六、遗传算法的进一步探究100某机构要组织m次讲座，需要租用会议室，有n个会议室可供租用。会议室适合的讲座约束如右表所示。一个会议室可以举办多次讲座。问最少需要租用哪些会议室来完成m次讲座。会议室租用问题问：与快递柜选址问题有什么区别？会议室租用问题的约束矩阵（m=8，n=5）讲座会议室x5x4x3x2x1t800011t700010t611010t511000t401100t301100t200101t100001101什么是集合覆盖问题问：生活中还有什么集合覆盖问题？【两类问题的共性】快递柜选址问题和会议室租用问题都是集合覆盖问题。【集合覆盖问题】给定大小为m的全集U和他的一组子集组成的大小为n的集合S，找到S的一个子集X，使得X的并集V等于全集U，此时X称为一个覆盖。给定(U,S)，求所有可能的覆盖中最小的覆盖。集合覆盖问题的约束矩阵（m=8，n=5）住宅楼/讲座快递柜/会议室x5x4x3x2x1t800011t700010t611010t511000t401100t301100t200101t100001102选择初始种群【随机选点法】在解空间中随机选择若干可能解形成初始种群。优点：设计简单且效率较高。缺点：有可能因为解的不均匀分布而漏掉最优解区域

。【均匀网格法】将解空间划分为j个不同区域并在各区域分别随机抽取个体。优点：避免遗漏优质区域。缺点：设计更复杂。Input:

种群大小k，编码解的长度nOutput:

初始种群的集合populationfunctionGEN-POPULATION(k,n)beginpopulation[1...k]←

空集合fori←1tok

dopopulation[i]

←

0～2n-1之间的均匀随机数end

forreturn

populationend

begin103计算个体的适应度Input:

编码解X，约束矩阵的行编码数组A，全集大小m，编码解长度n。Output:

编码解X的适应度。3functionFITNESS(X,A,m,

n)4

beginpart1←X的二进制编码中1的个数part2←0

//惩罚项fori←1tom

doif

X与A[i]的位与结果是0

thenpart2←part2

+

1

//统计未覆盖数目end

ifend

forreturn

part1+m*part2

//以m为惩罚系数13end

begin【适应度的用途】遗传算法在解空间中搜索满意解的驱动力。【适应度的本质】反映可能解和最优解之间的距离。【适应度的设计方法】以优化目标和约束条件为基础设计，本例使用带惩罚项的目标函数。104选择个体作为父代【随机选择的原则】个体的适应度越强，获选的机会越大【适应度选择策略】计算种群中所有个体的适应度根据适应度为每个个体设置选择概率，适应度较高的个体拥有更高的选择概率交叉前，使用两次选择算法选出两个父本用于交叉择个体Input:

种群集合populationOutput:

population中的一个编码解3functionSELECT

(population)beginfitnesses[1...n]←

population中所有个体的适应度

//计算所有个体的适应度并存入数组probabilities[1...n]←所有个体的选择概率，适应度越高概率越高i←随机产生的1～n间的数字，且probabilities[i]越大，产生i的概率越高X←population[i] //以选择概率为基础选returnX10end

begin105【交叉的策略】固定位置交叉/随机位置交叉、两段交叉/多段交叉父代交叉形成子代【交叉概率】以一定概率（交叉概率，一般0.2~0.8）进行交叉：形成交叉的是有性繁殖，否则是单性繁殖Input:

x1和x2是进行交叉的两个个体，

pc为交叉概率Output:

x1与x2交叉后的两个子代的集合functionCROSSOVER(x1,x2,

pc)beginp

←

0~1之间的均匀随机数

//决定是否交叉的概率children[1...2]←空集合if p

≤

pc

then

//产生交叉pos←

1~SIZE(x1)-1之间的均匀随机数

//决定交叉位置的随机数children[1]

←

x1左边第1~pos位拼接

x2右边第pos+1~n位

//产生一个新个体children[2]

←

x2左边第1~pos位拼接x1右边第pos+1~n位

//产生另一个新个体//x1进行单性繁殖//x2进行单性繁殖else

//不产生交叉children[1]

←x1children[2]

←x2end

ifreturn

childrenend

begin106子代进行随机变异【变异的策略】扰动策略：将编码解中的某个二进制位从0变为1或从1变为0互换策略：将编码解中的不同位置上的两位互换【变异概率】子代发生变异的概率，一般0.01~0.2Input:

一个编码解origin，变异概率pmOutput:

变异后的编码解functionMUTATE(origin,pm)beginr←0~1之间的均匀随机数i