1009040130-贺程-实验3.doc

《算法分析与设计》实验报告 实验三 贪心方法算法设计 姓名 贺程 学号 1009040130 班级 电子商务1002班 时间 2013/3/26 地点 文波机房 同 组 人 无 指导教师 朱少林 实验目的与要求 掌握贪心法算法设计的一般思想和方法。 掌握背包问题、最小生成树、单源点最短路径算法设计。 掌握贪心法设计算法求解一般问题。 实验内容 背包问题的贪心法算法设计和程序验证。 最小生树算法设计和程序验证。 单源点最短路径算法设计和程序验证。 相关内容 贪心方法的一般思想 Procedure GREEDY(A, n) //A(1: n)包含n个输入// Solution←Ф //将解向量初始化为空// for i←1 to n do x←SELECT(A) if FEASIBLE(solution , x) then solution←UNION(solution, x) endif repeat return(solution) endGREEDY 背包问题的贪心算法 Procedure GREEDY-KNAPSACK(P, W, M, X, n) //P(1: n)和W(1: n)分别含有按P(i)/W(i)≥P(i+1)/W(i+1)按序的n件物品的效益值和重量。M是背包的容量大小，而X(1: n)是解向量。// integer i, n; real P(1: n), W(1: n), X(1: n), M, cu; X←0 //将解向量初始化为零// cu←M //cu是背包剩余容量// for i←1 to n do if W(i)cu then exit endif X(i)←1 cu←cu-W(i) repeat if i≤n then X(i)←cu/W(i) endif end GREEDY-KNAPSACK 最小生成树问题的Prim算法 Line procedure PRIM (E, COST, n, T, mincost) //E是G的边集，COST(n, n)是一个正实数集合，如果不存在边(i, j),则为+∞。计算一棵最小生成树并把它作为一个集合存放到数组T中，最小成本生成树的总成本最后赋给mincost。// 1 real COST(n, n), mincost; 2 integer NEAR(n), n, I, j, k, l, T(1: n-1, 2); 3 (k, l)←具有最小成本的边 4 mincost←COST(k, l) 5 ((T(1, 1),T(1, 2))←(k, l) 6 for i←1 to n do 7 if COST(i, l) COST(i, k) then NEAR(i)←l 8 else NEAR(j)←k endif 9 repeat 10 NEAR(k)←NEAR(l)←0 11 for i←2 to n-1 do 12 设j是NEAR(j)≠0 且COST(j, NEAR(j))最小的下标 13 ((T(i, 1),T(i, 2))←(j, NEAR(j)) 14 mincost←mincost+COST(j, NEAR(j)) 15 NEAR(j)←0 16 for k←1 to n do 17 if NEAR(k)≠0 and COST(k, NEAR(k))COST(k,j) 18 then NEAR(k)←j 19 endif 20 repeat 21 repeat 22 if mincost≥∞ then print(‘no spanning tree’) endif 23 endPRIM 最小生成树问题的Kruskal算法 Line procedure KRUSKAL(E,COST,n, T, mincost) //G有n个结点，E是G的边集，COST（u, v）u, v）mincost是它的成本。// 1 real mincost, COST(1: n, 1: n) 2 integer PARENT(1:n), T(1:n-1, 2), n 3 以边成本为元素构造一个min-堆 4 PARENT← -1 5 i←mincost←0 6 while in-1 and 堆非空