计算理论与算法分析设计：总复习.pptx

计算理论与算法总复习;成绩计算方法;考题类型;CH1算法概述;算法的五个特征

1）有穷性2）确定性

3）输入4）输出5）可行性

算法的定义:Informally,analgorithmisanywell-definedcomputationalprocedurethattakessomevalue,orsetofvalues,asinputandproducessomevalue,orsetofvalues,asoutput.Analgorithmisthusasequenceofcomputationalstepsthattransformtheinputintotheoutput.

;O、o、?、?、?第一种理解方法;渐近分析中函数比较;O、o、?、?、?第二种理解方法;;;;例;例;例;CH2分治法;;;分治法的抽象过程;例1用分治法求n个元素集合S中的最大、最小元素。;;T(n)=2T(n/2)+2;;归并排序（MergeSort);主定理简化版;快排序（QuickSort);快排序---划分过程

;大整数乘法(1962年);求第k小的元素;;求第k个小的元素（选择问题）;线性时间选择问题:;线性时间选择:中位数应用;棋盘覆盖;问题分解过程：

以k=2时的问题为例，用二分法进行分解，得到如下图，用双线划分的四个k=1的棋盘。;循环赛日程表;循环赛日程表;循环赛日程表的推广;CH3动归;方法概述:基本思想;方法概述:适用条件;多段图的最短路问题;多段图的最短路问题;;矩阵链乘法;;货物储运问题;13-6-19;13-6-19;最长公共子序列的结构;子问题的递归结构;CH4贪心法;贪心算法;4.2贪心算法的基本要素;4.2贪心算法的基本要素;4.2贪心算法的基本要素;部分(或者小数)背包问题;n=3,M=20,(v1,v2,v3)=(25,24,15)

(w1,w2,w3)=(18,15,10)

;活动安排:问题描述;;;有限期的任务安排问题;;;;最优装载;4.3最优装载;;排序之车间作业计划模型;CH5回溯法;回溯法;问题的解空间;算法的基本步骤;二类常见的解空间树

①子集树：当所给的问题是从n个元素的集合S中找出满足某种性质的子集时，相应的解空间树称为子集树

叶结点数2n，总结点数2n+1，遍历时间为Ω(2n)

如0-1背包

②排列树：当所给问题是确定n个元素满足某种性质的排列时，相应的解空间树称为排列树

叶结点数n!，遍历时间为Ω(n!)

如TSP问题;回溯算法的一般框架;回溯算法的一般框架（续）;4后问题;;装载问题;问题分析;;;装载问题算法描述;最大团问题;问题分析;voidClique::Backtrack(inti)//计算最大团

{if(in){//到达叶结点

for(intj=1;j=n;j++)bestx[j]=x[j];

bestn=cn;return;}

intOK=1;//检查顶点i与当前团的连接

for(intj=1;ji;j++)

if(x[j]a[i][j]==0){//i与j不相连

OK=0;break;}

if(OK){//选中后仍满足团定义，进入左子树

x[i]=1;cn++;

Backtrack(i+1);

x[i]=0;cn--;}

if(cn+n-ibestn){//不选仍有可能获得更优解，进入右子树

x[i]=0;

Backtrack(i+1);}};子集和问题;子集和问题;背包问题;0-1背包问题;voidbacktrack(inti)

{//有哪些信誉好的足球投注网站第i层结点

if(in)//到达叶结点

更新最优解bestx,bestp;return;

if(cw+w[i]=c){//有哪些信誉好的足球投注网站左子树

x[i]=1;

cw+=w[i];

cp+=p[i]

backtrack(i+1);

cw-=w[i];cp-=p[i];

}

if(bound(i+1)bestp){

x[i]=0;//有哪些信誉好的足球投注网站右子树

backtrack(i+1);}

};;回溯过程