4.贪心算法_wg.docxVIP

贪心算法TSP旅行家从原点出发经历各个城市回到原点求最短路径代价矩阵如下：策略从任意城市出发，每次在没有到过的城市中选择最近一个，直到经所有城市回到出发点从1出发，选最近的4(2),从4开始，除了1,4，选最近的3(2)从3开始，除了1,4,3,选最近的5(5)从5开始，除了1435，选2（2）从2回1(3)1-4-3-5-2,代价2+2+5+2+3=14时间为O(n2)，因为每次都要搜n-1条边图着色，每个点从1开始依次考虑使用不冲突的颜色。如着色顺序1,2,3,4,5因为1使用c1,2与1相邻，只能使用c2；3可以使用c1；4可以使用c1；5可以使用c2如果着色顺序1,5,2,3,4因为1使用c1；5也可以使用c1；2使用c2；3与2和5冲突，只能使用c3，最终用3种颜色双向图着色 2n个顶点无向图，奇数点与除了i+1的所有偶数点邻接；偶数点与除了i-1的所有奇数点邻接从1,3,5,7…2n-1 使用c1，2,4,6,8….2n使用C2得到最优解：两种颜色如果使用1,2,3,4,…2n-1,2n，则需要n种颜色最小生成树权值之和最小的生成树Prism算法：任选一点开始，从已入选生成树中点集合中，找前往陌生点集合的最小邻接边Krushal算法：将邻接边排序，依次取最小的能联通的不会导致回路的邻接边背包问题 (可拆)有3个物品，其重量分别是{20, 30, 10}，价值分别为{60, 120, 50}，背包容量为50，哪么3种贪心策略所获得的价值为策略1选择价值最大的物品-背包总价上升很快，背包容量也消耗太快策略2选择最轻的物品-装尽可能多的物品，虽然容量消耗慢，背包价值没法保证迅速上升策略3选择单位重量价值最大的物品-两者之间寻找平衡0/1背包缺不能用贪心法求解，原因：物品不允许分割?无法保证将背包装满，常用动态规划法求解活动安排（greedySelector算法，使剩余的可安排时间段极大化，以便安排尽可能多的相容活动设待安排的11个活动的开始时间和结束时间按结束时间的非减序排列如下，贪心策略，首先选活动1，占用1-4时间，然后从2开始，依次选择不与活动1时间相冲突的活动，选择4，占用5-7时间选择不与1,4冲突的，8占用8-11时间选择不与1,4,8冲突的，11占用12-14时间最终结果1,4,8,11如活动已按结束时间排列排序，则只需遍历活动O(n)时间，否则需要排序O(nlogn)时间最优装载有一批集装箱要装上一艘载重量为c的轮船。其中集装箱i的重量为Wi。最优装载问题要求确定在装载体积不受限制的情况下，将尽可能多的集装箱装上轮船。解：先按重量排序，然后依次选择最轻的集装箱。计算时间为O(nlogn)，即快速排序的时间。单源最短路径Dijkstra算法，计算从源顶点1到其它顶点间最短路径的过程主循环体需要O(n)时间,每循环需要执行n-1次，所以完成循环需要O(n^2)时间，其余部分不超过O(n^2)时间多机调度问题NP完全问题，到目前为止还没有有效的解法，用贪心选择策略有时可以设计出较好的近似算法约定，每个作业均可在任何一台机器上加工处理，但未完工前不允许中断处理。作业不能拆分成更小的子作业3台机器M1，M2和M3加工处理。设7个独立作业{1,2,3,4,5,6,7}由处理时间分别为{2,14,4,16,6,5,3}先给机器1最长时间的作业4(16时间)然后给机器2剩余最长时间的作业2(14)给机器3作业5(6)，作业5先完成，检查三台机器，给M3作业6(5)M3上作业6完成再完成，检查三台，给M3作业3(4)。。。当作业数量n机器数量m时，计算时间为O(nlogn)