算法設計與分析

1、精選優(yōu)質(zhì)文檔-傾情為你奉上計算機算法設計與分析1、 實驗名稱：用貪心算法解決磁盤文件最優(yōu)存儲問題。2、 實驗目的：1）理解貪心算法的概念和掌握其基本要素； 2）針對具體問題，能應用貪心算法設計有效算法，提高對實際 問題的分析、設計和實現(xiàn)能力； 3）為后續(xù)課程的學習及課程設計打下堅實的實踐基礎。3、 實驗內(nèi)容： 1）問題描述： 設磁盤上有n個文件，f1,f2,fn，每個文件占磁盤上1個磁道。這n個文件的檢索概率分別是p1,p2,pn,且p1+p2+pn =1。磁頭從當前磁道移到被檢信息磁道所需的時間可用這2 個磁道之間的徑向距離來度量。如果文件pi存放在第i道上, ，則檢索這n 個文件的期望時間

2、是 ,其中d(I,j) 是第i道與第j 道之間的徑向距離|i-j|。磁盤問題就是要確定這n 個文件在磁盤上的存儲位置，使期望檢索時間達到最小。設計一個解此問題的算法，并分析算法的正確性與計算復雜性。 2）問題分析： a、通過對所給數(shù)據(jù)33 55 22 11 9的所有組合進行窮舉計算可以發(fā)現(xiàn)規(guī)律所在。兩個最優(yōu)解是：9 22 55 33 11以及11 33 55 22 9 b、通過進一步的研究分析可以證明這樣的規(guī)律是正確的。四、算法設計思路：如果對任何i，j，當i<>j時，pi<>pj，則n個文件在磁盤上將有N!種不同的存儲方式。如果考慮到f1，f2fn，這種排列方式與fn

3、f1排列的期望檢索時間相等，則要計算n!/2種不同的盤列方式。對于指定的i和j，pi和pj是不變的，可變因子是d(i,j),如果將d(i,j)視為一個元素恒定的集合，則他們與排列順序無關。先將這n個文件按其概率進行排序。設排序后有p1>=p2>=>=pn.則采用談心算法將文件f1放到中心磁道上，f2，f3分別靠著f1的左右磁道，f4在f2右邊得到最佳的方案。五、問題的貪心選擇性質(zhì)及最優(yōu)子結(jié)構(gòu)性質(zhì)：磁盤文件最優(yōu)存儲問題具有貪心選擇性質(zhì)：先將n個文件從大到小按概率進行排序。假設排序后有p1>=p2>=>=pn。貪心選擇性質(zhì)表示每次所選擇加入的對象文件，都能得到當

4、前的最優(yōu)值，即使得期望檢索時間達到最小。在磁盤最優(yōu)存儲問題中，要想使期望檢索時間達到最小。那么就要使兩個概率較大者的徑向距離越小越好。因此第一次從p1>=p2>=>=pn中選取P1所對應的文件f1置于中心磁道上。隨后從剩余概率隊列中選取概率最大和次最大者所對應的文件放在靠著f1的左磁道，和f1的右磁道。這將得到初始的最優(yōu)值。同樣地，繼續(xù)選擇剩余概率隊列中概率最大和次最大者所對應的文件分別置于靠著剛才所得最優(yōu)位置的左磁道和右磁道上，將得到新的最優(yōu)值。所以磁盤最優(yōu)存儲問題具有貪心選擇性質(zhì)。最優(yōu)子結(jié)構(gòu)性質(zhì)：按照這n個文件的排序概率（p1>=p2>=>=pn），假設

5、排序后的理想最優(yōu)序列為：f（n-1）,f(n-3),f(n-5),f(i)f4,f2,f1,f3,f5,f(j)f(n-2),fn。（n為奇數(shù)）。若n為偶數(shù)個，則補上一個數(shù)0。那么不管n為奇數(shù)或者是偶數(shù)，其理想最優(yōu)序列都可以表示為f（n-1）,f(n-3),f(n-5),f(i)f4,f2,f1,f3,f5,f(j)f(n-2),fn。（因為加上一個0，對其達到最小期望檢索時間無影響，所以可以進行此處理。）利用反證法思想假設存在一個f（n-1）,f(n-3),f(n-5),f(j)f4,f2,f1,f3,f5,f(i)f(n-2),fn。該序列是原序列對調(diào)f(i)與f(j)的位置所得。該序列所

6、得到的期望檢索時間小于上面的貪心策略時間。經(jīng)驗證發(fā)現(xiàn)，該序列所獲得的期望檢索時間>原所獲得的期望檢索時間。與最優(yōu)值相矛盾。故貪心解為最優(yōu)解。六、實驗代碼：#include"stdio.h"#define MAX 100void sort(float *a,int n) int i,j;float temp;for(i=0;i<n-1;i+)for(j=0;j<n-1-i;j+)if(aj>aj+1)temp=aj;aj=aj+1;aj+1=temp;void main()int i,j,n,k;float aMAX,xMAX;float m=0,t=

7、0;printf("請輸入文件數(shù)：n");scanf("%d",&n);printf("請分別輸入這些文件的檢索概率：n");for(i=0;i<n;i+)scanf("%f",&ai);sort(a,n);k=(n-1)/2;xk=an-1;for(i=k+1;i<n;i+) xi=an-2*(i-k);for(i=k-1;i>=0;i-)xi=an-2*(k-i)-1;for(i=0;i<n;i+)m+=ai;for(j=i+1;j<n;j+)t+=xi*xj*(j-i);t=t/(m*m);printf("經(jīng)過合理的安排之后，最少期望檢索為:%f n&quo