貪心算法

由于貪心算法本身的特殊性，我們?cè)谑褂秘澬乃惴ㄖ氨仨氁M(jìn)行證明，保證算法滿足貪心選擇性質(zhì)。具體的證明方法無(wú)外乎就是通過(guò)數(shù)學(xué)歸納法來(lái)進(jìn)行證明。但大部分人可能并不喜歡枯燥的公式，因而我這里提供一個(gè)使用貪心算法的小技巧。由于貪心算法某種程度上算是動(dòng)態(tài)規(guī)劃算法的特例，使用條件比較苛刻，因而能夠用動(dòng)態(tài)規(guī)劃解決的問(wèn)題盡量都是用動(dòng)態(tài)規(guī)劃來(lái)進(jìn)行先解決，如果在用完動(dòng)態(tài)規(guī)劃之后，提交時(shí)發(fā)現(xiàn)問(wèn)題超時(shí)，并且進(jìn)行狀態(tài)壓縮之后仍然超時(shí)，此時(shí)我們就可以**考慮使用貪心算法來(lái)進(jìn)行解決。**最后強(qiáng)調(diào)一下，我們?cè)谑褂秘澬乃惴ㄖ?，如果要保證解法的絕對(duì)正確，一定要對(duì)問(wèn)題進(jìn)行證明，切記，切記?。?/p>

下邊我們以區(qū)間調(diào)度問(wèn)題為例，來(lái)講一下貪心算法到底該如何取用。

區(qū)間調(diào)度問(wèn)題

問(wèn)題描述：

給你很多形如 [start, end] 的閉區(qū)間，請(qǐng)你設(shè)計(jì)一個(gè)算法，算出這些區(qū)間中最多有幾個(gè)互不相交的區(qū)間。

舉個(gè)例子，intvs = [[1,3], [2,4], [3,6]]，這些區(qū)間最多有 2 個(gè)區(qū)間互不相交，即 [[1,3], [3,6]]，你的算法應(yīng)該返回 2。注意邊界相同并不算相交。

這個(gè)問(wèn)題大眼一看好像有很多貪心策略可供選擇，比如我們可以選擇區(qū)間最短的？或者選擇開(kāi)始最早的？。。。

但是上面幾種策略，我們都可以比較容易的舉出反例來(lái)排除，同時(shí)這也是貪心算法的另一個(gè)小技巧--雖然好多時(shí)候直接證明貪心策略的正確性很難，但是我們可以從反證法入手，對(duì)貪心策略進(jìn)行證偽，排除許多錯(cuò)誤的貪心策略。😄😄

好了，說(shuō)了這么多，那針對(duì)該問(wèn)題正確的貪心策略到底是哪個(gè)？

其實(shí)正確的思路也比較簡(jiǎn)單，可以分成下面三步：

1. 從區(qū)間集合中選擇一個(gè)區(qū)間 x，這個(gè) x 是所有區(qū)間中結(jié)束最早的（end 最?。?/li>
2. 把所有與 x 區(qū)間相交的區(qū)間從區(qū)間集合中刪除掉。
3. 重復(fù) 1 和 2，直到區(qū)間集合為空。之前選出的那些 x 的集合就是最大的不想交子集。
   

這個(gè)思路實(shí)現(xiàn)成算法的話，可以按照每個(gè)區(qū)間的 end 數(shù)值進(jìn)行升序排序，因?yàn)檫@樣處理以后實(shí)現(xiàn)步驟 1 和步驟 2 就會(huì)容易很多。

我們通過(guò)下面這個(gè)動(dòng)圖來(lái)輔助理解其整個(gè)過(guò)程。

由于我們?cè)谟?jì)數(shù)之前進(jìn)行了排序，所以所有與 x 相交的區(qū)間必然會(huì)和 x 的 end 相交；如果一個(gè)區(qū)間不想與 x 的 end 相交，它的 start 必須要大于或者等于 x 的 end。

具體實(shí)現(xiàn)的代碼如下：

 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];
          }
        });
	//排序后的第一個(gè)必然可用
    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;
  }

應(yīng)用

如果學(xué)會(huì)了上面的區(qū)間調(diào)度問(wèn)題的話，leetCode 上邊有兩個(gè)題目，我們便都可以拿下了。

這個(gè)問(wèn)題大眼一看好像和我們之前講的那個(gè)區(qū)間調(diào)度問(wèn)題毫不相關(guān)，但仔細(xì)分析一下，好像是一模一樣的問(wèn)題，如果最多有 n 個(gè)不重疊的區(qū)間，那么就至少需要 n 個(gè)箭頭穿透所有區(qū)間。

因而問(wèn)題也就轉(zhuǎn)化成了，尋找不重疊區(qū)間的個(gè)數(shù)，但我們要注意的一點(diǎn)是，在 intervalSchedule 算法中，如果兩個(gè)區(qū)間的邊界觸碰，不算重疊；而按照這道題目的描述，箭頭如果碰到氣球的邊界氣球也會(huì)爆炸，所以說(shuō)相當(dāng)于區(qū)間的邊界觸碰也算重疊。

代碼實(shí)現(xiàn)如下：

public int findMinArrowShots(int[][] points) {
    if (points.length <= 0) {
      return 0;
    }
    // 在排序的過(guò)程中要考慮溢出情況的發(fā)生
    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;
  }

總結(jié)

本文主要結(jié)合一個(gè)例子，講了貪心算法的使用方式。

貪心算法實(shí)現(xiàn)起來(lái)容易，但難在證明。因而文中提供了兩個(gè)小竅門輔助判斷是否使用貪心算法：

1. 在使用考慮貪心算法之前，先考慮使用動(dòng)態(tài)規(guī)劃（考慮狀態(tài)壓縮）解決該問(wèn)題，如果問(wèn)題依然超時(shí)，則考慮使用貪心算法。
2. 在確定貪心策略之前，先用一些特殊的例子驗(yàn)證貪心策略的正確性。對(duì)于正確的貪心策略，為了保證算法的絕對(duì)正確，要通過(guò)數(shù)學(xué)歸納法進(jìn)行驗(yàn)證。

以上就是貪心算法原理及在Java中的使用的詳細(xì)內(nèi)容，更多關(guān)于Java 貪心算法的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

最新評(píng)論