证明最优算法

㈠ [算法] 贪心算法证明思路

动态规划和贪心算法都需要问题具有最优子结构，但不同的是贪心 自顶向下 ，先做选择再求解一个结果子问题，而动态规划自底向上求解子问题，需要先求出子问题的最优解再做选择。这是因为，动态规划最优解有两个子问题时，求解子问题 时有j-i-1种选择，但贪心选择特征能够使 其中一个子问题必定为空 ，这种子问题和选择数目的减少使得子问题能够自顶向下被解决。

a) 定义子问题空间，做出一个选择从而产生一个或多个子问题。子问题空间的定义结合需要求解的目标和选择后子问题的描述刻画来考虑。
b) 利用“剪切-粘贴”证明作为最优解的组成部分的每个子问题的解也是它本身的最优解。如果子问题的解不是最优解，将其替换为对应的最优解从而一定能得到原问题一个更优的解，这与最初的解是原问题的最优解的前提假设矛盾，因此最优子结构得证。

贪心的本质是局部最优解能产生全局最优解，即产生两个子问题 和 时，可以直接解决子问题 （在子问题 中，使用贪心策略选择a作为局部最优解）然后对子问题 进行分解，最终可以合并为全局最优解。
因此，要证明贪心选择性质只需要证明 存在一个最优解是通过当前贪心选择策略得到的 ，反过来，即证明**通过非贪心策略得到的原问题的最优解中也一定包含局部最优解a。

定义通过非贪心策略的选择可以得到的一个最优解A，将最优解中的元素和当前贪心策略会选择的元素逐个交换后得到的解A'并不比
A差（假设贪心策略会选择的元素在当前最优解中未被选择，通过“剪切-粘贴”证明得到的仍是最优解），可以证明存在原问题的最优解可以通过贪心选择得到。

㈡ 如何证明演化算法得到的解是近似最优解

1,用你的演化算法作一个benchmark，如果达到近似最优解，说明你的演化算法比较好。
2，算法没有缺点时，进行足够的时间计算，可以作为近似最优解。
3，松弛约束后，根据差可以基本判断是否最优解

㈢ 举出在信息学中已被证明的“最优算法”

·····你的内容和题目是否不和谐？
第一个比较排序算法的时间最少值可以成立在各种排序算法上的，比如桶排堆排或者快排，对于快排这种随机排序由于处理的数据不同或是随即函数的原因每次排序时间是不确定的。

所以我觉得第一句和 最优算法 没有明确的联系，我是学信息的。

关于算法，高中数学不是说了算法不是唯一的吗？至于最优打上引号还是有一些的我参考算法导论给你一些 关于搜索路径的简单地说就是找迷宫出口路径的Johnson顶点间的最短路径算法。
图算法中最小生成树的Lruskal和Prim算法

对于你的核心问题还是抱有疑问，一个问题有很多种算法可以解决，而一个算法能解决一类问题。你说你要从10个数中找出最小的，一定是从第一个找到最后一个，确实这是时间最优，但并不是空间最优，于是你的问题所谓的最优算法还是很难肯定一个算法是否是最优的，你在比如说用来测试CPU浮点运算速度的求pi值的算法有很多据我所知有3种，哪一种是最优的我无法确定。

所以若不是对某一特定的问题，而是处理某一类问题的时候，是要看算法的平均性能的。
你所谓的最优算法，也许是存在的，但是我无法找出答案，很抱歉 如果你看到我的解答，情做你该做的事。

㈣ OPT页面置换算法最优性证明。

1常见的置换算法

1．最佳置换算法（OPT）（理想置换算法）：所选择的被淘汰页面将是以后永不使用的，或者是在最长时间内不再被访问的页面，这样可以保证获得最低的缺页率。2．先进先出置换算法（FIFO）：优先淘汰最早进入的页面，亦即在内存中驻留时间最久的页面。3．最近最久未使用（LRU）算法：选择最近最长时间未访问过的页面予以淘汰。4．Clock置换算法（LRU算法的近似实现）：给每一帧关联一个附加位，称为使用位。5．最少使用（LFU）置换算法6．工作集算法7 . 工作集时钟算法8. 老化算法（非常类似LRU的有效算法）9. NRU(最近未使用）算法10. 第二次机会算法2操作系统页面置换算法代码#include <stdio.h>^[1]#include <stdlib.h>#include <unistd.h> #define TRUE 1#define FALSE 0#define INVALID -1#define NUL 0#define total_instruction 320 /*指令流长*/#define total_vp 32 /*虚页长*/#define clear_period 50 /*清零周期*/typedef struct{ /*页面结构*/int pn,pfn,counter,time;}pl_type;pl_type pl[total_vp]; /*页面结构数组*/struct pfc_struct{ /*页面控制结构*/int pn,pfn;struct pfc_struct *next;};typedef struct pfc_struct pfc_type;pfc_type pfc[total_vp],*freepf_head,*busypf_head,*busypf_tail;int diseffect,a[total_instruction];int page[total_instruction], offset[total_instruction];void initialize(int);void FIFO(int);void LRU(int);void NUR(int);int main(){int S,i;srand((int)getpid());S=(int)rand()%390;for(i=0;i<total_instruction;i+=1) /*产生指令队列*/{a[i]=S; /*任选一指令访问点*/a[i+1]=a[i]+1; /*顺序执行一条指令*/a[i+2]=(int)rand()%390; /*执行前地址指令m’*/a[i+3]=a[i+2]+1; /*执行后地址指令*/S=(int)rand()%390;}for(i=0;i<total_instruction;i++) /*将指令序列变换成页地址流*/{page[i]=a[i]/10;offset[i]=a[i]%10;}for(i=4;i<=32;i++) /*用户内存工作区从4个页面到32个页面*/{printf("%2d page frames",i);FIFO(i);LRU(i);NUR(i);printf(" ");}return 0;}void FIFO(int total_pf) /*FIFO(First in First out)ALGORITHM*//*用户进程的内存页面数*/{int i;pfc_type *p, *t;initialize(total_pf); /*初始化相关页面控制用数据结构*/busypf_head=busypf_tail=NUL; /*忙页面队列头，对列尾链接*/for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INVALID) /*页面失效*/{diseffect+=1; /*失效次数*/if(freepf_head==NUL) /*无空闲页面*/{p=busypf_head->next;pl[busypf_head->pn].pfn=INVALID; /*释放忙页面队列中的第一个页面*/freepf_head=busypf_head;freepf_head->next=NUL;busypf_head=p;}p=freepf_head->next; /*按方式调新页面入内存页面*/freepf_head->next=NUL;freepf_head->pn=page[i];pl[page[i]].pfn=freepf_head->pfn;if(busypf_tail==NUL)busypf_head=busypf_tail=freepf_head;else{busypf_tail->next=freepf_head;busypf_tail=freepf_head;}freepf_head=p;}}printf("FIFO:%6.4F",1-(float)diseffect/320);}void LRU(int total_pf){int min,minj,i,j,present_time;initialize(total_pf);present_time=0;for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INVALID) /*页面失效*/{diseffect++;if(freepf_head==NUL) /*无空闲页面*/{min=32767;for(j=0;j<total_vp;j++)if(min>pl[j].time&&pl[j].pfn!=INVALID){min=pl[j].time;minj=j;}freepf_head=&pfc[pl[minj].pfn];pl[minj].pfn=INVALID;pl[minj].time=-1;freepf_head->next=NUL;}pl[page[i]].pfn=freepf_head->pfn;pl[page[i]].time=present_time;freepf_head=freepf_head->next;}elsepl[page[i]].time=present_time;present_time++;}printf("LRU:%6.4f",1-(float)diseffect/320);}void NUR(int total_pf){int i,j,dp,cont_flag,old_dp;pfc_type *t;initialize(total_pf);dp=0;for(i=0;i<total_instruction;i++){if(pl[page[i]].pfn==INVALID) /*页面失效*/{diseffect++;if(freepf_head==NUL) /*无空闲页面*/{cont_flag=TRUE;old_dp=dp;while(cont_flag)if(pl[dp].counter==0&&pl[dp].pfn!=INVALID)cont_flag=FALSE;else{dp++;if(dp==total_vp)dp=0;if(dp==old_dp)for(j=0;j<total_vp;j++)pl[j].counter=0;}freepf_head=&pfc[pl[dp].pfn];pl[dp].pfn=INVALID;freepf_head->next=NUL;}pl[page[i]].pfn=freepf_head->pfn;freepf_head=freepf_head->next;}elsepl[page[i]].counter=1;if(i%clear_period==0)for(j=0;j<total_vp;j++)pl[j].counter=0;}printf("NUR:%6.4f",1-(float)diseffect/320);}void initialize(int total_pf) /*初始化相关数据结构*//*用户进程的内存页面数*/{int i;diseffect=0;for(i=0;i<total_vp;i++){pl[i].pn=i;pl[i].pfn=INVALID; /*置页面控制结构中的页号，页面为空*/pl[i].counter=0;pl[i].time=-1; /*页面控制结构中的访问次数为0，时间为-1*/}for(i=1;i<total_pf;i++){pfc[i-1].next=&pfc[i];pfc[i-1].pfn=i-1;/*建立pfc[i-1]和pfc[i]之间的连接*/}pfc[total_pf-1].next=NUL;pfc[total_pf-1].pfn=total_pf-1;freepf_head=&pfc[0]; /*页面队列的头指针为pfc[0]*/}/*说明：本程序在Linux的gcc下和c-free下编译运行通过*/【http://wenku..com/link?url=o_】
不知道能不能打开-是复制的 但也辛苦半天 忘采纳~

㈤ 如何证明dijkstra 算法是全局最优算法

证明：
（I）首先考虑最简单的情况，找找思路。
由于现在只知道S到S的最短距离，也就是0，所以第一步只能考虑从S出发直接到达各点的距离(显然在这个时候考虑路径存在中间顶点没有意义，因为你不能确定S到这个中间顶点的最短路径)。得到S直达各点的w(S,V_i)，i=1,2,...,n-1，与w[0,i]比较，w[1,i]保存小值。
这个时候，Dijkstra的做法是选出所有d[0,i]，i=0...n-1，为false的对应的w[1,i]，i=0...n-1，中的最小值w[1,k]并认为这就是源点S到目标顶点V_k的最短距离。这很好理解，因为假设S到V_k的最短距离是另外一条路径，则必然存在一个中间顶点，不妨设为V_u，u=0...n-1，则有w(S,V_u) + w(V_u, V_k) < w(S,V_k)，那么必有w(S,V_u) < w(S,V_k)，显然，这与w[1,k]是最小值矛盾，所以w[1,k]就是S到V_k的最短距离，此时把d[1,k]标记为true。
算法的中间值如何得出：
其实以上的叙述已经说明了中间值是如何得到的。设w[x,y]是当前刚确定的源点S到目标定点V_y的最短距离，其中x=0...n-1，y=0...n-1，对所有d[x,i]，i=0...n-1，为false的点，更新w[x+1,i]为w[x,i]与(w[x,y]+w(V_y,V_i))的较小值。（I）里的w[x,y]就是w[0,0]。
（II）现在考虑一般情况
设已求得一个集合A，|A|=k，现在求S到第(k+1)个点(注意不一定是V_(k+1)，这里的k只是A的基数而已)。
设w[k-1,u]，u=0...n-1，是在集合A的基数为k时，所有未访问的w[k-1,i]，i=0...n-1，保存的中间值中的最小值(也就是最后一个纳入集合A的顶点，k-1-0+1=k)。标记d[k-1,u]为true，对所有w[k,i]，更新d[k-1,i]为false的w[k,i]的值，使其为w[k-1,i]与w[k-1,u]+w(V_u, V_i)的较小值，然后选出d[k,i]为false的所有w[k,i]的最小值w[k,p]，p=0...n-1，即源点S到目标顶点p的最短距离，标记d[k,p]为true，继续这一过程，直到某一次求出的最小值为int.MaxValue(表示之后的点都不能到达)。
道理仍然是一样的，如果这个最小值w[k,p]不是源点S到顶点V_p的最短距离，那么设S经过顶点V_t然后到达V_p(V_t是这条路径的倒数第二个顶点)。V_t存在两种可能，要么属于集合A但不是顶点V_u，要么属于集合B。
（i）如果V_t属于A但不是顶点V_u，由于每一个中间值在每求出一个最短距离时都是比较过的，也就是说，在求出S到V_t的最短距离时，S->V_t->V_p的长度必然是和原来的S->V_p的路径长度比较过的，一定会保存下来，则不可能得到当前这个w[k,p]，w[k,p]里保存的应该是S经过V_t到V_p的长度而不是S经过V_u到V_p的长度。
（ii）如果V_t属于B，不妨设这条路径为S->V_r->V_o->V_t->V_p，其中V_r属于A，V_o，V_t可以是同一点，也可以是不同点，但是他们都不属于A而是属于B，那么显然有S->V_r->V_o的长度小于S->V_r->V_o->V_t->V_p的长度小于w[k,p]，即w[k,o] < w[k,p]，与w[k,p]是最小值矛盾。
(iii) 如果路径为S->V_t->V_p且V_t属于B，那么显然S->V_t比S->V_p要近，也就是说，在选择下一个最小值的时候，应该选择w[s,t]而非w[s,p]。
所以，这样一个顶点V_t不存在，一般情况得证。
证毕。

㈥ 漫谈算法如何证明贪心算法是最优 using exchange argument

这里主要是介绍一种证明贪心算法是最优的一种方法：Exchange Argument （不知道应该怎么翻译到中文，交换参数？感觉听起来挺别扭的，不像是一个方法的名字~o( □ )o）
Exchange Argument的主要的思想也就是 先假设 存在一个最优的算法和我们的贪心算法最接近，然后通过交换两个算法里的一个步骤(或元素)，得到一个新的最优的算法，同时这个算法比前一个最优算法更接近于我们的贪心算法，从而得到矛盾，原命题成立。
下面来看一个更为formal的解释：
步骤：
Step0: 给出贪心算法A的描述
Step1: 假设O是和A最相似(假设O和A的前k个步骤都相同，第k+1个开始不同，通常这个临界的元素最重要)的最优算法
Step2: [Key] 修改算法O(用Exchange Argument，交换A和O中的一个元素)，得到新的算法O’
Step3: 证明O’ 是feasible的，也就是O’是对的
Step4: 证明O’至少和O一样，即O’也是最优的
Step5: 得到矛盾，因为O’ 比O 更和A 相似。
证毕。
当然上面的步骤还有一个变种，如下：
Step0: 给出贪心算法A的描述
Step1: 假设O是一个最优算法（随便选，arbitrary）
Step2: 找出O和A中的一个不同。（当然这里面的不同可以是一个元素在O不再A，或者是一个pair的顺序在A的和在O的不一样。这个要根据具体题目）
Step3：Exchange这个不同的东西，然后argue现在得到的算法O 不必O差。
Step4: Argue 这样的不同一共有Polynomial个，然后我exchange Polynomial次就可以消除所有的不同，同时保证了算法的质量不比O差。这也就是说A 是as good as 一个O的。因为O是arbitrary选的，所以A是optimal的。
证毕
下面给几个例子：
例 Maximum Cardinality Disjoint Interval Problem
问题描述：给一些时间片段集合T={（a1，b1）（a2，b2），。。。，（an，bn）}，找出一个元素个数最多的子集S，子集中的每个元素的时间片段没有交叉。
Greedy Algorithm: 每次都选所有interval 中bi最小的那个，把（ai，bi）加入S，然后把（ai，bi）在T中删除，同时把T中所有和（ai，bi）有交叉的interval删除，然后再在T中找最小的bj，循环上面的操作，直到没有可以在添加的。
证明上面说的Greedy Algorithm是最优的。
下面就用第一个证明的步骤来证。
我们的Greedy Algorithm记为A，假设A不是最优的，那么就一定存在一个O，O是和A最相近的一个最优的算法，最相近是指和O和A的前K-1个选择都相同，第K个是不同的。
假设对于A，A第k个选择的是（ai，bi）；而O第K个选择的是（aj，bj）。从A的定义我们可以直到，bi<=bj。