人工智能算法（Python语言版）课件全套 胡矿 第1-9章-算法设计与分析基础 -图分析算法

第1章算法设计与分析基础《人工智能算法》提纲概述算法的基本概念算法效率分析算法的最优、最坏和平均效率算法运行时间估计总结概述(1)人工智能的三大基石：数据，算法，算力；人工智能的本质是算法；算法的优劣决定了智能系统水平高低算法对工程教育毕业要求的支撑：-工程知识：能够将数学、自然科学、工程基础和专业知识用于解决计算机领域的复杂工程问题。-设计/开发解决方案：能够设计针对复杂工程问题的解决方案，设计满

足特定需求的软件系统、模块/组件，并能够在设计环节中体现创新意识，考虑社会、健康、安全、法律、文化以及环境等因素。-研究：能够基于计算机科学与工程的技术和方法对复杂工程问题进行分析与研究，包括设计实验、分析与解释数据、并通过信息综合得到合理有效的结论。概述(2)

学界与业界为实现同样的目标而努力

人们越来越客观地看待学界与业界研究工作的价值，学界与业界的对立逐渐消除、逐渐认可对方的价值

计算机科学的特点需要业界做科研、学界解决实际问题，算法助力克服技术瓶颈学界与业界的合作成为常态，算法的价值得到双方认可当代计算机专业人才工程能力

算法“驾驶员”+“算法造车人”算法设计与分析助力程序设计能力的提升、程序设计水平的提高程序设计能力提升算法设计与分析水平提纲概述算法的基本概念算法效率分析算法的最优、最坏和平均效率算法运行时间估计总结算法的基本概念(1)算法：解决问题的一步一步的方法数据结构+算法=程序

-有了好的算法和数据结构，以某种程序设计语言予以实现

-算法不依赖于特定程序语言，描述求解问题的通用的一般步骤算法的定义与特点算法是一系列解决问题的步骤；对于符合一定规范或约束的输入，能在有限时间内得到所要求的输出；用伪代码（Pseudocode）描述；特点：（1）有穷性：算法在有限时间内完成。（2）确定性：算法的每一步必须是确定的，不能有二义性的解释。（3）可行性：算法中的每一步必须是有意义的，且能达到预期目的。（4）输入：输入的值域必须仔细定义。（5）输出：得到问题的解。（6）同一问题可能存在几种不同的算法，执行效率也会有所差异。算法的基本概念(2)算法的伪代码描述示例提纲概述算法的基本概念算法效率分析算法的最优、最坏和平均效率算法运行时间估计总结算法效率分析(1)效率：运行时间，存储空间计算时间-将操作的执行次数作为计算复杂度-不依赖于程序运行软硬件环境和编程语言等因素且具有一般性的算法效率分析结果-并不是实际执行的分和秒之类的时间（对于相同的运行环境有意义，但在不同处理器和内存等环境下并无意义）增长率

-基本操作：算法中最重要（对算法运行时间的贡献最大）的操作-关注：随着输入规模的增加，算法执行时间变化的趋势-讨论：针对较大规模的输入，运行时间的增长率或增长的阶（Order）基于渐进时间（增长率）对算法进行比较和分组算法效率分析(2)小规模输入会掩盖算法效率的显著差异，因此需要考虑大规模输入x2/83*x

2x+102*logx算法效率分析(3)2类重要操作-比较操作（Comparison）

计算从数值计算发展到数据处理，比较是数据处理中最重要的操作之一

(1)所有元素比较操作等价(2)搜索和排序算法中的基本操作-算术操作（Arithmetic）(1)加法操作（additive）：+,－,递增（increment）,递减（decrement）(2)乘法操作（multiplication）：×,÷,取模（modulus）(3)算法分析中，加法操作和乘法操作分别考虑算法效率分析(4)如何计算增长率？算法运行的渐进时间：去除了低阶项和首项系数后的算法运行时间函数，用渐进时间来表示算法的时间复杂度对规模为n的输入，若算法运行时间为cn2，随着n的增大，正常量c的作用逐渐降低；当与其他运行时间为dn3的算法相比，常量c并没有多大作用若算法运行时间为n2logn+3n2+5n，n越大，低阶项3n2+5n对算法效率影响越小以上算法的运行时间是n2阶、n3阶和n2logn阶的哪几类常见的增长率？

多项式函数（运行时间随着问题规模n的增加呈多项式增长）

指数函数（运行时间随着问题规模n的增加而爆炸性增长，例如2n）-logn、n、n2和n3，分别称为对数函数、线性函数、平方函数和立方函数-nc和nclogn（0<c<1）称为次线性函数，nlogn和n1.5称为次平方函数算法效率分析(5)渐进时间的符号(1)

符号（BigOmega）-

(f)：增长至少与f一样快的函数（增长不比f慢，效率不比f对应算法高）

-描述了一个运行时间的下界令f(n)和g(n)是从自然数集到非负实数集的两个函数，若存在一个自然数n0和一个正常数c，使得对所有的n

n0，f(n)

cg(n)，则称f(n)为

(g(n))，记为f(n)

(g(n))或f(n)=

(g(n))。

算法效率分析(6)(2)

O符号（BigOh）-O(f)：增长不比f快的函数（增长不比f快，效率不比f对应算法低）

令f(n)和g(n)是从自然数集到非负实数集的两个函数，若存在一个自然数n0和一个正常数c，使得对所有的n

n0，f(n)

cg(n)，则称f(n)为O(g(n))，记为f(n)

O(g(n))或f(n)=O(g(n))。

算法效率分析(7)令f(n)和g(n)是从自然数集到非负实数集的两个函数，若存在一个自然数n0和两个正常数c1和c2，使得对所有的n

n0，c1g(n)

f(n)

c2g(n)，则称f(n)为

(g(n))，记为f(n)

(g(n))或f(n)=

(g(n))。(3)

符号-(f)：增长与f一样快的函数

算法效率分析(8)(1)f(n)=(n2

n)/2,g(n)=6n.f(n)=O(g(n))?g(n)=O(f(n))?

g(n)=O(f(n))(2)f(n)=n4+3,g(n)=n5.f(n)=O(f(n))?g(n)=O(f(n))?f(n)=O(g(n))利用极限比较增长次数算法效率分析(9)

算法效率分析(10)O(f)+O(g)=O(f+g)

证明（根据O的定义证明）:

假设F(n)=O(f),G(n)=O(g)

那么，存在c1和n1，使得n

n1时，有F(n)

c1f(n)；

同理，存在c2和n2，使得n

n2时，有G(n)

c2g(n)。假设c3=max{c1,c2}，n3=max{n1,n2}，当n

n3时有

F(n)+G(n)=O(f)+O(g)

c1f(n)+c2g(n)

c3(f(n)+g(n))，

即O(f)+O(g)

c3(f(n)+g(n))。

因此，O(f)+O(g)=O(f+g)。O(f)·O(g)=O(f·g)特性：某些算法是由两个（以上）执行部分组成，该算法的整体效率由具有较大增长率的部分决定，即它效率最差的部分渐进符号的有用特性提纲概述算法的基本概念算法效率分析算法的最优、最坏和平均效率算法运行时间估计总结算法的最优、最坏和平均效率(1)最优情况-当输入规模为n时算法的最短运行时间-无法有效描述算法在一般情况下的时间复杂度，实际中一般不予考虑最坏情况-当输入规模为n时算法的最长运行时间-算法运行时间的上界平均情况-所有规模为n的输入的平均运行时间-实际上，考虑以计算时间为依据的不同输入类（计算时间意义上的等价类），计算所有不同输入类的平均运行时间算法的执行时间只与问题的规模有关、而与输入值无关算法的最优、最坏和平均效率(2)顺序搜索算法的效率分析假设-列表list[1

n]，无重复元素-目标不在列表中，则返回0算法

SequentialSearch(list,target,n)fori=1tondoif(target=list[i])thenreturniendifendforreturn0list:12,5,6,3,9,10,2,11

target:10

搜索过程12,5,6,3,9,10,2,1112,5,6,3,9,10,2,1112,5,6,3,9,10,2,1112,5,6,3,9,10,2,1112,5,6,3,9,10,2,1112,5,6,3,9,10,2,11算法的最优、最坏和平均效率(3)最坏情况分析-2种情况：target与list中最后一个元素匹配；target不在list中-target与list中的每一个元素进行比较-最多n次比较，时间复杂度为O(n)

平均情况分析(1)target总能成功找到（n个位置等概率）

第i个位置匹配，执行i次元素比较操作

(2)target未必能成功找到一共n+1种情况（target在list中：n种；target不在list中：1种）

n+1种情况等概率，平均比较次数：平均情况时间复杂度O(n)提纲概述算法的基本概念算法效率分析算法的最优、最坏和平均效率算法运行时间估计总结算法运行时间估计(1)非递归算法的效率分析步骤：1、确定输入规模；2、确定基本操作；3、考虑基本操作的执行次数是否仅仅与输入规模有关，则按需要进行最优、最坏和平均效率分析；4、建立基本操作执行次数与输入规模n

的求和表达式，即增长率函数；5、通过数学运算和公式化简，确定增长率。算法运行时间估计(2)递归算法的效率分析步骤：1、确定输入规模；2、确定基本操作；3、考虑基本操作的执行次数是否仅仅与输入规模有关。若还与其他因素有关，则按需要进行最优、最坏和平均效率分析;4、建立基本操作数与规模的函数关系，即递推关系/递推式（Recurrencerelation）和初始条件：5.解递推式，确定增长率。使用递推式描述递归算法的时间复杂度，通过求解递推式得到以n为自变量的闭合公式、从而估计递归算法的运行时间

提纲概述算法的基本概念算法效率分析算法的最优、最坏和平均效率算法运行时间估计总结总结算法是计算机、人工智能等学科领域的灵魂问题、算法的基本概念，算法与数据结构、程序的区别与联系算法效率分析：渐进时间，增长率，增长率渐进时间的符号和性质算法的最优、最坏和平均效率分析递归和非递归算法的运行时间估计结语

谢谢！

第2章

分治法《人工智能算法》提纲应用背景和动机分治法的基本思想和一般步骤分治法的适用条件分治法的复杂度分析方法合并排序总结将要求解的较大规模的问题分割成k个更小规模的子问题。应用背景和动机(1)nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=对这k个子问题分别求解-如果子问题的规模仍然不够小，再划分为k个子问题-如此递归地进行下去，直到问题规模足够小，很容易求出其解为止对这k个子问题分别求解，其中分解直到问题规模足够小，很容易求出其解为止合并小规模问题的解，自底向上求出原来问题的解nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)应用背景和动机(2)提纲应用背景和动机分治法的基本思想和一般步骤分治法的适用条件分治法的复杂度分析方法合并排序总结分治法的基本思想和一般步骤(1)分治法（Divide-and-Conquer）：将一个难以直接解决的复杂问题，将其从大到小逐步分解，进而将较易求解的小问题解合并得到原问题的解。

凡治众如治寡，分数是也。

——孙子兵法divide-and-conquer(S)if(|S|<=n0)adhoc(S)//解决小规模的问题

elsedivideSintosmallersubinstancesS1,S2,...,Sk//分解为子问题

fori=1tokdo

yi←divide-and-conquer(Si)//递归求解各子问题

endforreturnmerge(y1,...,yk)//合并各子问题的解

endif分治法的基本思想和一般步骤(2)原问题S子问题S1子问题S2……子问题SkS1的解y1S2的解y2……Sk的解yk问题S的解分治法的基本思想和一般步骤(3)注意：分解得到的子问题之间相互独立子问题使用相同的方法求解尽可能使子问题规模均等（平衡子问题）问题：DAG算法要被执行多少次？算法中的基本操作要被执行多少次？如何分析该类算法的时间复杂度？分治法适合求解什么样的问题?提纲应用背景和动机分治法的基本思想和一般步骤分治法的适用条件分治法的复杂度分析方法合并排序总结分治法的适用条件该问题的规模缩小到一定的程度就可以容易地解决该问题具有最优子结构性质:-该问题可以分解为若干个规模较小的相同问题-该问题的最优解包含着其子问题的最优解

-利用该问题分解出的子问题的解可以合并为该问题的解该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题，并不重复计算公共子问题若子问题不独立，如何处理？提纲应用背景和动机分治法的基本思想和一般步骤分治法的适用条件分治法的复杂度分析方法合并排序总结分治法的复杂度分析方法(1)Adhoc(S),|S|<n0DAC(S)=

DIV(S)+,else

分治算法时间复杂度分析不直观若将分治法映射到四个步骤，且已知每个步骤的计算时间，则分治法的时间复杂度可使用递推关系（Recurrencerelation）进行分析intfactorial(intn){if(n=0)return1returnn*factorial(n

1)}以乘法（*）作为基本操作分治法的复杂度分析方法(2)平衡子问题

-子问题规模大致相同

-若|S|=n,分解为个k个规模为n/m的子问题

-f(n)时间将k个子问题合并为原问题的解计算时间T(n)用递推关系表示为：分治法的复杂度分析方法(3)分治法运算时间的通用分治递推式：

一个规模n的问题，每次被分为a个子问题，每个子问题规模n/b（为简化分析，假设n=bk，k=1,2,3,...）

c：直接求解子问题（规模为tr）时间（常量）

f(n)：子问题分解和子问题解合并的时间提纲应用背景和动机分治法的基本思想和一般步骤分治法的适用条件分治法的复杂度分析方法合并排序总结合并排序(1)引例：合并两个有序子列表{179,285,351},{310,312,652,800}

(1)179<310:{179}(2)285<310:{179,285}(3)351>310:{179,285,310}(4)312<351:{179,285,310,312}(5)652>351:{179,285,310,312,351,652}{179,285,351},{310,312,652,800}{179,285,351},{310,312,652,800}合并排序(2)合并两个有序子列表能高效地完成只包含一个元素的列表是有序的自顶向下将列表划分为只含一个元素的片段

自底向上将有序子列表两两合并起来将列表{first,…,last}中两个有序子列表合并的递归思想：-若first小于last，则将其从中间位置划分为两个子列表-当first=last时,子列表中只含一个元素-将子列表合并起来，大小分别为1、2、4、…,合并排序(3)算法MergeSort(list,first,last)iffirst<lastthen

middle←(first+last)/2MergeSort(list,first,middle)MergeSort(list,middle+1,last)MergeLists(list,first,middle,middle+1,last)endif递归ABMergeLists什么时候首次执行?合并排序(4)示例：列给定表{310,285,179,254,351,423,861,139,450,520}将列表从中间划分为两个子列表310285179254351423861254450520合并两个有序子列表(1)A={310},B={285}C={285,310}(2)A={285,310},B={179}C={179}C={179,285,310}

当列表B中已无元素将剩余元素放到C的末尾下一步执行什么操作?合并排序(5)划分：310285179254351423861139450520合并：(3)A={254},B={351}C={254,351}之前的结果{179,285,310}(4)A={179,285,310},B={254,351}C={179}A={179,285,310},B={254,351}C={179,254}A={179,285,310},B={254,351}C={179,254,285}A={179,285,310},B={254,351}C={179,254,285,310}A={179,285,310},B={254,351}C={179,254,285,310,351}列表A中已无元素

一个隐含二叉树所表示的一系列递归调用栈存储每次调用过程的局部数据合并排序(6)MergeLists(list,start1,end1,start2,end2)(1)indexC←1,finalStart←start1,finalEnd←end2while(start1≤end1)and(start2≤end2)doiflist[start1]<list[start2]then

result[indexC]←list[start1]

start1←start1+1else

result[indexC]←list[start2]

start2←start2+1endif

indexC←indexC+1endwhile列表A中元素值更小列表B中元素值更小While循环什么时候停止执行?合并排序(7)(2)移动剩余元素(3)将结果从C中填回原列表

ifstart1≤end1thenfori←start1toend1do

result[indexC]←list[i]

indexC←indexC+1endforelsefori←start2toend2do

result[indexC]←list[i]

indexC←indexC+1endforindexC←1fori←finalStarttofinalEnddo

list[i]←result[indexC]

indexC←indexC+1endfor无需比较操作!合并排序(8)MergeLists的最优情况-列表A中所有元素都不大于B中最小-nA

次比较(n/2)-例如：A={1,2,3},B={4,5,6}MergeLists的最坏情况-列表A列表B中元素交叉排列时-每执行一次比较操作，将A或B中的一个元素移到列表C中-nA+nB–1次比较(n–1)-例如：A={1,3,5},B={2,4,6}MergeSort算法的执行时间

以元素比较为基本操作的排序问题下界为Θ(nlogn)合并排序最坏情况下比较次数接近以上下界，最优的排序算法合并排序(9)上述的递推式对于n是2的幂的时候成立，如果n是任意的整数（不是2的幂）呢？

递推关系:

结论:-算法MergeSort对一个n个元素的数组排序所需的时间是O(nlogn)，空间是O(n)。-合并排序的计算时间开销仅来自合并，划分本身无需时间开销。合并排序(10)合并排序算法的主要缺点：需要O(n)的额外空间空间开销：额外的result（列表C）空间，递归算法栈的空间改进思路：（1）“在位”的MergeLists，不需要额外的结果数组result；算法过于复杂，只具有理论上的意义（2）非递归合并排序算法；算法没有递归算法直观、容易理解合并排序(11)对比：递归的合并排序算法合并排序(12)对比：非递归的合并排序算法如何选择或设计递归、非递归的合并排序算法？提纲应用背景和动机分治法的基本思想和一般步骤分治法的适用条件分治法的复杂度分析方法合并排序总结总结分治法的适用条件——子问题独立分治法的基本思想——四个步骤分治法的复杂度分析方法——递推式合并排序（递归的思想，递归的算法）——以元素比较为基本操作，源于合并步骤结语谢谢!第3章减治法《人工智能算法》提纲减治法策略拓扑排序总结减治法策略大规模核酸检测：在席卷全球的新冠病毒感染检测和疫情防控中，由于人口众多，如果对每个人的核酸检测样本逐一检测以确诊感染病毒，实施难度较大。多人混检降低大规模筛查成本：针对40人以内的待检测人员群体，可将被检测人员根据人数均分为两组进行核酸混样检测，将每组检测人员的全部样本放到一起统一检测。随着核酸检测成本的逐渐降低，混检数量从40减少到10和5等。逐步缩小筛查范围：如果是阴性，则表明该组被检人员均不是病毒感染患者；如果是阳性，则表明该组被检人员中存在病毒感染患者。然后，对该组人员做进一步分组，继续进行核酸混样检测，循环往复，直至找出患者。减治法减治法策略减治法（Decrease-and-Conquer）利用给定规模与较小规模问题解之间的关系，从顶至下（递归）或从底至上（非递归）求解问题的一种方法3种类型（1）减常量法：常量通常为1即减1法，也有减2的（如奇偶数分别处理）（2）减常因子法：常因子通常为2（减半技术）（3）减可变规模法：规模减小的模式不同常量为1常量因子为2提纲减治法策略拓扑排序总结拓扑排序(1)问题描述假设我们要安排一系列任务，如任务分工、教学计划中的各门课程的安排顺序（先修课），项目中各子课题的研究顺序，建筑项目等每个任务只有其当先决条件具备时，才能着手安排这个任务去完成找到在满足先决条件情况下，各个任务如何安排的一个线性序列（先决条件不矛盾）例如：5门必修课的集合{C1,C2,C3,C4,C5}，学生必须修完这些课程。先决条件：1）C1和C2没有先决条件2）修完C1和C2才能修C33）修完C3才能修C44）修完C3和C4才能修C5问题：-学生按什么顺序学习这些课程？-解不唯一？拓扑排序(2)建模——图顶点——任务，边——某个任务的先决条件(1)有向图：任务之间有先后关系（有向边）(2)无环图：若为有环图，回路中就存在相互矛盾的条件，问题无解拓扑排序有解的图，必然是有向无环图基于深度优先遍历的拓扑排序-执行一次深度优先查找，记住顶点变成死端（出栈）的顺序-拓扑排序的一个解：将出栈次序反过来基于减一技术的拓扑排序-在余下的有向图中找一个源（没有入边的顶点），删除该源及出边-源不存在，算法停止-拓扑排序的一个解：顶点被删除的次序拓扑排序(3)

输入：G：给定n个顶点、m条边的有向无环图输出：List或False：输出存储拓扑序列顶点的列表，或不存在拓扑序列

拓扑排序(4)基于减一技术的拓扑排序（源删除算法）C1C2C4C3C5删除C1C2C4C3C5删除C2C4C3C5删除C3C4C5删除C4C5拓扑排序表：C2C1C3C4C5拓扑排序(5)课程修读的先后次序拓扑排序拓扑排序(6)源删除算法的实现——基于数组（图存储：邻接矩阵）用一个入度数组保存每个顶点的入度（无取出规则）找到入度为0的点，将其存入数组中，再将其从图中删除（与它相关的边都删除，相邻的顶点的入度均减1）重复步骤(1)执行，直至所有的顶点都被找到为止时间复杂度为O(n2)（即图的遍历）源删除算法的实现——基于队列（图存储：邻接表）(1)在图中找出所有无先决条件的源顶点，将它们全部入队（取出规则）若无源，算法停止，输出记录的顶点序列，得到解（无未访问顶点）(2)队头顶点出队（实现删除操作），且按出队顺序记录顶点，并同时删除

从这个顶点出发的所有的边（队列的出入队顺序相同）(3)返回步骤(1)执行时间复杂度为O(n+e)（初始源顶点O(n)，基于队列找邻接点O(e)）结语谢谢!第4章

贪心法《人工智能算法》提纲应用背景和动机贪心算法的基本思想哈夫曼编码总结应用背景和动机(1)背景：主播带货已成为了一种新的产品推销手段。为响应国家脱贫攻坚和乡村振兴战略，边远山区的地方政府也采取主播带货的方式推广农产品。例如：假设一批农产品要被想被大众熟知，则其影响因子需要达到1.3，现有3类主播，其中A类主播可帮助农产品提高0.4的影响因子，B类主播可帮助农产品提高0.3的影响因子，C类主播可帮助农产品提高0.1的影响因子。问题：应该如何安排主播带货，能够在最少的主播数量下帮助政府使得该农产品被大众熟知？直观的方案：尽量选择影响因子高的主播，即选择3名A类主播和1名C类主播，就可在最少的主播数量下让这批农产品的影响因子达到期望值。应用背景和动机(2)优化问题（Optimizationproblem）

不仅要找到答案，且要找到最佳答案贪心算法（Greedyalgorithm）

有时对优化问题能有较好的解决方案贪心算法分阶段执行，每一个阶段：当考虑做何种选择时，只考虑对当前问题最佳的选择，而不考虑其子问题的结果希望通过每一个步骤的局部最优（Localoptimum）而得到全局最优（Globaloptimum）未必能得到最优解应用背景和动机(3)运行9个作业，其时间分别为3,5,6,10,11,14,15,18,20

共有3个处理器，可执行这些作业按照最长时间作业优先的原则，将作业安排到空闲处理器201815141110653P1P2P3完成作业所需时间为18+11+6=35这一方案并不差，但是可能有更好的方案引例：多机调度应用背景和动机(4)若按照最短时间作业优先的原则，结果如何？201815141110653P1P2P3以上方案并不是一个好的方案，完成作业所需时间为6+14+20=40注意到：贪心算法本身能高效地执行每个阶段所需：选择当前最小或最大者应用背景和动机(5)显然，该方案是最优的，仍可能有其他最优方案如何得到以上最优方案？-尝试所有作业安排给处理器的可能方案，选择最短完成时间-需指数计算时间

更好的方案：201815141110653P1P2P3结论：贪心算法具有较高效率，其答案从实际应用的角度看已足够好提纲应用背景和动机贪心算法的基本思想哈夫曼编码总结贪心算法的基本思想1、贪心选择性质所求问题的整体最优解，希望通过一系列局部最优的选择

（贪心选择）——贪心算法可行的第一个基本要素通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题每一步对目前构造的部分解做一个扩展，满足：可行（满足约束）、局部最优、不可取消（贪心算法与动态规划算法的主要区别）

2、最优子结构性质问题的最优解包含其子问题的最优解证明贪心算法的正确性（针对最优化问题的求解）：-证明每一步所作的贪心选择最终导致问题的整体最优解-数学归纳法提纲应用背景和动机贪心算法的基本思想哈夫曼编码总结哈夫曼编码(1)背景-哈夫曼编码广泛地用于数据文件压缩-压缩率通常在20%～90%之间（变长码）-哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式-给出现频率高的字符较短的编码，出现频率较低的字符以较长的编码，可以大大缩短总码长前缀码-尽可能多地压缩文件、源文件很容易被重建-任一字符的代码(0,1序列)都不是其他字符代码的前缀——完全二叉树T-满足前缀约束，则编码无二义性-平均码长：字符c出现的频率为f(c),在T中的深度为dT(c)哈夫曼编码(2)哈夫曼编码（Huffmanencoding）算法为贪心法选择并合并最小出现频度的两个数字平均编码长度0.22*2+0.12*3+0.24*2+0.06*4+0.27*2+0.09*4

=2.42哈夫曼编码能得到最优编码

2212246279

ABCDEF152746100A=00

B=100

C=01

D=1010

E=11

F=101154编码结果哈夫曼编码(3)

哈夫曼编码(4)哈夫曼编码算法正确性证明的思路对最优前缀码二叉树T作修改得T，T

表示对C做出贪心选择得到的最优前缀码，x和y是T

中最深叶子且为兄弟（树T

与T具有相等的平均码长）。xybcTbcxyT

T中：

f(b)f(c)

f(x)f(y)

x和y是具有最小频率的两个字符

f(x)f(b)

f(y)f(c)T

是对C做出贪心选择的前缀编码树提纲应用背景和动机贪心算法的基本思想哈夫曼编码总结总结应用背景和动机贪心算法的基本思想和关键-贪心选择性质-最优子结构性质-贪心选择标准贪心算法的重要实例：哈夫曼编码贪心算法的正确性证明思路：数学归纳法结语谢谢！第5章

动态规划法《人工智能算法》提纲引例动态规划法的基本思想动态规划法的适用条件矩阵连乘问题0-1背包问题总结引例(1)Fibonacci序列1,1,2,3,5,8,13,…递归定义为：

分治算法（递归）：计算f(n)步骤：if(n=1)or(n=2)thenreturn1elsereturnf(n

1)+f(n

2)endIf展开递推式：算法简洁明了

对过程重复调用

重复调用数量巨大

T(n)为n的指数

不是有效的算法！线性时间的算法：从f(1)自底向上计算直到f(n)？引例(2)步骤1：用f(n)存储Fibonacci数列中第n个数的值；步骤2：步骤3：以自底向上的方法计算步骤4：在数组中分析构造出问题的解n012345678910f(n)011235813213455算法：A[0]

←

0;A[1]←

1fori

←2tondo

A[i]

←A[i

1]+A[i

2]returnA[n]时间复杂度：O(n)提纲引例动态规划法的基本思想动态规划法的适用条件矩阵连乘问题0-1背包问题总结动态规划法（DynamicProgramming）与分治法类似，其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=动态规划法的基本思想(1)经分解得到的子问题往往不是互相独立的不同子问题的数目常常只有多项式数量级在用分治法求解时，有些子问题被重复计算了许多次nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)动态规划法的基本思想(2)保存已解决的子问题的答案，在需要时再找出已求得的答案利用已得到的小规模问题的答案构造待求解的大规模问题的答案可以避免大量重复计算，从而得到多项式时间算法Thosewhocannotrememberthepastaredoomedtorepeatit.——GeorgeSantayana,ThelifeofReason,BookI:IntroductionandReasoninCommonSense(1905)动态规划法的基本思想(3)思想，就像幽灵一样……在它自己解释自己之前，必须先告诉它些什么——查尔斯.狄更斯《董贝父子》提纲引例动态规划法的基本思想动态规划法的适用条件矩阵连乘问题0-1背包问题总结动态规划的适用条件(1)1、最优子结构-问题的最优解包含了其子问题的最优解（多阶段决策）-最优子结构是问题能用动态规划算法求解的前提-利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优值逐步构造出整个问题的最优值（自顶向下得到最优解）-同一个问题可以有多种方式刻划它的最优子结构2、重叠子问题-每次产生的子问题并不总是新问题，有些子问题被反复计算多次-对每一个子问题只解一次，自底向上递归求值，并把中间结果存

储起来以便以后用来计算所需要的解-通常不同的子问题个数随问题的大小呈多项式增长（多项式时间）动态规划法的适用条件(2)Fibonacci(6)Fibonacci(5)Fibonacci(4)Fibonacci(4)Fibonacci(3)Fibonacci(3)Fibonacci(2)Fibonacci(2)Fibonacci(1)Fibonacci(2)Fibonacci(1)Fibonacci(3)Fibonacci(2)Fibonacci(2)Fibonacci(1)动态规划法对许多组合优化问题特别有效！

动态规划法的基本步骤找出最优解的性质，并刻划其结构特征递归地定义最优值以自底向上的方式计算出最优值（填表）根据计算最优值时得到的信息，构造最优解提纲引例动态规划法的基本思想动态规划法的适用条件矩阵连乘问题0-1背包问题总结矩阵连乘问题(1)引例

利用标准的矩阵乘法计算矩阵M1(210),M2(102),M3(210)的乘积(1)(M1M2)M3:2102+2210=80次乘法(2)M1(M2M3):21010+10210=400次乘法

结论：不同的乘法执行顺序，乘法次数相差很大！

矩阵连乘问题给定n个矩阵{A1,A2,…,An}，其中Ai和Ai+1可乘,i=1,2,…,n

1,确定这n个矩阵乘积的计算次序，使得所需乘法次数最少说明：矩阵乘法满足结合律，连乘的计算次序可由加括号方式确定

计算次序完全确定——完全加括号——按此次序进行2个矩阵相乘矩阵连乘问题(2)穷举搜索法

设前k个矩阵有P(k)种加括号方式，对每一个k，有P(k)P(n

k)种加括号方式1,1,2,5,14,42,132,429,1430,4862,16796,…P(n)随n呈指数增长！

矩阵连乘问题(3)递推关系式

记为A[i:j],最少乘法次数记为m(i,j),Ai的维数为pi

1

pi计算次序：-计算量计算A[i:k]的耗费+计算A[k+1:j]的耗费+A[i:k]乘A[k+1:j]的耗费-最优子结构性质计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的-重叠子问题性质？矩阵连乘问题(4)递推关系式m[i,j]的递推关系式:子问题：i,j的不同组合:最多(n2)个矩阵连乘问题(5)例如：若n=6,m(2,5)为以下三个耗费的最小值：-m(2,2)+m(3,5)+p1

p2

p5

-m(2,3)+m(4,5)+p1

p3

p5

-m(2,4)+m(5,5)+p1

p4

p5考虑两个方向：-m(i,i)

m(i,j-1)-m(i+1,j)m(j,j)

计算：-m(i,i),m(i+1,j)

m(i,j-1),m(j,j)决策：

min{m(i,j)},i

k<jm(1,6)m(1,5)m(1,4)m(1,3)m(1,2)m(1,1)m(2,6)m(2,5)m(2,4)m(2,3)m(2,2)m(3,6)m(3,5)m(3,4)m(3,3)m(4,6)m(4,5)m(4,4)m(5,6)m(5,5)m(6,6)矩阵连乘问题(6)依据其递归式以自底向上的方式进行计算（最优值）matrixChain(p[1..n+1],m[1..n][1..n],s[1..n][1..n])n←p.length

1fori=1tondo

m[i][i]←0endforforr=2tondofori=1ton

r+1do

j←i+r1

m[i][j]←m[i+1][j]+p[i

1]*p[i]*p[j]

s[i][j]←ifork=i+1tojdo

t←m[i][k]+m[k+1][j]+p[i

1]*p[k]*p[j]ift<m[i][j]then

m[i][j]←t

s[i][j]←kendifendforendforendforAi(Ai+1…Aj)(Ai…Ak)(Ak+1…Aj),i<k<j矩阵连乘问题(7){m(i,j)}

计算时间：

设一次乘法的代价为c.那么

所需空间：15

535

153035A3A2A120

2510

205

10A6A5A4提纲引例动态规划法的基本思想动态规划法的适用条件矩阵连乘问题0-1背包问题总结0-1背包问题(1)问题-给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?-特殊的整数规划问题：求一个n元0-1向量{x1,x2,…,xn}

目标：约束条件：0-1背包问题(2)最优子结构性质-设m(i,j)为背包剩余容量为j时考虑装入1~i种物品的最大价值-m(i,j)是下面两个量的最大值(考虑物品i)：(1)m(i–1,j):在容量为j的背包中装入1~i–1的物品，不装入物品i价值最大(2)m(i–1,j–wi)+vi:必装入物品i，在容量为j–wi的背包中装入1~i–1的物品的最大价值，再加上物品i的价值vi

(j

wi)递推式0-1背包问题(3)用一个(n+1)(C+1)的矩阵(表)来计算m(i,j),逐行填表算法:knapsack输入:

n种物品的重量和价值:{w1,w2,…,wn},{v1,v2,…,vn};背包容量C

输出：m(n,C)

算法：fori=0tondo

m[i,0]←0endforforj=0toCdo

m[0,j]←0endforfori=1tondoforj=1toCdo

m[i,j]←m[i

1,j]ifwi

jthen

m[i,j]←max{m[i,j],m[i

1,j

wi]+vi}endifendforendforreturnm[n,C]计算时间：O(nC)伪多项式时间！0-1背包问题(4)例如：若背包容量C=9,4种物品的重量和价值分别为{2,3,4,5}和{3,4,5,7},尽可能将物品装入背包，并使总价值最大。510的表：012345678900000000000100333333332003447777730034578991240034578101112最优值：最大价值为12最优解：装入物品1,2,3;装入物品3,4m(i,j)的计算只与m(i–1,0)~m(i–1,j)的值相关0-1背包问题(5)注意到：-求解给定问题时，有些较小子问题的解通常并不需要（填表时，i和j都以1递增）-自底向上：只有背包容量增加到能装入一个物品时，价值才增加（跃变）

自顶向下：递归求解，子问题重复，效率低-带记忆功能：自顶向下递归求解+自底向上表格MFKnapsack(i,j)//调用MFKnapsack(n,C)

//数组w[1..n]、v[1..n]、表m[0..n,0..C]是全局变量

初始化m[0..n,0..C]←

1；m[0,0]←0ifm[i,j]<0then//未计算，递归计算m[i,j]；否则，查表得m[i,j]ifj<withenm[i,j]←MFKnapsack(i-1,j)else

m[i,j]←max(MFKnapsack(i

1,j),

vi+MFKnapsack(i

1,j

wi))returnm[i,j]//直接返回结果（>=0,查表）或计算结果(<0)0-1背包问题(6)讨论-带记忆功能算法的效率与自底向上算法效率类型一样，提高效率不会超过一个常数因子-填表的空间开销较大，如何优化？-O(nC)伪线性时间复杂度，人们不希望复杂度与C有关，如何处理？-考虑近似求解，如何设计算法（贪心算法）？提纲引例动态规划法的基本思想动态规划法的适用条件矩阵连乘问题0-1背包问题总结总结动态规划的基本思想、适用条件，所解决问题的主要特征动态规划方法解决问题的一般方法和步骤、多阶段决策问题的特征和最优化原理动态规划的重要算法实例：-矩阵连乘问题的动态规划算法-0-1背包问题的动态归划算法结语谢谢！第6章回溯法《人工智能算法》提纲回溯法的基本思想n后问题总结引例(1)8-皇后问题QQQQQQQQ

图的m-着色问题不存在用穷举搜索之外的方法来解决问题引例(2)0-1背包问题的回溯分析-n=3,w={16,15,15},p={45,25,25},c=30-所有可能的情况vs.减小了的搜索空间cw=16bestp=cp=45cw=15cp=25cw=30bestp=cp=50rp=25rp<bestp减小了的搜索空间

回溯法的基本思想(1)问题的提出-很多问题通过穷举搜索数量巨大但有限多个可能性可以获得问题的解-很多问题不存在用穷举搜索之外的方法来解决问题的算法-找出问题的解集、回答什么是满足约束条件的最佳解、……回溯法概述-系统化的搜索，并且希望能将搜索空间尽可能减少-有组织的搜索，常常可以避免搜索所有的可能性-适用于解一些组合数（解空间）相当大的问题-问题的解向量：回溯法希望一个问题的解能够表示成一个n元式(x1,x2,…,xn)的形式回溯法的基本思想(2)问题的解空间

-显约束：对分量xi的取值限定-隐约束：为满足问题的解而对不同分量之间施加的约束-解空间：解向量满足显式约束条件的所有元组；将解空间组织为树问题状态的生成-扩展节点、活节点、死节点-深度优先的问题状态生成回溯法提出-避免无效搜索、提高效率——利用约束函数和限界函数来处死那些实际上不可能产生所需解的活节点，以减少问题的计算量-

具有限界函数的深度优先生成法——回溯法回溯法的基本思想(3)遍历子集树需O(2n)计算时间（最坏）

遍历排列树需要O(n!)计算时间（最坏）

backtrack(intt)ift>nthenoutput(x)elsefori←0to1do

x[t]←iif(legal(t))backtrack(t+1)endforbacktrack(t)ift>nthenoutput(x)elsefori←ttondoswap(x[t],x[i])if(legal(t))backtrack(t+1)swap(x[t],x[i])endfor子集树与排列树回溯法的基本思想(4)求解思路-确定解空间结构-深度优先搜索解空间+剪枝函数常用剪枝函数-用约束函数在扩展节点处剪去不满足约束的子树（问题本身的约束）-用限界函数剪去得不到最优解的子树（相对于已得到的解）主要特征-不需要存储整棵搜索树，只需存储根到当前扩展节点的路径-设h(n)为从根到叶的最长路径长度-对于子集树解空间——O(2h(n))

对于排列树解空间——O((h(n))!)提纲回溯法的基本思想n后问题总结n后问题(1)问题-在n×n格的棋盘上放置彼此不受攻击的n个皇后-n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上算法思想

-解空间：完全n叉树-解向量：(x1,x2,…,xn)-每行放一个皇后，x[i]表示皇后i被放在第i行x[i]列，约束：(1)(2)n后问题(2)n皇后问题的回溯算法booleanplace(k)forj=1tokdoif|k−j|=|(x[j]−x[k]|)or|x[j]=x[k]|thenreturnfalsereturntrueendforvoidbacktrack(t)

ift>nthensum←sum+1elsefori=1tondo

x[t]←i

ifplace(t)thenbacktrack(t+1)endfor时间复杂度：O(nn)和蛮力法相比？

初始化：

fori←0tondo

x[i]←0调用：

backtrack(1)n后问题(3)4-后问题的回溯法求解示例生成子集树中的27个节点n后问题(4)4-后问题的蛮力法求解示例

回溯法与蛮力法相比，优势何在？n后问题(5)

当n较小时，蛮力法优于回溯法；当n较大时，回溯法优于蛮力法；n越大，回溯法的优势越显著结论：提纲回溯法的基本思想n后问题总结总结(1)回溯法效率分析-

好的约束函数能显著地减少所生成的节点数

，往往计算量较大

-考虑生成节点数与约束函数计算量之间的折衷重排原理-尽可能减小搜索空间-对于许多问题而言，在搜索试探时选取x[i]的值顺序是任意的-在其他条件相当的前提下，让可取值最少的x[i]优先总结(2)回溯法的基本思想-解空间-深度优先搜索+剪枝函数-时间复杂度分析回溯法的重要算法实例：n后问题结语

谢谢！第7章

分支限界法《人工智能算法》提纲分支限界法的基本思想0-1背包问题总结引例0-1背包问题-n=3,w={16,15,15},p={45,25,25},c=30-所有可能的情况vs.减小了的搜索空间cw=16bestp=cp=45cw=15cp=25cp=0rp=25cp+rp<bestpcw=30bestp=cp=50FIFOvs.

最大可能节点优先?分支限界法vs.回溯法分支限界法与回溯法的区别(1)求解目标-分支限界法：适于求解满足约束条件的最优解-回溯法：找出解空间树中满足约束条件的解（一个或多个可行解）(2)搜索方式-分支限界法：广度优先、或最优目标函数优先-回溯法：深度优先分支限界法的节点生成-选择一个活节点为扩展结点-生成扩展节点的所有儿子节点-可行（可能）的儿子节点加入活节点列表分支限界法的基本思想(1)分支限界法中搜索树空间扩展（1）队列式(FIFO)分支限界法按照队列先进先出（FIFO）原则选取下一个结点为扩展节点（2）优先队列式(minHeap/maxHeap)分支限界法按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点“优先队列式分支限界法”更适用于优化问题?（1）和（2）搜索到叶子结点——找到一个最优解？确定搜索树（根据显约束确定内部结点的分支数）分支限界法的基本步骤？分支限界法的基本思想(2)分支限界法解决优化问题的基本思路-确定解空间树的结构-确定目标函数，作为结点扩展的依据-确定优先队列和优先级：最大堆/最小堆（目标函数最优）-最优目标函数优先+剪枝函数常用剪枝函数-用约束函数在扩展节点处剪去不满足约束的子树（问题本身的约束）-用限界函数剪去得不到最优解的子树

上界/下界限界函数

互相控制的目标函数约束

将可能导致最优解的活结点加入优先队列中提纲分支限界法的基本思想0-1背包问题总结0-1背包问题(1)基本思想

-解空间树：子集树，一个物品要么装入（左孩子）、要么不装入（右孩子）

4种物品的重量和价值分别为{4,7,5,3}和{40,42,25,12}，背包容量为100-1背包问题(2)-搜索空间扩展：优先队列——最大堆-优先级

节点i的价值上界ub=已装入物品的价值+剩余空间装满获得的最大价值-剪枝策略

<1>左子树：装入w[i]，若ew+w[i]<c，则可行若cp+p[i]>bestp则bestp

cp+p[i]

下一层活节点优先级：heap.addNode(ub,cp+p[i],cw+w[i],i+1)<2>右子树：不装入w[i],ub

bound(i+1)若ub>bestp，则可行

下一层活节点优先级：heap.addNode(ub,cp,cw,i+1)预处理：类似背包问题0-1背包问题(3)算法主要步骤：ifcw+w[i]<=c

thenifcp+p[i]>bestpthen

bestp

cp+p[i]

heap.addNode(ub,cp+p[i],cw+w[i],i+1)endifub

bound(i+1)ifub>bestp

then

heap.addNode(ub,cp,cw,i+1)endifnode

heap.removeMax()cw

node.weightcp

node.profitp

node.ubi

node.level如何实现bound的计算？0-1背包问题(4)上界bound的计算-预处理：将输入按照单位重量价值的顺序排序-计算bound：

cleft

c

cw

whilei<=nandw[i]<=cleftdo