活動安排問題

• 簡介
  • 活動安排問題是需要共享公共資源的一系列活動的高效安排問題，以在限定的資源前提下盡可能多地安排活動。一般，算法題中給出開始結束時間的活動序列都可以使用這種貪心思路。
• 問題描述
  • 有若干個活動，第i個活動的開始時間和結束時間是[Si,fi)，只有一間教室，活動之間不能交叉，即一個活動結束后另一個才能開始，求解最多能安排多少個活動？
• 問題分析
  • 目的是提高教室的利用率，盡可能多地安排活動。
  • 不妨考慮幾種容易想到的貪心策略。
    • 開始最早的活動優先
      • 顯然，有很多反例可以證明這個不合理之處。
    • 短活動優先
      • 看一個反例,[0,5),[5,10),[3,7)這里面最后的[3,7)最短，但是一旦安排了這個另外兩個就無法安排了，顯然，不合理。
    • 最少沖突的活動優先
      • 優先安排少的活動怎么樣呢？
      • 看個例子
        • [0,2),[2,4),[4,6),[6,8)
        • [1,3),[1,3),[1,3),[3,5),[5,7),[5,7),[5,7)
        • 第一行應該可以一起安排出來，但是按照沖突最少策略，最多安排三個活動。
    • 結束時間越早的活動優先
      • 這是看起來最不合理的，但是，可以證明一下。
        • 假設最優解OPT中安排了m個活動，我們把這些活動按照結束時間由小到大排序，顯然不沖突。假設排好順序后，這些活動是a(1),a(2)…a(m)。
        • 按照貪心策略，選出的活動自然是按照結束時間排好序的，并且也都是不沖突的，這些活動為b(1),b(2)…b(n)。
        • 關鍵問題是，假設a(1)=b(1),a(2)=b(2)…a(k)=b(k),但是a(k+1)!=b(k+1)，回答下面的問題
          • b(k+1)會在a(k+2),a(k+3)…a(m)中嗎？
            • 不會，因為b(k+1)的結束時間最早（我們就是如此貪心選擇的），即f(b(k+1))<=f(a(k+1))，而a(k+2),a(k+3),a(m)的開始結束時間都在f(a(k+1))之后，所以b(k+1)不在其中。
          • b(k+1)和a(1),a(2),a(k)沖突嗎？
            • 不沖突，因為a(1),a(2),a(k)就是(1),b(2),b(k)。
          • b(k+1)和a(k+2),a(k+3),a(m)沖突嗎？
            • 不沖突，因為f(b(k+1))<=f(a(k+1))，而a(k+2),a(k+3),a(m)的開始時間都在f(a(k+1))之后，更在f(b(k+1))之后了。
        • 因此，可以把a(k+1)換成b(k+1)，從而最優解和貪心的解多了一個相同的，經過一個一個替換，可以把最優解完全替換成貪心策略得到的解，從而證明這個貪心策略的最優性。
• 代碼
  • # -*-coding:utf-8-*-def bubble_sort(s, f):"""冒泡排序對結束時間排序，同時得到對應的開始時間的list:param s::param f::return:"""for i in range(len(f)):for j in range(0, len(f)-i-1):if f[j] > f[j+1]:f[j], f[j+1] = f[j+1], f[j]s[j], s[j+1] = s[j+1], s[j]return s, fdef greedy(s, f, n):a = [True for x in range(n)]# 選擇第一個活動j =0for i in range(1, n):# 如果下一個活動的開始時間大于等于上一個活動的結束時間if s[i] >= f[j]:a[i] = Truej = ielse:a[i] = Falsereturn aif __name__ == '__main__':s = [1, 2, 3, 5, 8]f = [3, 4, 5, 7, 9]s, f = bubble_sort(s, f)A = greedy(s, f, len(s))res = []for k in range(len(A)):if A[k]:res.append('({}, {})'.format(s[k], f[k]))print(''.join(res))
• 運行結果
• 補充說明
  • 具體代碼可以查看我的Github，歡迎Star或者Fork
  • 參考書《你也能看得懂的Python算法書》

總結

以上是生活随笔為你收集整理的贪心算法-02活动安排问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。