證明最優演算法

㈠ [演算法] 貪心演算法證明思路

動態規劃和貪心演算法都需要問題具有最優子結構，但不同的是貪心 自頂向下 ，先做選擇再求解一個結果子問題，而動態規劃自底向上求解子問題，需要先求出子問題的最優解再做選擇。這是因為，動態規劃最優解有兩個子問題時，求解子問題 時有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。