算法设计与分析

计算机算法设计与分析一、实验名称：用贪心算法解决磁盘文件最优存储问题。二、实验目的：1）理解贪心算法的概念和掌握其基本要素；2）针对具体问题，能应用贪心算法设计有效算法，提高对实际问题的分析、设计和实现能力；3）为后续课程的学习及课程设计打下坚实的实践基础。三、实验内容：1）问题描述：设磁盘上有n个文件，f1,f2,…,fn，，每个文件占磁盘上1个磁道。这n个文件的检索概率分别是p1,p2,…,pn,且p1+p2+…+pn=1。磁头从当前磁道移到被检信息磁道所需的时间可用这2个磁道之间的径向距离来度量。如果文件pi存放在第i道上,，则检索这n个文件的期望时间是,njijijidpp1),(,其中d(I,j)是第i道与第j道之间的径向距离|i-j|。磁盘问题就是要确定这n个文件在磁盘上的存储位置，使期望检索时间达到最小。设计一个解此问题的算法，并分析算法的正确性与计算复杂性。2）问题分析：a、通过对所给数据335522119的所有组合进行穷举计算可以发现规律所在。两个最优解是：922553311以及113355229b、通过进一步的研究分析可以证明这样的规律是正确的。四、算法设计思路：如果对任何i，j，当ij时，pipj，则n个文件在磁盘上将有N!种不同的存储方式。如果考虑到f1，f2……fn，这种排列方式与fn……f1排列的期望检索时间相等，则要计算n!/2种不同的盘列方式。对于指定的i和j，pi和pj是不变的，可变因子是d(i,j),如果将d(i,j)视为一个元素恒定的集合，则他们与排列顺序无关。先将这n个文件按其概率进行排序。设排序后有p1=p2=…=pn.则采用谈心算法将文件f1放到中心磁道上，f2，f3分别靠着f1的左右磁道，f4在f2右边……得到最佳的方案。五、问题的贪心选择性质及最优子结构性质：磁盘文件最优存储问题具有贪心选择性质：先将n个文件从大到小按概率进行排序。假设排序后有p1=p2=…=pn。贪心选择性质表示每次所选择加入的对象文件，都能得到当前的最优值，即使得期望检索时间达到最小。在磁盘最优存储问题中，要想使期望检索时间达到最小。那么就要使两个概率较大者的径向距离越小越好。因此第一次从p1=p2=…=pn中选取P1所对应的文件f1置于中心磁道上。随后从剩余概率队列中选取概率最大和次最大者所对应的文件放在靠着f1的左磁道，和f1的右磁道。这将得到初始的最优值。同样地，继续选择剩余概率队列中概率最大和次最大者所对应的文件分别置于靠着刚才所得最优位置的左磁道和右磁道上，将得到新的最优值。所以磁盘最优存储问题具有贪心选择性质。最优子结构性质：按照这n个文件的排序概率（p1=p2=…=pn），假设排序后的理想最优序列为：f（n-1）,f(n-3),f(n-5),…,f(i)…f4,f2,f1,f3,f5,…,f(j)…f(n-2),fn。（n为奇数）。若n为偶数个，则补上一个数0。那么不管n为奇数或者是偶数，其理想最优序列都可以表示为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。该序列是原序列对调f(i)与f(j)的位置所得。该序列所得到的期望检索时间小于上面的贪心策略时间。经验证发现，该序列所获得的期望检索时间原所获得的期望检索时间。与最优值相矛盾。故贪心解为最优解。六、实验代码：#includestdio.h#defineMAX100voidsort(float*a,intn){inti,j;floattemp;for(i=0;in-1;i++){for(j=0;jn-1-i;j++){if(a[j]a[j+1]){temp=a[j];a[j]=a[j+1];a[j+1]=temp;}}}}voidmain(){inti,j,n,k;floata[MAX],x[MAX];floatm=0,t=0;printf(请输入文件数：\n);scanf(%d,&n);printf(请分别输入这些文件的检索概率：\n);for(i=0;in;i++)scanf(%f,&a[i]);sort(a,n);k=(n-1)/2;x[k]=a[n-1];for(i=k+1;in;i++)x[i]=a[n-2*(i-k)];for(i=k-1;i=0;i--)x[i]=a[n-2*(k-i)-1];for(i=0;in;i++){m+=a[i];for(j=i+1;jn;j++)t+=x[i]*x[j]*(j-i);}t=t/(m*m);printf(经过合理的安排之后，最少期望检索为:%f\n,t);}七、实验结果：输入文件示例输出文件示例Input：335522119output：0.547396也即这5个文件在磁盘上的存储位置是922553311或者113355229。