贪心算法简介 -- 活动时间问题

贪心算法简介：
贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的是在某种意义上的局部最优解。

贪心算法不是对所有问题都能得到整体最优解，关键是贪心策略的选择，选择的贪心策略必须具备无后效性，即某个状态以前的过程不会影响以后的状态，只与当前状态有关。

基本思路
思想
贪心算法的基本思路是从问题的某一个初始解出发一步一步地进行，根据某个优化测度，每一步都要确保能获得局部最优解。每一步只考虑一个数据，他的选取应该满足局部优化的条件。若下一个数据和部分最优解连在一起不再是可行解时，就不把该数据添加到部分解中，直到把所有数据枚举完，或者不能再添加算法停止 。

过程

• 建立数学模型来描述问题；
• 把求解的问题分成若干个子问题；
• 对每一子问题求解，得到子问题的局部最优解；
• 把子问题的解局部最优解合成原来解问题的一个解。

算法特性编辑
贪婪算法可解决的问题通常大部分都有如下的特性：
随着算法的进行，将积累起其它两个集合：一个包含已经被考虑过并被选出的候选对象，另一个包含已经被考虑过但被丢弃的候选对象。

有一个函数来检查一个候选对象的集合是否提供了问题的解答。该函数不考虑此时的解决方法是否最优。
还有一个函数检查是否一个候选对象的集合是可行的，也即是否可能往该集合上添加更多的候选对象以获得一个解。和上一个函数一样，此时不考虑解决方法的最优性。
选择函数可以指出哪一个剩余的候选对象最有希望构成问题的解。

最后，目标函数给出解的值。

为了解决问题，需要寻找一个构成解的候选对象集合，它可以优化目标函数，贪婪算法一步一步的进行。起初，算法选出的候选对象的集合为空。接下来的每一步中，根据选择函数，算法从剩余候选对象中选出最有希望构成解的对象。如果集合中加上该对象后不可行，那么该对象就被丢弃并不再考虑；否则就加到集合里。每一次都扩充集合，并检查该集合是否构成解。如果贪婪算法正确工作，那么找到的第一个解通常是最优的

举个栗子：
还是上篇文中的 活动时间问题：

想要使用贪心算法的话，得先找到适合贪心算法的规律（局部最优选择）
对于任何非空的活动集合S，假如am是S中结束时间最早的活动，则am一定在S的某个最大兼容活动子集中。

代码实现：

using System;

namespace _5_1_1贪心算法_活动选择问题
{ class Program { static void Main(string[] args) { List<int> resultList =  Activity(1, 11, 0, 24); foreach (int item in resultList) { Console.WriteLine(item); } Console.ReadKey(); } //活动开始时间s，结束时间f static int[] s = { 0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12, 24 }; static int[] f = { 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 24 }; //参数：开始/结束的活动个数，开始/结束活动的时间 public static List<int> Activity(int startNumber, int endNumber,int startTime,int endTime ) { if (startNumber > endNumber || startTime >= endTime) return new List<int>(); //找到活动结束时间最早的活动 int temp = 0; for (int i = startNumber; i <= endNumber; i++) { if (s[i] >= startTime && f[i] <= endTime) { temp = i; break; } } //找剩下的时间中结束时间最早的活动 List<int> list = Activity(temp + 1, endNumber, f[temp], endTime); list.Add(temp); return list; } }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
 

迭代法更符合上面贪心算法的文字描述，，，
代码如下：

using System;

namespace _5_1_2贪心算法_活动选择问题_迭代
{ class Program { static void Main(string[] args) { // 活动开始时间s，结束时间f int[] s = { 0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12, 24 }; int[] f = { 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 24 }; //开始结束活动的时间 int startTime = 0; int ensTime = 24; //存储最大活动个数的列表 List<int> list = new List<int>(); //从第一个活动到最后一个活动 for (int i = 1; i <= 11; i++) { //判断每个活动是否子活动时间区间内 if(s[i]>= startTime && f[i]<= ensTime) { //在则记录，不在不处理 list.Add(i); //若在则只需要从此活动的结束时间继续搜索即可（更新活动时间） startTime = f[i]; } } foreach (int item in list) { Console.WriteLine(item); } Console.ReadKey(); } }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
 

文章来源: czhenya.blog.csdn.net，作者：陈言必行，版权归原作者所有，如需转载，请联系作者。

原文链接：czhenya.blog.csdn.net/article/details/78976035