貪心算法原理及在Java中的使用

貪心算法

由於貪心算法本身的特殊性,我們在使用貪心算法之前必須要進行證明,保證算法滿足貪心選擇性質。具體的證明方法無外乎就是通過數學歸納法來進行證明。但大部分人可能並不喜歡枯燥的公式,因而我這裡提供一個使用貪心算法的小技巧。由於貪心算法某種程度上算是動態規劃算法的特例,使用條件比較苛刻,因而能夠用動態規劃解決的問題盡量都是用動態規劃來進行先解決,如果在用完動態規劃之後,提交時發現問題超時,並且進行狀態壓縮之後仍然超時,此時我們就可以**考慮使用貪心算法來進行解決。**最後強調一下,我們在使用貪心算法之前,如果要保證解法的絕對正確,一定要對問題進行證明,切記,切記!!

下邊我們以區間調度問題為例,來講一下貪心算法到底該如何取用。

區間調度問題

問題描述:

給你很多形如 [start, end] 的閉區間,請你設計一個算法,算出這些區間中最多有幾個互不相交的區間。

舉個例子,intvs = [[1,3], [2,4], [3,6]],這些區間最多有 2 個區間互不相交,即 [[1,3], [3,6]],你的算法應該返回 2。註意邊界相同並不算相交。

這個問題大眼一看好像有很多貪心策略可供選擇,比如我們可以選擇區間最短的?或者選擇開始最早的?。。。

但是上面幾種策略,我們都可以比較容易的舉出反例來排除,同時這也是貪心算法的另一個小技巧–雖然好多時候直接證明貪心策略的正確性很難,但是我們可以從反證法入手,對貪心策略進行證偽,排除許多錯誤的貪心策略。😄😄

好瞭,說瞭這麼多,那針對該問題正確的貪心策略到底是哪個?

其實正確的思路也比較簡單,可以分成下面三步:

  1. 從區間集合中選擇一個區間 x,這個 x 是所有區間中結束最早的(end 最小)。
  2. 把所有與 x 區間相交的區間從區間集合中刪除掉。
  3. 重復 1 和 2,直到區間集合為空。之前選出的那些 x 的集合就是最大的不想交子集。

這個思路實現成算法的話,可以按照每個區間的 end 數值進行升序排序,因為這樣處理以後實現步驟 1 和步驟 2 就會容易很多。

我們通過下面這個動圖來輔助理解其整個過程。

由於我們在計數之前進行瞭排序,所以所有與 x 相交的區間必然會和 x 的 end 相交;如果一個區間不想與 x 的 end 相交,它的 start 必須要大於或者等於 x 的 end。

具體實現的代碼如下:

 public int eraseOverlapIntervals(int[][] intervals) {
    if (intervals.length == 0) {
      return 0;
    }
    Arrays.sort(
        intervals,
        new Comparator<int[]>() {
          @Override
          public int compare(int[] o1, int[] o2) {
            return o1[1] - o2[1];
          }
        });
	//排序後的第一個必然可用
    int count = 1;
    int x_end = intervals[0][1];
    for (int[] interval : intervals) {
      if (interval[0] >= x_end) {
        count++;
        x_end = interval[1];
      }
    }
    return count;
  }

應用

如果學會瞭上面的區間調度問題的話,leetCode 上邊有兩個題目,我們便都可以拿下瞭。

這個問題大眼一看好像和我們之前講的那個區間調度問題毫不相關,但仔細分析一下,好像是一模一樣的問題,如果最多有 n 個不重疊的區間,那麼就至少需要 n 個箭頭穿透所有區間。

 

因而問題也就轉化成瞭,尋找不重疊區間的個數,但我們要註意的一點是,在 intervalSchedule 算法中,如果兩個區間的邊界觸碰,不算重疊;而按照這道題目的描述,箭頭如果碰到氣球的邊界氣球也會爆炸,所以說相當於區間的邊界觸碰也算重疊。

 

代碼實現如下:

public int findMinArrowShots(int[][] points) {
    if (points.length <= 0) {
      return 0;
    }
    // 在排序的過程中要考慮溢出情況的發生
    Arrays.sort(points, (a, b) -> Integer.compare(a[1], b[1]));
    int count = 1;
    int x_end = points[0][1];
    for (int[] point : points) {
      if (point[0] > x_end) {
        count++;
        x_end = point[1];
      }
    }
    return count;
  }

總結

本文主要結合一個例子,講瞭貪心算法的使用方式。

貪心算法實現起來容易,但難在證明。因而文中提供瞭兩個小竅門輔助判斷是否使用貪心算法:

  1. 在使用考慮貪心算法之前,先考慮使用動態規劃(考慮狀態壓縮)解決該問題,如果問題依然超時,則考慮使用貪心算法。
  2. 在確定貪心策略之前,先用一些特殊的例子驗證貪心策略的正確性。對於正確的貪心策略,為瞭保證算法的絕對正確,要通過數學歸納法進行驗證。

以上就是貪心算法原理及在Java中的使用的詳細內容,更多關於Java 貪心算法的資料請關註WalkonNet其它相關文章!

推薦閱讀: