遇事不決,動態規劃

語言: CN / TW / HK

theme: orange

遇事不決,動態規劃

曾幾何時,遇事不決,暴力破解,最小的心智負擔快速解決問題,是大多數人優先考慮的解法。

但是作為一名優秀的青年,手撕演算法,腳踩資料結構,最低的演算法複雜度、最快的執行速度,解決最難的問題,才是優雅得體的。

在這樣巨集偉的願景之下,我對部分演算法進行了學習,發現相對傳統的暴力破解,動態規劃也是一種更貼合我們邏輯思維的解法。

接下來,就來了解一下什麼是動態規劃吧!

全文分為三個部分

  • 理論基礎 - 介紹動態規劃的基礎定義
  • 例項演示 - 通過經典的爬樓梯、揹包問題進一步掌握動態規劃的思想
  • git diff 演算法 - 瞭解動態規劃在實際場景中的運用 - 程式碼 diff 工具

理論基礎

什麼是動態規劃?

動態規劃(英語:Dynamic programming,簡稱DP)是一種在數學、管理科學、電腦科學、經濟學和生物資訊學中使用的,通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。

我們把問題分解為多個階段,每個階段對應一個決策。我們記錄每一個階段可達的狀態集合(去掉重複的),然後通過當前階段的狀態集合,來推導下一個階段的狀態集合,動態地往前推進。

簡單來說,就是將一個大問題分解成若干子問題,通過解決子問題,然後一步一步推導找到問題最終解的一個過程

大致就如下圖所示: image.png

怎麼樣,是不是非常簡單(開個玩笑,開個玩笑。

其實大部分動態規劃能解決的問題,都可以通過暴力列舉來解決,回溯演算法的思想就源於暴力列舉,當滿足情況就停止遍歷(剪枝)。不過回溯演算法的複雜度是呈指數級增長,動態規劃卻可以有效地降低時間複雜度。

我們常常使用動態規劃來解決:最優解問題,比如求最大值、最小值等等

動態規劃具有“一個模型三個特徵”

image-20220422234525764.png

一個模型

  • 多階段決策最優解模型

三個特徵

  • 最優子結構:問題的最優解包含子問題的最優解

  • 無後效性:

    在推到後面階段的狀態的時候,我們只關心前面階段的狀態值,不關心這個狀態是怎麼一步步推匯出來的

    某階段狀態一旦確定,就不受之後階段的決策影響

  • 重複子問題:不同的決策序列,到達某個相同階段時,可能會產生重複的狀態

啥模型?啥特徵?是不是有點難理解,我們可以結合以下的例項來剖析它們的含義。

例項演示

爬樓梯

假設你正在爬樓梯。需要 n 階你才能到達樓頂。

每次你可以爬 12 個臺階。你有多少種不同的方法可以爬到樓頂呢?

還記得之前說過動態規劃可以看做是通過解決子問題,獲取遞推規律,從而達到解決最終問題的過程嗎?

就和做測智商題的解法一致:找規律

首先我們嘗試一下正向找規律

  • 當 n = 1 時,我們有 1 種方法可以到達樓頂:

    • 1 階
  • 當 n = 2 時,我們有 2 種方法可以到達樓頂:

    • 1 階 + 1 階
    • 2 階
  • 當 n = 3 時,我們有 3 種方法可以到達樓頂:

    • 1 階 + 1 階 + 1 階
    • 1 階 + 2 階
    • 2階 + 1階
  • 。。。。

依次類推可以得到臺階數和方法數的關係:

| 臺階高度 | 方法總數 | | ---- | ---- | | 1 | 1 | | 2 | 2 | | 3 | 3 | | 4 | 5 | | 5 | 8 | | 6 | 13 | | 7 | 21 | | 8 | 34 | | ... | ... |

聰明的你應該已經發現規律了:從第 3 階開始,當前臺階方法總數的值不就等於前兩個值的和嘛。

3 = 2 + 1,5 = 3 + 2,8 = 5 + 3 ...

f(n)當做上第n個臺階的方法總數,那麼就是

f(n) = f(n - 1) + f(n - 2)

如果是根據反向找規律的思維來推導的話就是:

每次可以爬 1 或 2 個臺階,就是說爬上第 n 個臺階,一定是從第 n - 1 或者 n - 2個臺階上去的,那麼爬上第 n 個臺階的方法總數就是爬到第 n - 1 個臺階的方法總數與爬到第 n - 2 個臺階的方法總數之和。

使用程式碼的方式來解決就是這樣:

const climbStairs = (n) => {    // f[i] 為第 i 階樓梯有多少種方法爬到樓頂    const f = new Array(n + 1).fill()    // 記錄初始值,0 階臺階 0 種, 1 階臺階 1 種,2 階臺階 2 種    f[0] = 0    f[1] = 1    f[2] = 2    // 從第 3 階開始,當前臺階方法總數的值等於前兩個值的和    for(let i = 3; i <= n; i++) {        f[i] = f[i - 1] + f[i - 2]   }    // 返回抵達當前臺階的方法數    return f[n] };

到這裡可以發現兩個關鍵點:

  • f(n)的獲取完全依賴於f(n - 1)f(n - 2),也就是最終結果的獲取依賴於子結果,對應最優子結構特徵
  • f(n)的獲取只關心f(n - 1)f(n - 2)的值,而並不關心f(n - 1)f(n - 2)值是如何推匯出來的,對應無後效性特徵

接下來,我們通過經典的揹包問題來深入瞭解下這種演算法

揹包問題

假設你有一個可以裝 4 kg 東西的揹包

商店裡有如下三件物品(所有物品大小形狀都看作一致,僅重量不同)

怎樣選擇,能讓裝進揹包的物品價值最大?

image-20220419222232455.png

遇事不決,我們就。。把所有情況列出來:

image-20220416231920937.png

可以很清晰的看到,選擇平板 + 膝上型電腦是在有限容量(4kg)下價值最大的(3500元)選擇。

這樣雖然可行,但是不優雅,在有 3 個商品的時候,我麼需要計算 8 種組合,在有 4 件商品的時候,我們要計算 16 種組合,當有 n 件商品就需要就計算 2 ^ n 種組合,眾所周知,指數級複雜度的演算法,優秀青年不到萬不得已絕對不會使用。

這時候,就輪到我們的標題登場了:遇事不決,動態規劃

按照之前介紹過的動態規劃的理念(通過解決小問題來推匯出大問題的答案),來具體分析一下:

  • 4 kg 的揹包,裝 3 種不同價值和重量的物品,如何使裝的物品價值總和最大

  • 可以將大的數值(4kg、3種)拆解成小數值:

    • 1kg 的揹包裝 1 種物品能獲取最大價值的方法;
    • 1kg 的揹包裝 2 種物品能獲取最大價值的方法;
    • 1kg 的揹包裝 3 種物品能獲取最大價值的方法;
    • 2kg 的揹包裝 1 種物品能獲取最大價值的方法;
    • 。。。

文字描述不太直觀,轉換成表格的形式:

| | 1kg揹包 | 2kg揹包 | 3kg揹包 | 4kg揹包 | | ------------ | --------------- | ------------------- | ---------------- | --------------- | | 平板/1kg/1500 | 1kg揹包裝平板 | 2kg揹包裝平板 | 2kg揹包裝平板 | 2kg揹包裝平板 | | 音響/4kg/3000 | 1kg揹包裝平板和音響 | 2kg揹包裝平板和音響 | 3kg揹包裝平板和音響 | 4kg揹包裝平板和音響 | | 筆記本/3kg/2000 | 1kg揹包裝平板、音響和筆記本 | 2kg揹包裝平板、筆記本和音響和筆記本 | 3kg揹包裝平板、和音響和筆記本 | 4kg揹包裝平板、音響和筆記本 |

這樣一張表格就可以看作上文提到的多階段決策最優解模型

然後我們再依次分析,每一格能裝的最大價值物品,比如平板這一行:

  • 【1kg 揹包裝平板】:平板剛好 1kg 可以裝下,所以最大價值為1500
  • 【2kg 揹包裝平板】:平板 1kg 可以裝下,所以最大價值為1500
  • 【3kg 揹包裝平板】:平板 1kg 可以裝下,所以最大價值為1500
  • 【4kg 揹包裝平板】:平板 1kg 可以裝下,所以最大價值為1500

| | 1kg揹包 | 2kg揹包 | 3kg揹包 | 4kg揹包 | | ------------ | ----- | ----- | ----- | ----- | | 平板/1kg/1500 | 1500 | 1500 | 1500 | 1500 | | 音響/4kg/3000 | | | | | | 筆記本/3kg/3000 | | | | |

我們目前在【4kg 揹包裝平板】獲得的最大價值是1500 元

那麼到了音響這一行:

  • 【1kg 揹包裝平板和音響】:只裝得下 1kg 的平板,最大價值為1500
  • 【2kg 揹包裝平板和音響】:只裝得下 1kg 的平板,最大價值為1500
  • 【3kg 揹包裝平板和音響】:只裝得下 1kg 的平板,最大價值為1500
  • 【4kg 揹包裝平板和音響】:只裝平板,價值為1500;只裝音響,價值為3000;因此最大價值為3000

| | 1kg揹包 | 2kg揹包 | 3kg揹包 | 4kg揹包 | | ------------ | ----- | ----- | ----- | -------- | | 平板/1kg/1500 | 1500 | 1500 | 1500 | 1500 | | 音響/4kg/3000 | 1500 | 1500 | 1500 | 3000 | | 筆記本/3kg/3000 | | | | |

可以看到,【4kg 揹包】中更新了最大價值為3000元

接著往下看筆記本這一行

  • 【1kg 揹包裝平板、音響和筆記本】:只裝得下 1kg 的平板,最大價值為1500
  • 【2kg 揹包裝平板、音響和筆記本】:只裝得下 1kg 的平板,最大價值為1500
  • 【3kg 揹包裝平板、音響和筆記本】:只裝 1kg 的平板,價值為1500;只裝 3kg 的筆記本,價值為2000,所以最大價值為2000

這樣【3kg】揹包的最大價值更新為了2000元:

| | 1kg揹包 | 2kg揹包 | 3kg揹包 | 4kg揹包 | | ------------ | ----- | ----- | -------- | ----- | | 平板/1kg/1500 | 1500 | 1500 | 1500 | 1500 | | 音響/4kg/3000 | 1500 | 1500 | 1500 | 3000 | | 筆記本/3kg/2000 | 1500 | 1500 | 2000 | |

最後的【4kg 揹包裝平板、音響和筆記本】中,就只剩兩種情況了:

image-20220419223036097.png

【4kg音響的價值】 vs 【3kg筆記本的價值】 + 【1kg平板的價值】

顯然【3kg音響的價值】 + 【1kg平板的價值】略勝一籌,奪得桂冠

最終得出:同時裝下平板和筆記本,最大價值為3500,如下表格所示

| | 1kg揹包 | 2kg揹包 | 3kg揹包 | 4kg揹包 | | ------------ | ------- | ------- | ------- | --------- | | 平板/1kg/1500 | 1500(平) | 1500(平) | 1500(平) | 1500(平) | | 音響/4kg/3000 | 1500(平) | 1500(平) | 1500(平) | 3000(音) | | 筆記本/3kg/2000 | 1500(平) | 1500(平) | 2000(筆) | 3500(平+筆) |

可能有人會表示疑惑:這和我用窮舉法不能說完全相似,只能說一模一樣?甚至步驟看起來還更多了??

當然不是!

我們可以看到在推導【4kg 揹包裝平板、音響和筆記本】最大價值的時候,我們只做了一個比較:

【4kg音響的價值】 vs 【3kg筆記本的價值】 + 【1kg平板的價值】

也就是

【當前的最大價值】 vs 【當前商品的價值】 + 【剩餘空間的最大價值】

當【當前的最大價值】沒有被更新的時候,就對應了我們上面提的"三個特徵"中的重複子問題特徵:不同的決策序列,到達某個相同階段時,可能會產生重複的狀態

每一步的最大價值的計算都只依賴於這兩個數值的比較

1d7b5ade16f5405d8190c86dfda36a5a.jpg

不信的話,我們再增加一個商品試試:

image-20220419224701594.png

表格同樣再來一行

| | 1kg揹包 | 2kg揹包 | 3kg揹包 | 4kg揹包 | | ------------ | ------- | ------- | ------- | --------- | | 平板/1kg/1500 | 1500(平) | 1500(平) | 1500(平) | 1500(平) | | 音響/4kg/3000 | 1500(平) | 1500(平) | 1500(平) | 3000(音) | | 筆記本/3kg/2000 | 1500(平) | 1500(平) | 2000(筆) | 3500(平+筆) | | 手機/1kg/2000 | | | | |

  • 【1kg 揹包裝平板、音響、筆記本和手機】:1500(平) vs 1kg 手機,手機獲勝,最大價值更新為2000

    | | 1kg揹包 | 2kg揹包 | 3kg揹包 | 4kg揹包 | | ------------ | ------- | ------- | ------- | --------- | | 平板/1kg/1500 | 1500(平) | 1500(平) | 1500(平) | 1500(平) | | 音響/4kg/3000 | 1500(平) | 1500(平) | 1500(平) | 3000(音) | | 筆記本/3kg/2000 | 1500(平) | 1500(平) | 2000(筆) | 3500(平+筆) | | 手機/1kg/2000 | 2000(手) | | | |

  • 【2kg 揹包裝平板、音響、筆記本和手機】: 當前(2kg揹包)最大價值 1500(平) vs 當前物品價值 2000(手) + 1 kg揹包最大價值(1500平),後者獲勝,為3500元

    image-20220419232336251.png

    | | 1kg揹包 | 2kg揹包 | 3kg揹包 | 4kg揹包 | | ------------ | ------- | --------- | ------- | --------- | | 平板/1kg/1500 | 1500(平) | 1500(平) | 1500(平) | 1500(平) | | 音響/4kg/3000 | 1500(平) | 1500(平) | 1500(平) | 3000(音) | | 筆記本/3kg/2000 | 1500(平) | 1500(平) | 2000(筆) | 3500(平+筆) | | 手機/1kg/2000 | 2000(手) | 3500(手+平) | | |

  • 【3kg 揹包裝平板、音響、筆記本和手機】:當前(3kg揹包)最大價值2000(筆) vs 當前物品價值 2000(手) + 剩餘 2kg揹包最大價值1500(平),後者獲勝,為3500元

    image-20220419232236986.png

    | | 1kg揹包 | 2kg揹包 | 3kg揹包 | 4kg揹包 | | ------------ | ------- | --------- | --------- | --------- | | 平板/1kg/1500 | 1500(平) | 1500(平) | 1500(平) | 1500(平) | | 音響/4kg/3000 | 1500(平) | 1500(平) | 1500(平) | 3000(音) | | 筆記本/3kg/2000 | 1500(平) | 1500(平) | 2000(筆) | 3500(平+筆) | | 手機/1kg/2000 | 2000(手) | 3500(手+平) | 3500(手+平) | |

  • 【4kg 揹包裝平板、音響、筆記本和手機】:最後一個想必你也會了,只需比較

    image-20220419232113896.png

    可以得出最大值為 2000(手) + 2000(筆),最大值更新為 4000 元

    | | 1kg揹包 | 2kg揹包 | 3kg揹包 | 4kg揹包 | | ------------ | ------- | --------- | --------- | --------- | | 平板/1kg/1500 | 1500(平) | 1500(平) | 1500(平) | 1500(平) | | 音響/4kg/3000 | 1500(平) | 1500(平) | 1500(平) | 3000(音) | | 筆記本/3kg/2000 | 1500(平) | 1500(平) | 2000(筆) | 3500(平+筆) | | 手機/1kg/2000 | 2000(手) | 3500(手+平) | 3500(手+平) | 4000(手+筆) |

如果將表格看作是一個二維陣列packagei表示行,j表示列,package[i][j]表示當前格的最大價值的話,我們可以得出:

image-20220419233637501.png

此時,增加一個商品,我們只增加了 4 個步驟就求出了最大價值,也就是說,如果我們使用這種方法求解最大價值,只需要【揹包重量 * 物品數】步就可以得到結果,複雜度為O(n ^ 2),而使用窮舉法,每增加一件物品,步驟數卻會呈指數增長(2^4, 2^5, 2^6.......),即複雜度為O(2 ^ n)。

計算機對所有結果的處理過程其實就是一一窮舉,而我們通過演算法實現的程式碼,可以大大減少這個窮舉的過程,因此在實際表現上就是“執行速度更快了,結果出現的更快了”。複雜度的降低意味著執行效率的提升。動態規劃較之盲目的窮舉帶來的好處就在於此。

總結

由以上的示例,我們可以得出

  • 動態規劃可以幫助你在給定約束條件下找到最優解。在揹包問題中,你必須在揹包容量給定的情況下,獲取價值總和最高的物品
  • 在問題可分解為彼此獨立且離散的子問題時,就可使用動態規劃來解決。在揹包問題中,我們是有一個大前提的:所有物品的形狀等其他因素視為一致。如果不一致,就不適合使用動態規劃了。

學習演算法不光是為了能夠刷題,更重要的是培養我們對複雜場景的多維思考能力。

git diff 演算法

最後,就到了我寫這篇文章的最初的打算了。恭喜還能讀到這裡的朋友,你將會增加一些其他人不知道的知識。

20200917110440_58017.gif

演算法思路

我們經常使用的 git 或者 IDE 中都有程式碼對比的能力,如下所示:

image-20220416160143851.png

程式碼差異化對比是被版本控制系統用來確認程式碼做了哪些更改。那麼要如何實現對程式碼的差異性對比的功能呢?

比如說,有一個字串

a = 'ABCABBA'

當對它做出了部分更改,並提交:

a = 'CBABAC'

如何判斷這次更改的差異呢?

首先最簡單的方法就是直接做全量替換

image-20220423120320178.png

全刪了重新來過,最低的心智負擔創造最大的價值,好!

image-20220430144651699.png

顯而易見,如果你在 git 上檢視提交記錄返回這樣的結果,怕不是會直接刪庫跑路。那麼如何讓 diff 結果更加直觀詳細呢?

一般思路就是,相同的元素保留,只增/刪不同的元素

image-20220423134446785.png

這種對比方式就很直觀地體現出做出了哪些更改,當然,這種列舉方式不止一種,我們還可以有多種的實現方式:

image-20220423141841319.png

可以看到,這四種方式的操作步驟都是隻有五步,都屬於步驟數最優解的範疇。

差異演算法的目的是提供一種產生差異的策略,其中差異具有某些理想的性質。我們通常希望差異儘可能小,但也需要其他考慮。

比如是先刪除後增加,還是先增加後刪除,還是一邊加一邊減?

所以 diff 演算法不僅僅是需要找出兩份程式碼的不同之處,還需要考慮增減的順序帶來的可閱讀性

一般而言,先統一進行刪除操作,再進行新增操作是比較好的方式:

image-20220423151530209.png

你們也可以開啟 gitlab / github / gitee 觀察程式碼對比部分,都是使用的【先刪除差異部分,再新增】的策略,這樣樣能保證最佳的閱讀感。

不止如此,還有對程式碼結構特徵的考量。

例如,如果想要插入一個方法,該方法的結束應該被認為是新的,而不是保留前面方法的結束:

好:   class Smart                 差:    class Smart          def initName(name)                def initName(name)            name = 'jason'                      name = 'jason'            return                        +     return      +                                   +      +   def initage(age)                +   def initage(age)      +     age = 18                      +     age = 18      +     return                              return

注:此處運用了貪心演算法

綜上,一個優秀的直觀的 diff 演算法需要滿足:

  1. 先刪除,後增加
  2. 整塊刪除後新增,而不是刪除新增交叉
  3. 新增和刪除的邏輯結構一致

圖搜尋

Myers 演算法就是這樣,不但能快速定位到差異化的內容,還考慮了最直觀的閱讀性。當然,Myers 演算法核心就是本文的主角:動態規劃。

Myers 演算法將尋找 diff 的過程抽象成了圖搜尋。

A     B     C     A     B     B     A ​   o-----o-----o-----o-----o-----o-----o-----o   0   |     |     | \   |     |     |     |     | C   |     |     | \ |     |     |     |     |   |     |     |   \ |     |     |     |     |   o-----o-----o-----o-----o-----o-----o-----o   1 向右:增加   |     | \   |     |     | \   | \   |     | B   |     | \ |     |     | \ | \ |     | 向下:刪除   |     |   \ |     |     |   \ |   \ |     |   o-----o-----o-----o-----o-----o-----o-----o   2 對角線:保留原內容不變   | \   |     |     | \   |     |     | \   | A   | \ |     |     | \ |     |     | \ |   |   \ |     |     |   \ |     |     |   \ |   o-----o-----o-----o-----o-----o-----o-----o   3   |     | \   |     |     | \   | \   |     | B   |     | \ |     |     | \ | \ |     |   |     |   \ |     |     |   \ |   \ |     |   o-----o-----o-----o-----o-----o-----o-----o   4   | \   |     |     | \   |     |     | \   | A   | \ |     |     | \ |     |     | \ |   |   \ |     |     |   \ |     |     |   \ |   o-----o-----o-----o-----o-----o-----o-----o   5   |     |     | \   |     |     |     |     | C   |     |     | \ |     |     |     |     |   |     |     |   \ |     |     |     |     |   o-----o-----o-----o-----o-----o-----o-----o   6 ​   0     1     2     3     4     5     6     7

向右表示“刪除”,向下表示“新增”,對角線表示“保留原內容不變”。

圖中每一條從左上角(0, 0)到右下角的(7, 6)的路徑都可以視為一次 diff 過程。

比如我選擇最外層的路線:

image-20220427221831837.png 這條就是人腦思維最快解:

from ABCABBA DO 一路向右:-A -B -C -A -B -B -A 一路向下:+C +B +A +B +A +C RESULT CBABAC

那麼 Myers 演算法如何做到在萬千條道路中找到最快最優雅的那條呢?容我慢慢道來

第一步

首先,我們從(0, 0)開始出發

0,0

此時有兩個選擇,可以向右到達(1,0)和向下到達(0,1),也就是

0,0 --- 1,0 | | 0,1

第二步

接著分析第二步,先考慮從(0,1)出發,也有向下、向右兩種情況:

  1. 向下移動到達(0,2),但是(0,2)到達(1,3),(1,3)到達(2,4)都是對角線,對角線的移動意味著保留元素不變,既不需要刪除,也不需要新增元素,所以我們可以將(0,1)到達(2,4)標記為一步完成。 image-20220430153555386.png

  2. 向右移動到達(1,1),這裡也有一條對角線可以快速從(1,1)到達(2,2) image-20220430153827281.png

我們標記如下:

0,0 --- 1,0 | | 0,1 --- 2,2 | | 2,4

接著再判斷另一個分支(0,0) -> (1,0)之後的移動步驟:

  1. 從(1,0)向右移動到(2,0)後,通過對角線直達(3,1) image-20220430190556339.png

  2. 從(1,0)向下移動到(1,1)後,可以通過對角線直達(2,2) image-20220430183005196.png

細心的小夥伴應該發現了,之前通過(0,1)也是兩步直達(2,2),那麼哪種路徑是我們需要的呢?

image-20220430185122467.png

還記得一個優秀的直觀的 diff 演算法需要滿足的條件嗎?先刪除後增加(向右是刪除,向下是增加)

而我們通過(1,0)到達(2,2)正是先向右後向下即先刪除後增加,比通過(0,1)的先增加後刪除是一種更好的解。

image-20220430190413198.png

因此,目前移動的步驟標記變更如下,記住,我們只保留每一步的最佳結果:

0,0 --- 1,0 --- 3,1 |       | |       | 0,1     2,2 | | 2,4

第三步

接下來,就到了比較關鍵的第三步了。第三步的起始位置有三個,分別是(2,4),(2,2)和(3,1)

image-20220501190904183.png

  • 從(2,4)可以到達(3,6)和(4,5)兩個位置
  • 從(2,2)可以到達(2,3)和(5,4)兩個位置
  • 從(3,1)可以到達(5,2)和(5,4)兩個位置

可以看到,從(2,2)和(3,1)都能一步到達(5,4),根據我們在上面定義的結論:整塊刪除後新增,而不是刪除新增交叉。通過(2,2)到達(5,4)經歷了刪增刪,通過(3,1)到達(5,4)經歷了刪刪增,所以(3,1)要優於(2,2)

image-20220502135807695.png

同樣思路,先進行兩次插入,然後再進行一次刪除(向下兩次,然後向右),得到(4,5);而先進行刪除,然後再進行兩次插入,得到(2,3)。因此,我們將保留(4,5)結果,並丟棄(2,3),表明(4,5)是在一次刪除和兩次插入之後以任何順序可到達的最佳位置。

第三步完整記錄如下:

0,0 --- 1,0 --- 3,1 --- 5,2 |       |       | |       |       | 0,1     2,2     5,4 | | 2,4 --- 4,5 | | 3,6

到現在為止,你應該發現竅門了,我們就不再一步步推導了,最終可以得到如下最佳移動軌跡:

0,0 --- 1,0 --- 3,1 --- 5,2 --- 7,3 |       |       | |       |       | 0,1     2,2     5,4 --- 7,5 |               |       | |               |       | 2,4 --- 4,5     5,5     7,6 |       |       | |       |       | 3,6     4,6     5,6

因此(0,0) => (1,0) => (3,1) => (5,4) => (7.5) => (7,6)就是兩個字串之間 diff 的最佳路徑,也就是

image-20220423134446785.png

核心原理

我們已經瞭解了圖搜尋是如何進行的,那麼 Myers 演算法是如何實現的呢?

首先,將上面的移動軌跡旋轉45度後渲染:

k\d|     0     1     2     3     4     5 ----+--------------------------------------   | 4 |                             7,3   |                           / 3 |                       5,2   |                     / 2 |                 3,1         7,5   |               /     \     /     \ 1 |           1,0         5,4         7,6   |         /     \           \ 0 |     0,0         2,2         5,5   |         \                       \ -1 |           0,1         4,5         5,6   |               \     /     \ -2 |                 2,4         4,6   |                     \ -3 |                       3,6

橫軸上的數字 d 表示我們在圖中所到達的深度,即走了多少步;

縱軸上的數字 k 表示每一步座標(x,y)的差值 x - y

向右移動一步 x 加 1,所以 k 也增加 1;向下移動一步 y 加 1,同樣的 k 就會減少 1;沿對角線移動,x 和 y 都是增加相同的值,因此它倆的差值 k 保持不變。

我們記錄的是每一步的 k 值能到達的最遠的距離。

從圖中我們可以發現,除了原始座標(0,0)外,所有節點要麼是從左上角的節點過來(向下移動),要麼是從左下角的節點過來(向右移動)。

也就是每個(d,k)的取值都依賴於(d - 1, k - 1)和(d - 1, k + 1)兩個值的更優解。

怎樣判斷(d - 1, k - 1)和(d - 1, k + 1)誰更優秀呢?上文也提到過了,要保證刪除先於新增,向右走的多就表示刪除的多,x 就越大。

在(d,k) = (2,0)這個座標中,左上角的 x 值 1 要大於左下角 x值 0,所以自然而然的,從(x,y) = (1,0)走到(x,y) = (2,2)是最優解

k\d|     0     1     2 ----+----------------------   | 1 |           1,0   |         /     \ 0 |     0,0       ( 2,2 )   |         \ -1 |           0,1

如果 x 的值一樣大呢?比如(d, k) = (3,-1)的時候,有(x,y) = (2,2)和(x,y) = (2,4)兩個選擇

k\d|     0     1     2     3 ----+----------------------------   | 2 |                 3,1   |               / 1 |           1,0   |         /     \ 0 |     0,0         2,2   |         \ -1 |           0,1       ( 4,5 )   |               \     / -2 |                 2,4

上面提到過,左上角的節點向下移動到達目標節點,左下角的節點向右到達目標節點,所以我們選擇向右(刪除有限)到達目標節點的節點,也就是(2,4)

可能有人對這句話不太理解,其實把座標軸旋轉45度還原回去再看看就明白了

到目前為止,是不是感覺每一個節點的最優座標判定還是很複雜

image-20220502154005340.png

所以我們需要把整個過程按照如下步驟再簡化一下:

  1. 我們存了 k 的值和 x 的值,就不需要儲存 y 的值了,因為可以通過 k = x -y 計算出來
  2. 我們不需要儲存每一步的移動方向,只需要儲存每一步的最佳 x 值就行了,因為路徑可以通過找到最小的 d 來還原

簡化後可以得到:

k\d|     0     1     2     3     4     5 ----+--------------------------------------   | 4 |                             7   | 3 |                       5   | 2 |                 3           7   | 1 |           1           5           7   | 0 |     0           2           5   | -1 |           0           4           5   | -2 |                 2           4   | -3 |                       3

最後,觀察上圖不難發現,在每一步 d 中的 x 值都取決於(d -1) 步中的 x 值,並且每一步都在交替修改奇數位或者偶數位 k 的位置,所以對其依賴的值不會產生影響。因此,我們可以將 x 值儲存在單個以 k 為索引的扁平化陣列當中:

k |   -3   -2   -1     0     1     2     3     4 --------+-----------------------------------------------       | d = 0 |                     0       | d = 1 |               0     0     1       | d = 2 |         2     0     2     1     3       | d = 3 |   3     2     4     2     5     3     5       | d = 4 |   3     4     4     5     5     7     5     7       | d = 5 |   3     4     5     5     7     7     5     7

當在陣列 (d, k) = (5,1)到達終點 (x, y) = (7,6)時終止遍歷。

程式碼的具體實現可以參考myers-diff/main.go at master · cj1128/myers-diff 以及 jsdiff/base.js at master · kpdecker/jsdiff

這就是很純粹的動態規劃的思想:通過找到到達每一個節點的最優解,以推斷出到達終點的最優解

最後

創造不易,圖片都是自己P的,點個贊再走吧!祝大家升職加薪!

參考

理論基礎部分

資料結構與演算法之美 - 王爭 - 動態規劃理論:一篇文章帶你徹底搞懂最優子結構、無後效性和重複子問題

例項演示部分

70. 爬樓梯 - 力扣(LeetCode)

演算法圖解-巴爾加瓦-動態規劃-揹包問題

git diff 演算法部分

Git 是怎樣生成 diff 的:Myers 演算法 - CJ Ting's Blog

The Myers diff algorithm: part 1 – The If Works

The Myers diff algorithm: part 2 – The If Works

myers-diff/main.go at master · cj1128/myers-diff

jsdiff/base.js at master · kpdecker/jsdiff