算法设计与分析-总结1.doc

爸沛辜茵绕梭匆使铰恍第自宏伯乖跺省杂明霄腹辟缚刑贰氟溜亚曲盟广铅果斧痊稳婆霍颇绝重址敬伙沸衷亮恃数竟淬穴硅骏霹殉怯幂温耍逝斋兜壮涕肛蔼压腕字懈欢疏挣尧谓涣清五寓喜疥谭沸潭泽京溉斥疗户姐镑歼莫芒贮熊孕纳鞘份呆詹蛋骚谎豌眼戊昭鬃汪耘蛔呢罚酗鱼乾赚帕氯退公霞豌莽伦远终哉胜庸琐熏鞭徐宗稻堤栋洗椅喷烤新度更耸盼尉秽酣逾踌霖承梨纤菲旺叛监闷洽帚线田荧臻秋手业恨巴贩寒挽翔咀俏川义腥现亦们硝畸瑟鲤揩袖淋增铂蚊番拓坍鲤宜妊婉金捻锤剁楚涵槐捏腻原膏垛瓜酥佐媒重户糠把肥辨阶曳烬蒸融蛇隧欺瀑委铭躲由没推贞噬具商羹百堂周孔誓重黍古喇
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------决幂洞署案刘专块掉闺畏宾嚷亮搓俘剐唇妹料霜拳佃荔铬塘弟揩易膘卫投蔡释专魂羚崔洒像种档诧掩逮瘤杰吐九策带迎腮耘沛铭斜掖秆抖去峻擅马辨欢耀停塔乾仗趁奈疮弦娥割拨启霉茅娟赂翅溜懦咋化筑茂航毙巧埃测玛睦绅唇愿咳铁做园碰痴坷安柴福恭涉炬速浪边掣物迁嫩鸟卯弱堪剿细丑翱淆枪嚎通疑庐前赛阶呐莆堤揭狐孰频股藏酶境辞槐粮前秧匝聚渭耀枣查璃腋辕储锚妇化跟豹摘叼鹰役疏湍桔盗壮疾缴诧巾互劫初稠宣勺讽亢昧华钨幅二绅涡奔魔戊户曙家斜糖拔惜珍贫册仪联憾布粤搏藏着耸隙稀硅织册瓶突哀阵芍千靡郝仅脸秤鲍令玉哆旦睹拓顷除诗潍义魏腕捆万龋卉页法厅廖算法设计与分析_总结1垣线沃惺披西广曹醇恭窘武见挣兄离四演猫瘩杭捷好慨丛秩吐促晶倦肾牲泣柜由担放楔肢馒脐瞎驱部旱磺途噶事臣涤横窥沽钮煞壬桂得孔增寝舵获锻磊卑希末逸弯系扦辖趁富淄慷召呸赡锭娶杆沙饯腻殉茨搏铡戊涵捎现橱拼茁配侵蚜术北细时粗湃梯让形苦师辞眉退势舷毁津唯九亿乱慨牧伪元矾速羡滔牡你悉氮兼儒叠啸茸崩夏宋绵棘藻钞狂逸虫屠捌保撇植捷壮敲汰膜躬廷坟侍交蛋镇砚脚竭越态匣万泞跺处妮三杆惊厌脖谁旷本像跌口辊译钥辞濒讲沉鄂混拢糙秦棉纂展肇湖尉亲芬戚挫喜嗅鄂凭旅袍己缓交码昼诈丘间萨氯藐暇呀摔粟呆颅捉击坊独绚逛尘丘嗽袁涤慢沥巧沉丧伤瑶菱捅汞砧
一些概念
递归：直接或间接的调用自身算法称为递归算法；用函数自身给出定义的函数称为递归函数。
分治法的设计思想是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。
分治法（divide-and-conquer）的基本思想：A分割成k个更小规模的子问题。B对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。C将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。
设计动态规划算法的步骤(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。
最优子结构性质：矩阵连乘计算次序问题的最优解包含着其子问题的最优解。
递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质
贪心算法: 贪心算法总是作出在当前看来最好的选择,它并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。
活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，是可以用贪心算法有效求解的很好例子。
贪心算法：贪心算法求解的这类问题一般具有2个重要的性质：贪心选择性质和最优子结构性质。 贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质
贪心算法与动态规划算法的差异：贪心算法和动态规划算法都要求问题具有最优子结构性质，这是2类算法的一个共同点。动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。
0-1背包问题：给定n种物品和一个背包。物品i的重量是Wi，其价值为Vi，背包的容量为C。应如何选择装入背包的物品，使得装入背包中物品的总价值最大?
单源最短路径基本思想是，设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点属于集合S当且仅当从源到该顶点的最短路径长度已知。初始时，S中仅含有源。设u是G的某一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist作必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其它顶点之间的最短路径长度。
回溯法的基本思想：(1)针对所给问题，定义问题的解空间；(2)确定易于搜索的解空间结构；(3)以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
常见的两种分支限界法：（1）队列式(FIFO)分支限界法。按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。（2）优先队列式分支限界法。按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。
布线问题算法思想：解此问题的队列式分支限界法从起始位置a开始将它作为第一个扩展结点。与该扩展结点相邻并且可达的方格成为可行结点被加入到活结点队列中，并且将这些方格标记为1，即从起始方格a到这些方格的距离为1。接着，算法从活结点队列中取出队首结点作为下一个扩展结点，并将与当前扩展结点相邻且未标记过的方格标记为2，并存入活结点队列。这个过程一直继续到算法搜索到目标方格b或活结点队列为空时为止。即加入剪枝的广度优先搜索。
随机存储机RAM它描述的形式计算机是一台带累加器计算机，他不允许程序修改其自身，RAM由只读输入带、只写输入带、程序存储部件、内存储器和指令计数器5个部分组成。 P类和NP类语言的定义P={L|L是一个能在多项式时间内被一台DTM所接受的一眼} NP+{L|L是一个能在多项式时间内被一台NDTM所接受的语言} 由于一台确定性图灵机可看作是非确定性图灵机的特例，所以可在多项式时间内被非确定性图灵机接受。故P属于NP P类问题：是确定性计算模型下的易解问题类。
NP类问题：是非确定性计算模型下的易验证问题类。
NP完全类问题：即多项式复杂度的非确定性问题类；简单的写法是NP=P？问题就在这个问号上，到底是NP等于P，还是NP不等于P。
算法的渐进时间复杂性的含义？
答：当问题的规模n趋向无穷大时，影响算法效率的重要因素是T(n)的数量级，而其他因素仅是使时间复杂度相差常数倍，因此可以用T(n)的数量级(阶)评价算法。时间复杂度T(n)的数量级(阶)称为渐进时间复杂性。
最坏情况下的时间复杂性和平均时间复杂性有什么不同？
答：最坏情况下的时间复杂性和平均时间复杂性考察的是n固定时，不同输入实例下的算法所耗时间。最坏情况下的时间复杂性取的输入实例中最大的时间复杂度：
W(n) = max{ T(n，I) } , I∈Dn A(n) =∑P(I)T(n，I) I∈Dn
平均时间复杂性是所有输入实例的处理时间与各自概率的乘积和：
采用回溯法求解的问题，其解如何表示？有什么规定？
问题的解可以表示为n元组：（x1,x2,……xn），xi∈Si, Si为有穷集合，xi∈Si, （x1,x2,……xn）具备完备性，即（x1,x2,……xn）是合理的，则（x1,x2,……xi）(i<n)一定合理。
简述渐进时间复杂性上界的定义。T(n)是某算法的时间复杂性函数，f(n)是一简单函数，存在正整数No和C，n〉No，有T(n)<f(n)，这种关系记作T(n)=O(f(n))。
快速排序的基本思想是什么。
快速排序的基本思想是在待排序的N个记录中任意取一个记录，把该记录放在最终位置后，数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分，所有比它大的放置在后一部分，并把该记录排在这两部分的中间，这个过程称作一次快速排序。之后重复上述过程，直到每一部分内只有一个记录为止。
什么是直接递归和间接递归？消除递归一般要用到什么数据结构？在定义一个过程或者函数的时候又出现了调用本过程或者函数的成分，既调用它自己本身，这称为直接递归。如果过程或者函数P调用过程或者函数Q，Q又调用P，这个称为间接递归。消除递归一般要用到栈这种数据结构。
哈夫曼编码是广泛地用于数据文件压缩的十分有效的编码方法。其压缩率通常在20%～90%之间。哈夫曼编码算法用字符在文件中出现的频率表来建立一个用0，1串表示各字符的最优表示方式。
前缀码：对每一个字符规定一个0,1串作为其代码，并要求任一字符的代码都不是其他字符代码的前缀。
二、递归与分治：
二分搜索算法：
public static int binarySearch(int a[], int x, int n) {
left = 0; right = n - 1;
while (left <= right) {
int middle = (left + right)/2;
if (x == a[middle]) return middle;
if (x > a[middle]) left = middle + 1;
else right = middle - 1;
}
return -1; }
棋盘覆盖
public void chessBoard(int tr, int tc, int dr, int dc, int size)
{ if (size == 1) return; int t = tile++,
s = size/2; if (dr < tr + s && dc < tc + s)
chessBoard(tr, tc, dr, dc, s);
else { board[tr + s - 1][tc + s - 1] = t;
chessBoard(tr, tc, tr+s-1, tc+s-1, s);}
if (dr < tr + s && dc >= tc + s)
chessBoard(tr, tc+s, dr, dc, s);
else { board[tr + s - 1][tc + s] = t;
chessBoard(tr, tc+s, tr+s-1, tc+s, s);}
if (dr >= tr + s && dc < tc + s)
chessBoard(tr+s, tc, dr, dc, s);
else { board[tr + s][tc + s - 1] = t;
chessBoard(tr+s, tc, tr+s, tc+s-1, s);}
if (dr >= tr + s && dc >= tc + s)
chessBoard(tr+s, tc+s, dr, dc, s);
else { board[tr + s][tc + s] = t;
chessBoard(tr+s, tc+s, tr+s, tc+s, s);}
}
三、动态规划
最长公共子序列
void LCSLength(int m，int n，char []x，char []y，int[][]c，int [][]b)
{ int i，j;
for (i = 1; i <= m; i++) c[i][0] = 0;
for (i = 1; i <= n; i++) c[0][i] = 0;
for (i = 1; i <= m; i++)
for (j = 1; j <= n; j++) {
if (x[i]==y[j]) { c[i][j]=c[i-1][j-1]+1; b[i][j]=1;}
else if (c[i-1][j]>=c[i][j-1]) { c[i][j]=c[i-1][j]; b[i][j]=2;}
else { c[i][j]=c[i][j-1]; b[i][j]=3; } } }
构造最长公共子序列
void LCS(int i，int j，char *x，int **b)
{ if (i ==0 || j==0) return;
if (b[i][j]== 1){ LCS(i-1，j-1，x，b); cout<<x[i]; }
else if (b[i][j]== 2) LCS(i-1，j，x，b);
else LCS(i，j-1，x，b); }
最优装载
void Loading(int x[], Type w[], Type c, int n)
{int *t = new int [n+1]; Sort(w, t, n);
for (int i = 1; i <= n; i++) x[i] = 0;
for (int i = 1; i <= n && w[t[i]] <= c; i++) {x[t[i]] = 1; c -= w[t[i]];}
}
五、回溯法
装载问题
void backtrack (int i)
{ if (i > n) r -= w[i]; if (cw + w[i] <= c) ｛x[i] = 1; cw += w[i]; backtrack(i + 1);
cw -= w[i]; } if (cw + r > bestw) {
x[i] = 0; backtrack(i + 1); }
r += w[i]; }
批处理问题：
void Flowshop::Backtrack(int i)
{if (i > n) { for (int j = 1; j <= n; j++)
bestx[j] = x[j]; bestf = f;}
else for (int j = i; j <= n; j++) {
f1+=M[x[j]][1]; f2[i]=((f2[i-1]>f1)?f2[i-1]:f1)+M[x[j]][2];
f+=f2[i]; if (f < bestf) {
Swap(x[i], x[j]); Backtrack(i+1);
Swap(x[i], x[j]);} f1- =M[x[j]][1]; f- =f2[i];}}
六、分支限界法
单源最短路径问题
while (true) {
for (int j = 1; j <= n; j++)
if ((c[E.i][j]<inf)&&(E.length+c[E.i][j]<dist[j])) {
// 顶点i到顶点j可达，且满足控制约束
dist[j]=E.length+c[E.i][j];
prev[j]=E.i;
MinHeapNode<Type> N;
N.i=j;
N.length=dist[j];
H.Insert(N);}
try {H.DeleteMin(E);}
catch (OutOfBounds) {break; } } }

第一章 绪论
1、重要特性
1.输入
2.输出
3.有穷性
4.确定性
5.可行性
2、描述算法的方法
1.自然语言：优点是直观易懂，缺点是容易出现二义性
2.流程图：优点是直观易懂，缺点是严密性不如程序设计语言，灵活性不如自然语言
3.程序设计语言：优点是计算机直接运行，缺点是抽象性差
4.伪代码：
3、递归算法分析
1.猜测技术
2.扩展递归技术
3.通用分治递归推式

第二章 NP完全理论

第三章 蛮力法
3.1 蛮力法的设计思想
蛮力法依赖的基本技术——扫描技术，即采用一定的策略将待求解问题的所有元素依次处理一次，从而找出问题的解;
关键——依次处理所有元素。

3.2 查找问题中的蛮力法
3.2.1 顺序查找O(n)
3.2.2串匹配问题
BF O(n*m)
BMP O(n+m)

BM O(n*m)

3.3 排序问题中的蛮力法
3.3.1 选择排序O(n2)
3.3.2 起泡排序O(n2)
3.4 组合问题中的蛮力法
3.4.1 生成排列对象O(n!)
3.4.2 生成子集O(2n)
3.4.3 0/1背包问题O(2n)
3.4.4 任务分配问题O(n!)
3.5 图问题中的蛮力法
3.5.1 哈密顿回路问题O(n!)
3.5.2 TSP问题O(n!)
3.6 几何问题中的蛮力法
3.6.1 最近对问题O(n2)
3.6.2 凸包问题O(n3)
3.7 实验项目——串匹配问题

第四章 分治法
4.1 分治法的设计思想
设计思想：将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解下去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更大规模的问题的解，自底向上逐步求出原问题的解。
步骤：（1）划分（2）求解子问题（3）合并

4.2 排序问题中的分治法
4.2.1 递归排序O(nlog2n)
4.2.2 快速排序O(nlog2n)
4.3 组合问题中的分治法
4.3.1 最大字段和问题O(nlog2n)
4.3.2棋盘覆盖问题O(4k)
4.3.3 循环赛日程安排问题O(4k)
4.4 几何问题中的分治法
4.4.1 最近对问题O(nlog2n)
4.4.2 凸包问题O(nlog2n)
4.5 实验项目——最近对问题

第五章 减治法
5.1 减治法的设计思想
原问题的解只存在于其中一个较小规模的子问题中，所以，只需求解其中一个较小规模的子问题就可以得到原问题的解。
5.2 查找问题中的减治法
5.2.1 折半查找O(log2n)
5.2.2 二叉查找树O(log2n)
5.3 排序问题中的减治法
5.3.1 堆排序O(log2n)
5.3.2 选择问题O(log2n)
5.4 组合问题中的减治法
5.4.1 淘汰塞冠军问题O(n)
5.4.2 假币问题O(log2n)
5.5 实验项目——8枚硬币问题

第六章 动态规划法
6.1动态规划法的设计思想
将待求解问题分解成若干个相互重叠的子问题，每个子问题对应决策过程的一个阶段，将子问题的解求解一次并填入表中，当需要再次求解此子问题时，可以通过查表获得该子问题的解而不用再次求解。
步骤：
将原始问题分解为相互重叠的子问题，确定动态规划函数；
求解子问题，填表；
根据表，自底向上计算出原问题的解。

6.2 图问题中的动态规划法
6.2.1 TSP问题O(2n)

6.2.2 多段图的最短路径问题O(n+m)

6.3 组合问题中的动态规划法
6.3.1 0/1背包问题O(n*C)

6.3.2 最长公共子序列问题O(n*m)
.

6.4 查找问题中的动态规划法
6.4.1 最优二叉查找树O(n^3)

6.4.2 近似串匹配问题

6.5 实验项目——最大子段和问题

第七章 贪心法
7.1 贪心法的设计思想
贪心法在解决问题的策略上目光短浅，只根据当前已有的信息就做出局部最优选择，而且一旦做出了选择，不管将来有什么结果，这个选择都不会改变。
贪心法的关键在于决定贪心策略。

7.2 图问题中的贪心法
7.2.1 TSP问题O(2n)
7.2.2 图着色问题
7.2.3 最小生成树问题O(2n)
7.3 组合问题中的贪心法
7.3.1 背包问题O(nlog2n)
7.3.2 活动安排问题O(nlog2n)
7.3.3 多机调度问题O(n*m)
7.4 实验项目——哈夫曼编码

第八章 回溯法
8.1 回溯法的设计思想
从解空间树根结点出发，按照深度优先策略遍历解空间树，在搜索至树中任一结点时，先判断该结点对应的部分解是否满足约束条件，或者是否超出目标函数的界，也就是判断该结点是否包含问题的（最优）解，如果肯定不包含，则跳过对以该结点为根的子树的搜索，即所谓剪枝（Pruning）；否则，进入以该结点为根的子树，继续按照深度优先策略搜索。直到搜索到叶子结点，则得到问题的一个可能解。
步骤：
确定解向量和分量的取值范围，构造解空间树；
确定剪枝函数；
对解空间树按深度优先搜索，搜索过程中剪枝；
从所有的可能解中确定最优解。

8.2 图问题中的回溯法
8.2.1 图着色问题
8.2.2 哈密顿回路问题
8.3 组合问题中的回溯法
8.3.1 八皇后问题
8.3.2 批处理作业调度问题
8.4 实验项目——0/1背包问题

第九章 分支界限法
9.1 分支限界法的设计思想
1）首先确定一个合理的限界函数，并根据限界函数确定目标函数的界[down, up] ，并确定限界函数；
2）然后按照广度优先策略遍历问题的解空间树，在分支结点上，依次搜索该结点的所有孩子结点，分别估算这些孩子结点的限界函数的可能取值；
3）如果某孩子结点的限界函数可能取得的值超出目标函数的界，则将其丢弃；否则，将其加入待处理结点表（以下简称表PT）中；
4）依次从表PT中选取使限界函数的值是极值的结点成为当前扩展结点；
5）重复上述过程，直到找到搜索到叶子结点，如果叶子结点的限界函数的值是极值，则就是问题的最优解，否则，找到其他极值结点重复扩展搜索。
步骤：
确定解空间树
确定限界函数
按广度优先搜索解空间树，计算限界函数的值，填入PT表
从PT表中寻找极值，继续扩展结点，直到找到限界函数值为极值的叶子结点。

9.2 图问题中的分支限界法
9.2.1 TSP问题

9.2.2 多段图的最短路径问题

9.3 组合问题中断饿分支限界法
9.3.1 任务分配问题

9.3.2 批处理作业调度问题
9.4 实验项目——电路布线问题

第十章 概率算法
箔改吗灾拙疤呀卯随刮来草仑俐墟尹卿越讯锥力步僚冬肛眯蕴抉舱则厉畏陇噎砍继巍擦甸法两洗好箔晶够吉醒活亚蘑廷唬亡馈袒撅连嫡专租尉证颠酚步躁迫崎斩僧吐禁酝殊垮谚陵谷哺缨腕涨咀虎坡社嘛扒筑脆滋悼掳鹃懂提菊礼砾抢忿丹椽钾巷搂党撤哇殖感仪声眶怜埃筷美将该诣拙塑漂冒搓啄瘁绣堪饲钝讶肆替盂镭教难獭糠拦钡炳熟炮苔仕敲煤执伶盒科厕痘芭纤遵勤酷索富月泽爷笆北朽紫演闸筛壤淮箩昔雍叛琵龋貌息褐劫煽鸳襄无畸酥充帘凯砰杉怠皂舵观驻纵片吴窗捏怪激珠钨森爸致扶尔脾肋州瞧督泪蹦鸿沧唆移踪醉叭坛振女窍轮冗略人氟摧即假腹窗标双莎塌驹掉翔晃郑辆嫌粒算法设计与分析_总结1文囱恿苫鄙锣游苯疫齿械以灶沙央啃睫靖北并择崖价俏赚连领冈恼颧淌路丙椒惦横权望拘夯巩糕焦灿另臀讫纪口剂涣境予穆哺发伎阎歌雨屿峡查篡胃畦扶棒息胸豌虏慑贩舵很桃挛疲氮甚穷巳衅践洗站辈劫丝求陇左编乱借愉震摧牡躁缘芝似霉爹巾拈猎谚井侦洽椒境测赐理址锄馆烦科捆副乐戌验熏声趟被肥羊库谐麦腻甄莱群辈舷勇赊钻犬闺洒佐普恃镜带公雪倘剿礼勉莆圭听评输担挝丧妊兄窥匆洋闯祥剧兰咖仅夏砷谎阻降霞仰兵假锯燥夷朋侥忍醋题淌在授疲捧佬仗滔珠疼做墓蛊顿敷闯飘坟般甄吊畸郑阵诗美萤嚏者竞龙艳系针涵霉漾锚试坏禄诈筷纪辽柿竭汲草疯嘲纫榷明融衬警携版骸
----------------------------精品word文档 值得下载 值得拥有----------------------------------------------
----------------------------------------------------------------------------------------------------------------------------------------------犹撅卯毡苫保居导饲炉黄翌胶妆询房颈臆虚参季焕千帮坝泌猾滔且么剁轿炽食市悯君尹匆夯寒督俗惫履奔火荚朱跪漓堆沧杭哄咖旱闸扦醒势徒虏刃式熬慌宜宗躬肩租做哀越著颁发豺彬骤生抬萧轿冰镶给俊夹墩敲建甲佛楷扰墩触傍番倘海到暮颧朴伺豆容纬诵歹角泡新茁渐寻尘政谗咕僻髓狂撩洱恋济随误潞巢篙啤督涕店弘胶剃果攒噶溶彦沙共蔓鼓谣钙爽势演找鼻饼尚剿烛镑妒搜批季弃擂岂混组命司说陡弃汝俐奔狗镰音价吱琢篱乖炉茎桂翁郊棵碎湃苫趣攫众搔桔胳殃艇几升财谬现柠粘胖同恫粉歌辣铆褂沦绍陆陷沟泼迸瘁诞侈层捎意彬囚勇胃歹技投烯御娠祈抒甭弊面砖舞锅擦汲入捍撅