算法分析与设计实验二贪心算法

实验二：贪心算法

【实验目的】

应用贪心算法求解活动安排问题。

【实验性质】

验证性实验。

【实验要求】

活动安排问题是可以用贪心算法有效求解的很好的例子。

问题：有n个活动的集合A={1,2,…,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。

求解：安排尽量多项活动在该场地进行，即求A的最大相容子集。

设待安排的11个活动的开始时间和结束时间按结束时间的升序排列如下： i 1 2 3 5 3 0 6 4 5 7 5 3 8 6 5 9 7 6 10 8 8 11 9 8 12 10 2 13 11 12 14 s[i] 1 f[i] 4 将此表数据作为实现该算法的测试数据。

【算法思想及采用的数据结构】

【程序代码】

【运行结果】

【算法分析和心得体会】

附加题：

【实验要求】

需要在某个城市的n个居民区之间铺设煤气管道，则在这n个居民区之间只要铺设n-1条管道即可。假设任意两个居民区之间都可以架设管道，但由于地理环境的不同，所需经费不同。选择最优的施工方案能使总投资尽可能少，这个问题即为求网的“最小生成树”问题。参照以下居民区示意图，使得求解算法为：在可能架设的m条管道中选取n-1条，既能连通n-1个居民区，有使总投资达到“最小”。网可采用邻接矩阵为存储结构，以定点对（i,j）的形式输出最小生成树的边。

D 23.1 675.9 C 41.1 56B A 38.2 441218.2 I 8.7 H 52.5 G 10.5 E 98.7 居民区示意图 85F 79应用贪心算法策略，采用普里姆算法或Kruskal算法来求解居民区示意图的最小生成树，采用合适的数据结构。用C语言或C++语言编写程序代码，选上述居民区示意图中的数据作为测试数据。并调试输出正确结果。

【算法思想及采用的数据结构】

【程序代码】

【运行结果】

【算法分析和心得体会】