4.2　理解算法策略

一個精心設(shè)計的算法盡可能地將問題劃分為更小的子問題，從而最大限度地優(yōu)化可用資源的使用。設(shè)計算法有不同的算法策略，算法策略包含下面列出的三種典型策略，還有些策略沒有列入進來。

這里，我們介紹以下三種策略：

• 分治策略
• 動態(tài)規(guī)劃策略
• 貪心算法策略

4.2.1　分治策略

分治策略就是找到一種方法，將規(guī)模較大的問題分解成可以相互獨立解決的規(guī)模較小的子問題，然后將這些子問題產(chǎn)生的解合并起來，生成問題整體的解，這就是所謂的分治策略。

從數(shù)學(xué)上講，如果問題（P）有n個輸入且需要對數(shù)據(jù)集d進行處理，則用分治策略為問題設(shè)計求解方案會將問題分解成k個子問題，記為P1至Pk，每個子問題將處理數(shù)據(jù)集d的一個分區(qū)。通常，假設(shè)P1至Pk依次處理數(shù)據(jù)分區(qū)d1至dk。

我們看一個實例。

實例——適用于Apache Spark的分治策略

Apache Spark是一個用于解決復(fù)雜分布式問題的開源框架，它使用了分治策略來解決問題。為了處理問題，它將問題分為多個子問題，并且彼此獨立地處理。我們將通過從一個列表中計數(shù)單詞的簡單的例子來說明這一點。

假設(shè)我們有以下單詞列表：

我們要計算此列表中每個單詞出現(xiàn)的頻率。為此，我們將采用分治策略來有效解決此問題。

圖4-3展示了分治策略的實現(xiàn)流程。

在圖4-3中，我們將一個問題劃分為以下幾個階段：

• 分割（splitting）：在這個階段中，輸入數(shù)據(jù)被分為可以相互獨立處理的分區(qū)，這稱為分割。圖4-3中我們有三個分區(qū)。
• 變換（Mapping）：可以在分區(qū)上獨立運行的任何操作都稱為變換。在圖4-3中，變換操作將分區(qū)中的每個單詞轉(zhuǎn)換為鍵值對，對應(yīng)于三個分區(qū)，有三個并行運行的變換器。
• 混合（shuffling）：混合是將相似的鍵組合在一起的過程。一旦相似的鍵聚集在一起，聚合函數(shù)就可以在它們的值上運行。請注意，混合是性能密集型的操作，因為需要將原本分布在網(wǎng)絡(luò)各處的相似鍵聚集在一起。
• 聚合（reducing）：在相似鍵的值上運行一個聚合函數(shù)的操作叫作聚合。在圖4-3中，我們要計算每個單詞的個數(shù)。

我們看看如何通過編寫代碼來實現(xiàn)此目的。為了演示分治策略，我們需要使用一個分布式的計算框架。為此，我們將在Apache Spark上運行Python：

1. 首先，為了使用Apache Spark，我們創(chuàng)建一個Apache Spark的運行環(huán)境：

2. 現(xiàn)在，我們創(chuàng)建一個包含一些單詞的示例列表。我們將把這個列表轉(zhuǎn)換成Spark的本地分布式數(shù)據(jù)結(jié)構(gòu)，稱為彈性分布式數(shù)據(jù)集（Resilient Distributed Dataset，RDD）：

3. 現(xiàn)在，我們使用map函數(shù)將單詞轉(zhuǎn)換為鍵值對（如圖4-4所示）。

4. 我們使用reduce函數(shù)進行聚合，并獲得最終結(jié)果（如圖4-5所示）。

這演示了我們是如何使用分治策略來計算單詞出現(xiàn)次數(shù)的。

4.2.2　動態(tài)規(guī)劃策略

動態(tài)規(guī)劃是由理查德·貝爾曼（Richard Bellman）在20世紀50年代提出的一種用于優(yōu)化某類算法的策略。它基于智能緩存機制，嘗試重用大量計算，這種智能緩存機制稱為記憶。

當我們要解決的問題可以拆分為若干子問題時，動態(tài)規(guī)劃可帶來良好的性能優(yōu)勢。子問題部分涉及了一些會在不同的子問題中重復(fù)的計算，我們的想法是執(zhí)行一次計算（這是耗時的步驟），然后在其他子問題上重復(fù)使用計算結(jié)果。這在解決遞歸問題時尤其有用，因為這些問題可能會多次計算相同的輸入。

4.2.3　貪心算法

在深入展開討論之前，我們先定義兩個術(shù)語：

• 算法開銷：在我們嘗試找出確定型問題的最優(yōu)解時，都要花費一些時間。隨著我們要求解的優(yōu)化問題變得越來越復(fù)雜，找出最優(yōu)解所花費的時間也會增加。我們用Ωi表示算法開銷。
• 最優(yōu)解增量：給定的優(yōu)化問題都存在一個最優(yōu)解。在通常情況下，我們用自己選擇的算法對解迭代地進行優(yōu)化。對于給定的問題，總是存在當前問題的一個完美解，稱為最優(yōu)解。如前所述，根據(jù)待求解問題的類型，最優(yōu)解有可能是未知的，或者說計算和驗證最優(yōu)解需要花費的時間長到人們無法接受。假設(shè)最優(yōu)解是已知的，那么在第i輪迭代中，當前解與最優(yōu)解的差稱為最優(yōu)解增量，用?i表示。

對于復(fù)雜問題，我們有兩種可行的策略：

• 策略1：花更多時間尋找最接近最優(yōu)解的解，使得?i盡可能小。
• 策略2：最小化算法開銷Ωi，采用快刀斬亂麻的方法，只需使用可行解即可。

貪心算法基于策略2，它并不致力于找出全局最優(yōu)解，而是選擇最小化算法開銷。

采用貪心算法是為多階段問題找出全局最優(yōu)解的一種快速簡單的策略。它基于選擇局部最優(yōu)值而無須費力去驗證局部最優(yōu)值是否也是全局最優(yōu)的。一般來說，除非我們很幸運，否則貪心算法找到的解不會被當作全局最優(yōu)解，因為尋找全局最優(yōu)解通常是一項非常耗時的任務(wù)。因此，與分治算法和動態(tài)規(guī)劃算法相比，貪心算法的速度很快。

通常，貪心算法定義如下：

1. 假設(shè)我們有一個數(shù)據(jù)集D。在這個數(shù)據(jù)集中，選擇一個元素k。

2. 假設(shè)當前的候選解或可行解為S。考慮在S中包含k，如果可以將它包括進來，則將當前解更新為Union(S, k)。

3. 重復(fù)上述過程，直到S被填滿或D被用完為止。