對于AI產(chǎn)品經(jīng)理來說，掌握一些算法是必要的。本文將從五個方面，講述AI產(chǎn)品經(jīng)理必修的貪心算法，希望對你有幫助。

去年“新智元”有一篇報道《清華畢業(yè)計算機教授遭持槍劫車，靠“貪心算法”追回秒殺美國警察》，整個故事像看微小說一樣，可對于核心問題“貪心算法”是什么并沒有說清楚，于是就有了下面的內(nèi)容。

一、什么是貪心算法

貪心的意思在于在作出選擇時，每次都要選擇對自身最為有利的結(jié)果，保證自身利益的最大化，貪心算法就是利用這種貪心思想而得出一種算法。

貪心算法可以簡單描述為：大事化小，小事化了。對于一個較大的問題，通過找到與子問題的重疊，把復雜的問題劃分為多個小問題。并且對于每個子問題的解進行選擇，找出最優(yōu)值，進行處理，再找出最優(yōu)值，再處理。也就是說貪心算法是一種在每一步選擇中都采取在當前狀態(tài)下最好或最優(yōu)的選擇，從而希望得到結(jié)果是最好或最優(yōu)的算法。

貪心算法在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。

二、貪心算法基本思路

步驟一：建立數(shù)學模型來描述問題。

步驟二：把求解的問題分成若干個子問題。

步驟三：對每個子問題求解，得到子問題的局部最優(yōu)解。

步驟四：把子問題的解局部最優(yōu)解合成原來問題的一個解。

三、貪心算法的選擇

所謂貪心選擇是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，換句話說，當考慮做何種選擇的時候，我們只考慮對當前問題最佳的選擇而不考慮子問題的結(jié)果。

貪心算法以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導致問題的整體最優(yōu)解。

我們下面通過示例來看一下貪心算法如何選擇。

四、貪心算法示例

看一下《算法導論》中的經(jīng)典例題：活動選擇問題。

有n個需要在同一天使用同一個教室的活動a1，a2……an，教室同一時刻只能由一個活動使用。每個活動ai都有一個開始時間si和結(jié)束時間fi 。一旦被選擇后，活動ai就占據(jù)半開時間區(qū)間[si,fi)。如果[si,fi]和[sj,fj]互不重疊，ai和aj兩個活動就可以被安排在這一天。該問題就是要安排這些活動使得盡量多的活動能不沖突的舉行（標紅的是我們利用貪心算法求出的結(jié)果1、4、8、11）。

第一步：分析題目

目標函數(shù)count（n）活動次數(shù)最多。

約束條件是下一個活動開始時間大于或等于上一個活動開始時間s[i]>=f[j]。

第二步：選擇解題思路

• 每次選擇開始時間最早的活動
• 每次選擇持續(xù)時間最短的活動
• 每次選取結(jié)束時間最早的活動

第三步：證明上面哪種思路可以應用于本題

為了方便，我們用不同顏色的線條代表每個活動，線條的長度就是活動所占據(jù)的時間段，藍色的線條表示我們已經(jīng)選擇的活動；紅色的線條表示我們沒有選擇的活動。

1）如果我們每次都選擇開始時間最早的活動，不能得到最優(yōu)解

證明（反證法）：

例如我們選擇了10號活動（開始時間2點，結(jié)束時間13點）；

2號活動待選擇（開始時間3點，結(jié)束時間5點）；

則會出現(xiàn)上圖所示的情況，這顯然違背了約束條件。

2）如果我們每次都選擇持續(xù)時間最短的活動，不能得到最優(yōu)解

證明（反證法）：

例如我們選擇了2號活動（開始時間3點，結(jié)束時間5點）；

1號活動待選擇（開始時間1點，結(jié)束時間4點）；

則會出現(xiàn)上圖所示的情況，這顯然也違背了約束條件。

3）如果我們每次都選取結(jié)束時間最早的活動，能夠得到最優(yōu)解（采用的貪心策略）

那么怎么證明貪心算法是對的呢？

要證明一個算法是錯的非常簡單，要證明是對的卻非常難。對于貪心算法的證明，一是使用歸納法，二是采用反證法。像上面兩種策略，我們實際上就用到了反證法。

回到策略本身，按這種方法選擇相容活動，能夠為未安排的活動留下盡可能多的時間。

第四步：選好策略，那我們就來按照貪心算法的基本思路總結(jié)一下

1. 數(shù)學模型是目標函數(shù)count（n）最大，約束條件是s[i]>=f[j]；
2. 求解哪個活動結(jié)束時間最早（本題目顯然是活動1）；
3. 求解哪個動開始時間s[i]大于上一個活動結(jié)束時間f[j]；
4. 把步驟三求出的活動依次取出，作為我們選取的活動

上代碼：

這段代碼的含義是：

1. 定義活動號n，活動開始時間、結(jié)束時間Type s[]，Type f[]，布爾邏輯判斷A[]；
2. 定義進入算法的活動序號，最終選取的活動序號i，j；
3. 初始活動i=1，由于1號活動結(jié)束時間，所以選取j=1。

從2號活動開始進入運算，具體運算規(guī)則：

• 判斷條件：活動開始時間（i）>上一個活動結(jié)束時間（j）
• A[]為true，j選中
• A[]為false，j不選擇
• i自增1位，繼續(xù)判斷，直至i=11

上圖直觀展示了算法的整個運行過程。

五、貪心算法應用

貪心算法應用非常廣泛，特別電腦游戲AI或者一些推薦。

以經(jīng)典的跳躍游戲為例：

1.題目描述

給定一個非負整數(shù)數(shù)組，你最初位于數(shù)組的第一個位置。

數(shù)組中的每個元素代表你在該位置可以跳躍的最大長度。

判斷是否能夠到達最后一個位置。

2.問題分析

先轉(zhuǎn)化為數(shù)學模型：給定一個數(shù)組，數(shù)組中每個位置的數(shù)字代表當前位置i能夠向前跳躍num[i]的距離，然后判斷是否能夠從第一個位置跳到最后一個位置。

這道題的難點就在于每次跳多遠的距離算合適呢？

如果從i的位置能跳num[i]距離最遠能到達j的位置，那么這中間的任何一個位置我們都能跳到，但我們具體是跳到i–j之間的哪個位置才是真正合適的位置？

利用貪心的思想我們的目的是判斷最后能否跳到最后一個位置，其實就是只要能保證在i–j之間跳到一個能夠在下一次跳的更遠的距離，那么這個位置就是最合適的位置。

本文由 @CARRIE 原創(chuàng)發(fā)布于人人都是產(chǎn)品經(jīng)理。未經(jīng)許可，禁止轉(zhuǎn)載

題圖來自Unsplash，基于CC0協(xié)議