活動選擇問題理解貪心演算法
一.貪心演算法
對於一些最優解問題，每一步都做當前的最優選擇，最後得到的選擇結果就是最終問題的最優解，這樣的問題就適用貪心演算法。貪心演算法在每一步做出局部的最優選擇，最後得到整個問題的最優解。顯然，實際問題中存在大量問題並不是每一步最優就能最終最優的，如01背包問題，因此貪心演算法解決問題簡化了解決方案，但是得到的最終結果的可信度不如動態規劃演算法或者分治演算法高，往往考慮不夠全面。問題能否使用貪心演算法解決要根據問題實際分析。
二.活動選擇問題
有n個需要在同一天使用同一個教室的活動a1,a2,…,an，教室同一時刻只能由一個活動使用。每個活動ai都有一個開始時間si和結束時間fi 。一旦被選擇後，活動ai就佔據半開時間區間[si,fi)。如果[si,fi]和[sj,fj]互不重疊，ai和aj兩個活動就可以被安排在這一天。該問題就是要安排這些活動使得盡量多的活動能不衝突的舉行（最大兼容活動子集）。例如下圖所示的活動集合S，其中各項活動按照結束時間單調遞增排序。
{a3,a9,a11}是一個兼容的活動子集，但它不是最大子集，因為子集{a1,a4,a8,a11}更大，實際上它是我們這個問題的最大兼容子集，但它不是唯一的一個{a2，a4，a9，a11}
1.動態規劃演算法
static void Main(string[] args) { //添加兩個活動，一個從0點到0點，一個從24點到24點 //記錄活動start時間的數組 int[] s = { 0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12, 24 }; //記錄活動end時間的數組 int[] e = { 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 24 }; //記錄所有方案的二維數組 //數組的行數和列數對應了活動方案的編號，如result[3,7]代表了第3個到第7個活動的活動最大兼容子集 List<int>[,] result = new List<int>[13, 13]; //為二維數組賦初值，集合中的數字代表哪些活動組合成最大兼容子集 for (int m = 0; m < 13; m++) { for (int n = 0; n < 13; n++) { result[m, n] = new List<int>(); } } //雙重循環 //依次遍歷存儲所有活動的最大兼容子集，j是最後一個活動編號，i是第一個活動編號 for (int j = 0; j < 13; j++) { for (int i = 0; i < j - 1; i++) { //int集合sij用於存儲計算出的第i到第j個活動的最大兼容子集 List<int> sij = new List<int>(); //循環遍歷每一個活動，number是當前指向的活動編號 for (int number = 1; number < s.Length - 1; number++) { //如果當前遍歷到的活動的時間在最後一個活動j的開始時間和第一個活動i的結束時間之間，這個活動就能插入兩個活動之間進行 if (s[number] >= e[i] && e[number] <= s[j]) { sij.Add(number); } } //如果有活動插入到了兩個活動之間 if (sij.Count > 0) { //保存最大兼容子集的活動的數量 int maxCount = 0; //保存最大兼容子集 List<int> tempList = new List<int>(); //循環遍歷插入的活動 foreach (int number in sij) { //計算最大兼容子集的活動的數量 int count = result[i, number].Count + result[number, j].Count + 1; //更新最大兼容子集的活動數量 //可能有多個活動可以插入兩個活動之間，因此需要判斷哪一個活動插入後是從i活動到j活動的最大兼容子集 //將最大兼容子集的活動編號保存起來 if (maxCount < count) { maxCount = count; tempList = result[i, number].Union<int>(result[number, j]).ToList<int>(); tempList.Add(number); } } //更新計算出的i活動到j活動的最大兼容子集 result[i, j] = tempList; } } } //結果取出第0個活動到第12個活動的最大兼容子集即可 List<int> a = result[0, 12]; foreach (int item in a) { Console.Write(item + " "); } Console.ReadKey(); }
2.貪心演算法（遞歸解決）
可以看到在ActivitySelection方法的for循環中，找到了一個局部最優結果就break跳出循環繼續尋找下一個結果了（遞歸尋找下一個局部最優解），當前這個結果只是當前的最優解，是否是最終問題的最優解並沒有管，因此貪心演算法的結果並不是那麼可信
static void Main(string[] args) { List<int> list = ActivitySelection(1, 11, 0, 24); foreach(int t in list) { Console.Write(t + " "); } Console.ReadKey(); } static int[] s = { 0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12, 24 }; static int[] e = { 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 24 }; /// <summary> /// 計算給定的活動編號之間的活動能否在給定時間內進行 /// </summary> /// <param name="startActivityNumber">開始的活動編號</param> /// <param name="endActivityNumber">結束的活動編號</param> /// <param name="startTime">開始時間</param> /// <param name="endTime">結束時間</param> /// <returns></returns> public static List<int> ActivitySelection(int startActivityNumber,int endActivityNumber,int startTime,int endTime) { //如果活動已經找完或者時間已經找完，結束遞歸調用 if (startActivityNumber > endActivityNumber || startTime >= endTime) return new List<int>(); //記錄可以插入的活動編號 int tempNumber = 0; //循環遍歷活動編號，看能否在給定時間內進行 for (int number = startActivityNumber; number <= endActivityNumber; number++) { //判斷能否在給定時間內進行 if(s[number] >= startTime && e[number] <= endTime) { tempNumber = number; break; } } //找到了一個能插入的活動後，繼續遞歸找下一個能插入的活動 List<int> list = ActivitySelection(tempNumber + 1, endActivityNumber, e[tempNumber], endTime); //將找到的活動編號添加入集合中 list.Add(tempNumber); //返回找到的結果 return list; }
3.貪心演算法（迭代解決）
迭代的解決方案只需要遍歷所有的活動，然後看活動能否在指定時間內進行，如果可以的話就將該活動添加進集合，然後將下一個活動可以開始的時間更新為剛才活動的結束時間。
static void Main(string[] args) { List<int> list = ActivitySelection(1, 11, 0, 24); foreach(int t in list) { Console.Write(t + " "); } Console.ReadKey(); } static int[] s = { 0, 1, 3, 0, 5, 3, 5, 6, 8, 8, 2, 12, 24 }; static int[] e = { 0, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 24 }; /// <summary> /// 計算給定的活動編號之間的活動能否在給定時間內進行 /// </summary> /// <param name="startActivityNumber">開始的活動編號</param> /// <param name="endActivityNumber">結束的活動編號</param> /// <param name="startTime">開始時間</param> /// <param name="endTime">結束時間</param> /// <returns></returns> public static List<int> ActivitySelection(int startActivityNumber,int endActivityNumber,int startTime,int endTime) { //保存結果的list List<int> list = new List<int>(); //循環遍歷活動編號，看能否在給定時間內進行 for (int number = 1; number <= 11; number++) { //判斷能否在給定時間內進行，找到可以在給定時間內進行的活動後將活動編號加入結果的集合，並且下一個活動的開始時間需要更新 if(s[number] >= startTime && e[number] <= endTime) { list.Add(number); startTime = e[number]; } } //返回找到的結果 return list; }
