近似算法及對(duì)某些標(biāo)準(zhǔn)問(wèn)題的適用性

食品配送：旅行商問(wèn)題的現(xiàn)實(shí)應(yīng)用。本文將介紹近似算法及其對(duì)某些標(biāo)準(zhǔn)問(wèn)題的適用性，以及哪些因素會(huì)影響到特定算法的選擇。什么是近似算法？近似算法是一種處理優(yōu)化問(wèn)題 NP 完全性的方式，它無(wú)法確保最優(yōu)解。近似算法的目標(biāo)是在多項(xiàng)式時(shí)間內(nèi)盡可能地接近最優(yōu)值。它雖然無(wú)法給出精確最優(yōu)解，但可以將問(wèn)題收斂到最終解的近似值。其目標(biāo)滿足以下三個(gè)關(guān)鍵特性：

能夠在多項(xiàng)式時(shí)間內(nèi)高效運(yùn)行；

能夠給出最優(yōu)解；

對(duì)于每個(gè)問(wèn)題實(shí)例均有效。

背景數(shù)學(xué)表達(dá)式的評(píng)估常伴隨常量、變量分析和方程的階，可用于衡量近似的復(fù)雜度。此類(lèi)評(píng)估將問(wèn)題分解為 P 和 NP 難問(wèn)題。P 問(wèn)題和 NP 問(wèn)題的策略P 問(wèn)題是指可以在多項(xiàng)式時(shí)間內(nèi)求解的問(wèn)題。NP 表示不確定性多項(xiàng)式時(shí)間（nondeterministic polynomial time），NP 問(wèn)題是指在多項(xiàng)式時(shí)間內(nèi)近似驗(yàn)證答案的問(wèn)題。但目前人們發(fā)現(xiàn)，很多此類(lèi)問(wèn)題需要指數(shù)時(shí)間才能求解。

P 和 NP 策略。真正的爭(zhēng)論在于 P=NP 還是 P≠NP。之前的一些研究證明這兩種都是對(duì)的。如果一個(gè)問(wèn)題是多項(xiàng)式次方，則存在多個(gè)最優(yōu)算法。因此，在 NP 完全問(wèn)題中，存在兩種方法找到近優(yōu)解，然后選擇最適合的算法。如果輸入的大小比較小，則具備指數(shù)運(yùn)行時(shí)間的算法可能會(huì)比較適合。其次，通過(guò)用近似算法替代確定性算法，我們?nèi)匀荒軌蛟诙囗?xiàng)式時(shí)間內(nèi)找到近優(yōu)解。近似算法的復(fù)雜度可以從輸入大小和近似因子中推斷出來(lái)。接下來(lái)，我們通過(guò)一些示例，深入探索這些算法如何應(yīng)用到現(xiàn)實(shí)問(wèn)題中。分區(qū)問(wèn)題（Partition Problem）在計(jì)算機(jī)科學(xué)領(lǐng)域，該問(wèn)題的定義是：給定多重正整數(shù)集 X，它可以被分割為兩個(gè)元素之和相等的子集 X1 和 X2，即每個(gè)子集的數(shù)值之和與另一個(gè)子集相等。

例如，X={3，4，1，3，3，2，3，2，1} 可以被分割為 X1={3，3，2，3} 和 X2={4，2，3，1，1}，二者的數(shù)值之和都是 11。類(lèi)似地，X={1，3，1，2，1，2} 可以被分成 X1={2，1，1，1} 和 X2={3，2}，兩個(gè)子集的數(shù)值之和都是 5。有趣的是，這不是唯一解。X1={1，3，1} 和 X2={2，1，2} 的數(shù)值之和也為 5，這表明存在多個(gè)可能的子集。這就是 NP 完全問(wèn)題，存在偽多項(xiàng)式時(shí)間動(dòng)態(tài)規(guī)劃解，可獲得該問(wèn)題的近優(yōu)解。方法和決定步驟現(xiàn)在，我們開(kāi)始分析這個(gè)問(wèn)題，把它分解成數(shù)個(gè)單獨(dú)的標(biāo)準(zhǔn)問(wèn)題。這里，我們想要找出多重集的元素之和相等的子集，那么該問(wèn)題就可以分解成以下兩個(gè)問(wèn)題：

子集和問(wèn)題：子集 X 的元素之和等于數(shù)字 W。

多路數(shù)字分割：給定整數(shù)參數(shù) W，確定如何將 X 分割成 W 個(gè)等額子集。

近似算法如上所述，將分區(qū)問(wèn)題分解為多路分割與子集和問(wèn)題后，我們就可以考慮為這些問(wèn)題而開(kāi)發(fā)的算法，包括：貪婪數(shù)字分割（Greedy number Partitioning）該算法循環(huán)遍歷所有數(shù)字，將每個(gè)數(shù)字分配給總和最小的子集。如果數(shù)字未以排序方式排列，則其運(yùn)行時(shí)復(fù)雜度為 O（n），近似率約為 3/2。其 Python 偽代碼如下：

def find_partition(numbers):    """Separate the available numbers into two eqal sum series.    Args:        numbers: collection of numbers, for example list of integers.    Returns:        Two lists of numbers.    """    X = []    Y = []    sum_X = 0    sum_Y = 0    for n in sorted(numbers, reverse=True):        if sum_X < sum_Y:           X.append(n)           sum_X = sum_X + n        else:           Y.append(n)           sum_Y = sum_Y + n    return (X, Y)

將數(shù)字排序，則運(yùn)行時(shí)復(fù)雜度增加到 O（n logn），近似率增加到 7/6。如果數(shù)字在 ［0，1］ 范圍內(nèi)均勻分布，則近似率約為 1 + O（log logn/n）。

分區(qū)問(wèn)題圖示。上圖用二叉樹(shù)的形式展示所有分區(qū)。樹(shù)的根部表示集合中的最大數(shù)，每一級(jí)對(duì)應(yīng)輸入數(shù)字，每個(gè)獨(dú)立分支對(duì)應(yīng)不同的子集。遍歷這些集合需要深度優(yōu)先遍歷（depth-first traversal），所需的空間復(fù)雜度為 O（n），時(shí)間復(fù)雜度為 O（2^n）。適用性：該算法可以根據(jù)情況進(jìn)行修改，以便改善運(yùn)行時(shí)復(fù)雜度。每一級(jí)的首要目標(biāo)是構(gòu)建一個(gè)分支，將當(dāng)前數(shù)字分配給總和最小的子集。首先通過(guò)貪婪數(shù)字分割找出總和，然后切換到優(yōu)化，得到全多項(xiàng)式時(shí)間近似解。Karmarkar-Karp 算法Karmarkar-Karp 算法指以降序方式排列數(shù)字的最大差分方法，該方法將差值替換掉原來(lái)的數(shù)字不斷放進(jìn)集合中。其 Java 偽代碼實(shí)現(xiàn)如下：

int karmarkarKarpPartition(int[] baseArr) {        // create max heap        PriorityQueue heap = new PriorityQueue(baseArr.length, REVERSE_INT_CMP);
    for (int value : baseArr) {                heap.add(value);        }
    while (heap.size() > 1) {        int val1 = heap.poll();            int val2 = heap.poll();            heap.add(val1 - val2);    }
    return heap.poll();}

該算法包含輸入集 S 和參數(shù) k。將 S 分割成 k 個(gè)子集，使這些子集中的數(shù)字總和相等，從而構(gòu)建期望輸出。該算法包含如下關(guān)鍵步驟：

以降序方式排列數(shù)字；

用差值替換掉原來(lái)的數(shù)字，直到只有一個(gè)數(shù)字；

采用回溯算法，完成分區(qū)。

適用性：該算法通過(guò)構(gòu)建二叉樹(shù)來(lái)假設(shè)分區(qū)。每一級(jí)表示一對(duì)數(shù)字，左側(cè)的分支表示用差值替換數(shù)字，右側(cè)的分支表示將差值放置在同一個(gè)子集中。該算法先通過(guò)最大差分求得解，然后繼續(xù)尋找更好的近似解。它所需的空間復(fù)雜度為 O（n），但最糟糕的情況下所需的時(shí)間復(fù)雜度可能會(huì)達(dá)到 O（2^n）。裝箱問(wèn)題裝箱問(wèn)題有多種現(xiàn)實(shí)應(yīng)用。例如，如何從根本上改善印度的垃圾管理系統(tǒng)。這個(gè)問(wèn)題就可以通過(guò)裝箱問(wèn)題來(lái)解決，幫助當(dāng)局決定 x 量的垃圾需要多少個(gè)垃圾箱。

在計(jì)算機(jī)科學(xué)領(lǐng)域中，該問(wèn)題可用于多種內(nèi)存管理技術(shù)。在該算法中，我們可以通過(guò)去除冗余和最小化空間浪費(fèi)來(lái)包裝不同形狀和大小的對(duì)象。例如：給定一個(gè)包含 n 個(gè)項(xiàng)的集合，每個(gè)項(xiàng)的大小分別為 s1，s2，。.，sn （0《=si《=1， 1《=i《=n），如何將它們裝進(jìn)最少數(shù)量的箱子？經(jīng)典方法：1. 鄰近適應(yīng)算法 （Next Fit）：查看當(dāng)前項(xiàng)是否適合當(dāng)前箱子。如果適合，則將物品放置在箱子里，否則開(kāi)啟一個(gè)新的箱子。我們來(lái)看一個(gè)示例：項(xiàng)是 0.5， 0.7， 0.5， 0.2， 0.4， 0.2， 0.5， 0.1， 0.6，箱子大小均為 1。

基于鄰近適應(yīng)算法的裝箱解決方案（M = 箱子總數(shù) = 6）。2. 最先匹配法 （First Fit）：按順序?yàn)g覽箱子，在第一個(gè)箱中放置新的項(xiàng)，直到放不下再啟用新的箱子。我們來(lái)看一個(gè)示例：項(xiàng)是 0.5， 0.7， 0.5， 0.2， 0.4， 0.2， 0.5， 0.1， 0.6，箱子的大小均為 1。

基于最先匹配法的裝箱解決方案（M = 箱子總數(shù) = 5）。3. 最優(yōu)匹配法 （Best Fit）：按順序?yàn)g覽箱子，將每一個(gè)新的項(xiàng)放在最適合的箱子里。如果不適合，則創(chuàng)建一個(gè)新的箱子。我們來(lái)看一個(gè)示例：項(xiàng)是 0.5， 0.7， 0.5， 0.2， 0.4， 0.2， 0.5， 0.1， 0.6，箱子的大小均為 1。

基于最優(yōu)匹配法的裝箱解決方案（M = 箱子總數(shù) = 5）。該方法的輸出與最先匹配法相同，但該方法的優(yōu)點(diǎn)是實(shí)現(xiàn)速度比 FFD 快，即時(shí)間復(fù)雜度為 O（nlogn）。自然方法：如果我們提前知道所有項(xiàng)的大小，那么自然的解決方案就是首先按照從大到小排序，然后應(yīng)用以下啟發(fā)式方法：

最先匹配遞減法

最優(yōu)匹配遞減法

假設(shè)有相同的示例 0.7， 0.6， 0.5， 0.5， 0.5， 0.4， 0.2， 0.2， 0.1，則排序?yàn)?0.7， 0.6， 0.5， 0.5， 0.5， 0.4， 0.2， 0.2， 0.1。

優(yōu)化方法（M = 箱子總數(shù) = 4）。

審核編輯：郭婷