蒙特卡罗(Monte Carlo)算法的基本思想:
设p是一个实数，且1/2<p<1。如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且称p-1/2是该算法的优势。
如果对于同一实例，蒙特卡罗算法不会给出2个不同的正确解答，则称该蒙特卡罗算法是一致的。
线性规划基本定理：如果线性规划问题有最优解，则必有一基本可行最优解。
单纯形算法的特点是：
（1）只对约束条件的若干组合进行测试，测试的每一步都使目标函数的值增加；
（2）一般经过不大于m或n次迭代就可求得最优解。
单纯形算法的基本思想就是从一个基本可行解出发，进行一系列的基本可行解的变换。每次变换将一个非基本变量与一个基本变量互调位置，且保持当前的线性规划问题是一个与原问题完全等价的标准线性规划问题。
图灵机由以下几部分组成：一条无限长的带（有无穷个格子）、一个读写头、一个有限状态控制器以及一个程序。
NPC形式化定义：
定义1：语言L是NP完全的当且仅当（1） L【NP；（2）对于所有L’【NP有L’ ～pL。
如果有一个语言L满足上述性质(2),但不一定满足性质（1），则称该语言是NP难的。
所有NP完全语言构成的语言类称为NP完全语言类，就是NPC。
定理1 设L是NP完全的，则（1）L?P当且仅当P＝NP；（2）若 L ?p L1，且 L1? NP，则L1是NP完全的。
团问题:
任给图G和整数k．试判定图G中是否存在具有k个顶点的团？
1)团问题?NP。显然，验证G的一个子图是否成团只需多项式时间即可。
2)SAT?团问题。
任给表达式f．构造一个相应的图G如下：
①图G的每个顶点对应于f中的每个文字(多次出现的重复计算)。
②若G中两个顶点其原对应的文字不相互补且不出现于同一于句中，则将其连线。
设f有n个子句，则f可满足当且仅当f对应的图G中有n个顶点的团。
这是因为：
(a)若f可满足，即有某种赋值使得f取值为真，它等价于使得每个ci中都至少有一个文字为真，这n个文字(每个ci(1＜i<n)中一个)对应的图G中的n个顶点就构成一个团。
(b)若图G中有一n个顶点的团，则取给出使得这n个顶点对应的文字都为真的赋值，则f的取值为真(这由图G的定义易证)。
显见，上述构造图G的方法是多项式界的，因此SAT 团问题。
由(a)、(b)有，团问题?NPC。证毕。
单源最短路径问题:
void shortestpaths(v)
{
MinHeap H[1000];
//定义最小堆
MinHeapNode<type> E;
E.i=v;
E.length=0;
Dist[v]=0;
//搜索问题界空间
while(true)
{ for(j=1;j<=n;j++)
if((c[E.i][j]<inf)&&
(E.length+c[E.i][j]<dist[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)数值随机化算法: ?求解数值问题,得到近似解
(2)Monte Carlo算法:? 问题准确性,但却无法确定解正确性
(3)Las Vegas算法:?获得正确解,但存在找不到解的可能性
(4)Sherwood算法:?保证能获得正确解
旅行售货员问题:(优先队列式分支限界法)
Type Travding (int v[])
{ MinHeapNode H(1000)；
Type Minout[N+1]；
//计算 Minout[i]=顶点 i的最小出边费用
Type Minsurn=0；//最小出边费用和
for（i=1;i＜＝n；i++）{
Min=NoEdge；
for（ j=1；j＜＝n；j++）
if（a[i][j]!=NoEdge＆＆(a[i][j]<Min || Min==NoEdge) Min=a[i][j]；
if（Min==NoEdge） return(NoEdge)； //无回路
MinOut[i]= Min；
MinSum+=Min；
}
//初始化
MinHeapNode E；
for（i= 0；i＜ n；i++）
E.x［i］= i+ 1；
E.s=0；
E.cc=0；
E.rcost=MinSum；
Bestc=NoEdge；
while（E.s＜n-1) //非叶结点
if（E.s<n-1）{ //当前扩展结点是叶结点的父结点
if（a[E.x[n-2][E.x[n-1]]!=NoEdge ＆＆a[E.x[n-2][1]!=NoEdge&&（E.cc+
a[E.x[n-2]][E.x[n-1]]+a[E.x[n-1]][1]<
bestc || bestc==NoEdge）{
//费用更小的回路
bestc=Ecc+a[E.x[n-2]][E.x[n-1]]
+a[E.x[n-1]][1]；
E.c＝bestc；
E.lcost=bestc；
E.s++；
Insert（H,E）；}
else delete(E.x) ；} //舍弃扩展结点
else { //产生当前扩展结点的儿子结点
for（ i＝E.s+1；i＜n；i++＝
if（a[E.x[E.s]][E.x[i]]!=NoEdge）
{ //可行儿子结点
Type cc＝E.cc+a[E.x[E.s]][E.x[i]]；
Type rcost=E.rcost-MinOut[E.x[E.s]]；
Type b=cc+rcost； //下界
if（b＜ bestc||bestc== NoEdge )
{ //子树可能含最优解
for（j= 0； j＜ n； j++)
N.x[j]=E.x[j]；
N.x[E.s+1]=E.x[i]；
N.x[i]=E.x[E.s+1]；
N.cc=cc；
N.s= E.s+1；
N.lcost=b；
N.rcost＝rcost；
Insert（H,N）；
}
}
delete(H,E.x)；
}//完成结点扩展
DeleteMin(H,E)；} //取下一扩展结点
if (堆已空) break； //堆已空
}
if（bestc==NoEdge）return( NoEdge)；
//无回路
//将最优解复制到v[l：n]
for（i=0；i＜n；i++)
v[i+ 1]=E.x[i]；
while (true){ //释放最小堆中所有结点
delete(H, E. x)；
DeleteMin(H,E)；} //取下一扩展结点
if (堆已空) break； //堆已空
}
return(bestc)；
}
回溯算法解批处理作业调度(解空间：排列树):
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];
}
}
所以在最坏的情况下，整个算法的计算时间复杂性为O(n!)
回溯算法解0-1背包问题(解空间：子集树):
template<class Typew, class Typep>
Typep Knap<Typew, Typep>::Bound(int i)
{// 计算上界
Typew cleft = c - cw; // 剩余容量
Typep b = cp;
// 以物品单位重量价值递减序装入物品
while (i <= n && w[i] <= cleft) {
cleft -= w[i];
b += p[i];
i++;
}
// 装满背包
if (i <= n) b += p[i]/w[i] * cleft;
return b;
}
void backtrack(i)
{ if( i>n )
{ bestp=cp;
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 )
backtrack(i+1); //x[i]=0
}
由于上界函数Bound()需要O(n)的时间，在最坏的情况下有O(2n)个右儿子结点需要计算上界函数，所以0-1背包问题的回溯算法Backtrack()所需要的时间是O(n2n)。
回溯算法解图的m着色问题:
void Color::Backtrack(int t)
{
if (t>n) {
sum++;
for (int i=1; i<=n; i++)
cout << x[i] << ' ';
cout << endl;
}
else
for (int i=1;i<=m;i++) {
x[t]=i;
if (Ok(t)) Backtrack(t+1);
}
}
bool Color::Ok(int k)
{// 检查颜色可用性
for (int j=1;j<=n;j++)
if ((a[k][j]==1)&&(x[j]==x[k])) return false;
return true;
}
回溯法总的时间耗费是O(m^n *n)
回溯算法解最大团问题（解空间：子集树）：
void Clique::Backtrack(int i)
{// 计算最大团
if (i > n) {// 到达叶结点
for (int j = 1; j <= n; j++) bestx[j] = x[j];
bestn = cn; return;}
// 检查顶点 i 与当前团的连接
int OK = 1;
for (int j = 1; j < i; 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 - i > bestn) {// 进入右子树 x[i] = 0;
Backtrack(i+1);}
}
解最大团问题的回溯算法Backtrack所需的计算时间为O(n2n)。
回溯法的基本思想是：不断用修改过的判定函数Pi只(x1,x2,…,xi)(亦称为限界函数)去测试正在构造中的n元组的部分向量(x1,x2,…,xn)．看其是否可能导致最优解。如果判定(x1，x2，…，xn)不可能导致最优解，那么就不再测试可能要测试的mi+1mi+2...mn个向量。
解符号三角形问题的回溯算法Backtrack所需的计算时间为O(n2n)。
贪心法解最优装载问题：
template<class Type>
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]];}
}
算法所需的计算时间为 O(nlogn)
算法是指解决问题的一种方法或一个过程。算法是若干指令的有穷序列，满足性质：(1)输入 (2)输出 (3)确定性 (4)有限性：
问题的计算时间下界为?(f(n))，则计算时间复杂性为O(f(n))的算法是最优算法。
1. 什么是动态规划法：将问题分解成多级或许多子问题，然后顺序求解子问题，前一个子问题的解为后一个子问题的求解提供有用的信息。
2. 什么是贪心法：从问题某一初始或推测值出发，一步步的攀登给定目标，尽可能快的去逼近更好的解，当达到某一步不能继续时终止。
3. 什么是分支定界法：对有约束条件的最优化问题所有可行解定向、适当地进行搜索。将可行解空间不断地划分为越来越小的子集（分支），并为每一个子集的解计算一个上界和下界（定界）。
5、什么是NP类问题：
NP={L|L是一个能在多项式时间内被一台NDTM图灵机所接受的语言}，其中NDTM是非确定性图灵机。或者可说：NP是所有可在多项式时间内用不确定的算法求解的判定问题的集合。对于NP类，相当于要求验证模块在多项式时间内完成对应NDTM，有非确定性算法。
1. 算法的分类：1）(数值算法 ) 2） 非数值算法
2. 算法的描述：1）自然语言描述 2）(流程图描述) 3）程序语言描述
3. 算法的分析标准：1） 时空观念 2 ）(发展观念) 3） 设计观点 4） 交流的观点
设计动态规划算法的步骤。
(1)找出最优解的性质，并刻划其结构特征。
(2)递归地定义最优值。
(3)以自底向上的方式计算出最优值。
(4)根据计算最优值时得到的信息，构造最优解。
动态规划法求矩阵连乘问题：
void MatrixChain(int *p，int n，int **m，int **s)
{for (int i = 1; i <= n; i++) m[i][i] = 0;
for (int r = 2; r <= n; r++)
for (int i = 1; i <= n - r+1; i++) {
int j=i+r-1;
m[i][j] = m[i+1][j]+ p[i-1]*p[i]*p[j];
s[i][j] = i;
for (int k = i+1; k < j; k++) {
int t = m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j];
if (t < m[i][j]) { m[i][j] = t; s[i][j] = k;}
}
}
}
因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。
1.简述算法的五个重要的特征。：①有穷性： 一个算法必须保证执行有限步之后结束；②确切性： 算法的每一步骤必须有确切的定义； ③输入：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定义了初始条件；④输出：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的；⑤可行性： 算法原则上能够精确地运行，而且人们用笔和纸做有限次运算后即可完成。备注： 算法可以没有输入。因为有些算法中包含了输入，如随机产生输入。
2.简答贪心算法的基本元素：①贪心选择性质：所谓贪心选择性质指所求问题的整体最优解可以通过一系列局部最优的选择达到。②最优子结构性质：当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构。
3.简述动态规划算法的基本思想和基本步骤以及动态规划问题的特征。
动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。
按以下几个步骤进行：
①分析最优解的性质，并刻划其结构特征。
②递归地定义最优值。
③以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。
④根据计算最优值时得到的信息，构造一个最优解。
动态规划问题的特征：动态规划算法的有效性依赖于问题本身所具有的两个重要性质：最优子结构性质和子问题重叠性质。
1、最优子结构：当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。
2、重叠子问题：在用递归算法自顶向下解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，在以后尽可能多地利用这些子问题的解。
4.简述回溯算法的基本思想及解题步骤。
回溯法的基本思想：确定了解空间的组织结构后，回溯法就从开始结点（根结点）出发，以深度优先的方式搜索整个解空间。这个开始结点就成为一个活结点，同时也成为当前的扩展结点。在当前的扩展结点处，搜索向纵深方向移至一个新结点。这个新结点就成为一个新的活结点，并成为当前扩展结点。如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。换句话说，这个结点不再是一个活结点。此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。回溯法即以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已没有活结点时为止。（9分）
运用回溯法解题通常包含以下三个步骤：
（1）针对所给问题，定义问题的解空间；（2分）
（2）确定易于搜索的解空间结构；（2分）
（3）以深度优先的方式搜索解空间，并且在搜索过程中用剪枝函数避免无效搜索。
5.简述分治算法的基本思想及基本步骤。
分治法的基本思想：对于一个输入规模为 的问题，若该问题容易的解决，则直接解决，否则将其分解为 个规模较小的子问题，这些子问题相互独立且与原问题形式相同，递归求解这些子问题，然后将各个子问题的解合并，得到原问题的解。（9分）
分治法在每一层递归上由以下三个步骤组成：
①划分：将原问题分解为若干规模较小、相互独立、与原问题形式相同的子问题；（2分）
②解决：若子问题规模较小，则直接解决；否则递归求解各个子问题。（2分）
③合并：将各个子问题的解合并为原问题的解。（2分）
6.分支限界法的基本思想：
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。问题的解空间树是表示问题解空间的一棵有序树，常见的有排列树。在搜索问题的解空间树时，分支限界法与回溯法对当前扩展结点所使用的扩展方式不同。在分支限界法中，每一个活结点只有一次机会成为扩展结点。活结点一旦成为扩展结点，就一次性产生其所有儿子结点。在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被子加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。
7.贪心算法的基本思想如下：从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止，得到问题的一个解。
贪心算法存在问题：1. 不能保证求得的最后解是最佳的；2. 不能用来求最大或最小解问题；3. 只能求满足某些约束条件的可行解的范围。
8.动态规划与分治法的异同：
相同点：动态规划法与分治法类似，它们都是将问题划分为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。
不同点：而分治法中的各个子问题是独立的 (即不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不同的是，如果各子问题是不是相互独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。
9.分支限界法与回溯法的异同：
分支限界法类似于回溯法，也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使用某一目标函数值达到极大或极小的解，即在某种意义下的最优解。因此， 回溯法以深度优先的方式搜索解空间树T，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树T。
10.证明装载问题具有贪心选择性质.
证明:设集装箱已依其重量从小到大排序, (x1,x2, …,xn)是最优装载问题的一个最优解.又设1.当k=1时, (x1,x2, …,xn)是一个满足贪心选择性质的最优解.
2.当k>1时,取y1=1;yk=0;yi=xi,1<I≤N,I≠K
因此,(y1,y2, …,yn)是所给最优装载问题的一个可行解
另一方面,由
(y1,y2, …,yn)是一个满足贪心选择性质的最优解
所以,最优装载问题具有贪心选择性质
Hanoi塔问题:
void hanoi(int n, int a, int b, int c)
{
if (n > 0)
{
hanoi(n-1, a, c, b);
move(a,b);
hanoi(n-1, c, b, a);
}
}
6.3 递归算法到非递归算法的转换
递归算法有两个基本特性：一是递归算法是一种分而治之的、把复杂问题分解为简单问题的求解问题方法,对求解某些复杂问题,递归算法分析问题的方法是十分有效的；二是递归算法的时间/空间效率通常比较差。
因此,对求解某些问题时,我们希望用递归算法分析问题,用非递归算法具体求解问题。这就需要把递归算法转换为非递归算法。
把递归算法转化为非递归算法有如下三种基本方法：
(1)通过分析，跳过分解过程，直接用循环结构的算法实现求值过程。
(2)自己用栈模拟系统的运行时栈,通过分析只保存必须保存的信息,从而用非递归算法替代递归算法。
(3)利用栈保存参数,由于栈的后进先出特性吻合递归算法的执行过程,因而可以用非递归算法替代递归算法。
