資源簡介

(共62張PPT)
第7章 經典算法
約瑟夫問題
球鐘問題
八皇后問題
背包問題
地圖著色問題
旅行商問題
約瑟夫問題
球鐘問題
八皇后問題
7.2
7.3
7.1
點擊查看本小節知識架構
點擊查看本小節知識架構
點擊查看本小節知識架構
背包問題
7.4
點擊查看本小節知識架構
地圖著色問題
7.5
點擊查看本小節知識架構
旅行商問題
7.6
點擊查看本小節知識架構
學習目標
掌握
熟練
掌握
掌握各種經典算法的設計思想與操作原理
1
2
熟練操作算法中涉及的數據結構
3
掌握具體算法實例的代碼編寫方法
本章將主要介紹一些經典算法的實例。經典算法涉及到很多解決問題的方法，如回溯法、貪心算法、分治法、動態規劃法、分支界限法等。前面的章節中，本書已經介紹了利用貪心算法與分治法解決問題的實例，如赫夫曼樹、快速排序等。本章將主要介紹使用回溯法與動態規劃法解決問題的實例，其中也涉及一些數據結構的操作，望讀者理解算法的設計思想，熟練編寫操作代碼。
7.1 約瑟夫問題
7.1.1
算法概述
返回目錄
7.1.2
算法實現
7.1.1 算法概述
約瑟夫問題又稱為約瑟夫斯置換，是一個在計算機科學和數學中出現的問題。在計算機編程中，類似問題又可以稱為約瑟夫環。約瑟夫問題有很多版本，其一般的形式如下所示。
假設編號分別為(1,2,…n)的 n 個人圍坐成一圈。其中，約定序號為 k(1≤k≤n)的人從 1 開始報數，數到 m的那個人出列，然后下一位繼續從 1 開始報數，數到 m的那個人再次出列，以此類推，直到所有人出列為止。
如圖所示，設 k 等于 3，n 等于 8，m 等于 4，則出列的序列為 6–2–7–4–3–5–1–8。
7.1.2 算法實現
1．鏈表實現
由 7.1.1 節中對約瑟夫問題的簡單描述可知，每個待出列的人都可以被視為一個數據元素，這些元素形成一個封閉環。因此，可以使用單向循環鏈表來解決約瑟夫問題。
使用單向循環鏈表解決約瑟夫問題的代碼參考教材7.1.2節。
例中，joseph()函數將數據元素個數設定為 8，然后從第 3 個元素開始計數，每當計數到第 4個元素時，將該元素刪除。
Joseph()函數首先采用循環的方式對單向循環鏈表進行遍歷，然后尋找需要刪除的元素的上一個元素與下一個元素，最后將這兩個元素進行連接，即可實現指定元素的刪除。每一次刪除元素后，單向循環鏈表都會重新連接為一個新的環，因此無須考慮環中數據元素減少的問題。程序運行結果如下所示。
由運行結果可以看出，按照約瑟夫問題的規則，輸出數據元素的順序為 6–2–7–4–3–5–1–8。
7.1.2 算法實現
2．循環實現
在單向循環鏈表中，每刪除一個數據元素（結點）后，鏈表都會重新形成新的循環。因此，無論第幾次刪除數據元素，其刪除過程都與第一次相同，即計數到 k 時，刪除對應數據。而如果采用數學的思想處理約瑟夫問題，就需要考慮刪除數據產生的空位對后續計數的影響。例如，假設當前環中的數據元素為 10 個，從第 0 個元素開始，每次計數到 4 時，將對應的數據元素刪除，如圖所示。
7.1.2 算法實現
對環中的數據元素進行操作，第一次刪除的是編號為 3 的元素，第二次刪除的是編號為 7 的元素（以元素 4 為起始點進行計數）。由此推理，第三次刪除的是編號為 1 的元素。當進行第四次刪除操作時，編號為 3 的元素已經被刪除（環斷開），此時需要刪除的是編號為 6 的元素，而非編號為 5的元素，可見數據刪除產生的空洞對計數產生了影響。
為了解決上述問題，可以將每一次刪除數據元素后的環看作成一個新環，這樣就不會產生數學運算上的不連續，如圖所示。
7.1.2 算法實現
圖中，第一次刪除的是編號為 3 的元素，元素 3 刪除后，元素 2 與元素 4 的連接斷開，形成空洞。因此，可以將刪除元素后的環重新看作一個新環，即將被刪除元素的下一位元素重新編號為 0，以此類推，這樣形成的新環在數學運算上就是連續的，不會對后續刪除元素產生影響。
由圖可知，實際刪除的是編號為 3 的元素，而在新環中該元素對應的編號為 9。因此，當前需要解決的問題是新環中被刪除元素的編號與舊環中的編號如何一一對應。
從圖中可以看出，新環中的元素的編號是由舊環中的元素整體移動 k（k 為計數值，為 4）個單位得來的。由此可以推理出公式 old_num=(new_num+k)%old_sum，其中，old_num 表示舊環中被刪除元素的
編號，new_num 表示新環中被刪除元素的編號，k 表示計數值，old_sum 表示舊環中元素的總個數。例如，圖中需要刪除的元素的編號為 3，而在新環中對應的編號為 9，k 為 4，舊環中元素總數為 10（刪除元素之前環中元素的總數），即 3=(9+4)%10。
7.1.2 算法實現
按照上述操作方式，在每一次刪除元素后，都重新構造新環，如圖所示。
7.1.2 算法實現
圖中，每一次刪除元素后，都需要重新構造新環，即從被刪除元素的下一位開始重新編號。每一個環相對于上一個環來說，都是一個新環。
綜上所述，根據構造的新環與推理公式，即可推導出原始的環中每一次刪除的元素對應的編號。例如，計算圖中的原始環第五次刪除的元素的編號，只需要找到第五次刪除元素后構造的新環，然后根據推理公式進行推導即可，如圖所示（截取自圖 7.4）。
7.1.2 算法實現
第五次刪除元素后構造的新環在數學計算上是連續的，即序列順序為 0–1–2–3–4，得出第五次刪除的元素的編號為 5（在新環中的編號，非原始環中的編號）。結合推理公式可知，(5+4)%6=3，即編號為 5 的元素對應上一個新環（第四次刪除元素后構造的新環）中編號為 3 的元素，如圖所示（截取自圖 7.4）。
將元素 3 加入推理公式可得出，(3+4)%7=0，即編號為 3 的元素對應上一個新環（第三次刪除元素后構造的新環）中編號為 0 的元素，如圖所示（截取自圖 7.4）。
7.1.2 算法實現
將元素 0 加入推理公式可得出，(0+4)%8=4，即編號為 0 的元素對應上一個新環（第二次刪除元素后構造的新環）中編號為 4 的元素，如圖所示（截取自圖 7.4）。
將元素 4 加入推理公式可得出，(4+4)%9=8，即編號為 4 的元素對應上一個新環（第一次刪除元素后構造的新環）中編號為 8 的元素，如圖所示（截取自圖 7.4）。
7.1.2 算法實現
將元素 8 加入推理公式可得出，(8+4)%10=2，即編號為 8 的元素對應上一個新環（原始環）中編號為 2 的元素，如圖 所示（截取自圖 7.4）。
經過一系列推導可知，原始環中第五次刪除的元素的編號為 2。
總結上述過程，可以得到以下結論。
（1）如果需要確定原始環中第 n 次刪除的元素，只需要找到第 n 次構造的新環中刪除的元素的編號，將其代入推理公式執行 n 次，即可確定原始環中刪除的元素。
（2）第 n 次構造的新環中刪除的元素的編號等于元素的總個數減去 n，例如，圖 7.4 中，第七次刪除的元素在新環中的編號為 3(3=10－7)。
7.1.2 算法實現
將上述結論與圖 7.4 結合可以得出以下結果（元素總數 sum 為 10，計數值 k 為 4）。
（1）第一次刪除的元素的編號為：(sum－1+k)%sum=(10－1+4)%10=3。
（2）第二次刪除的元素的編號為：(sum－2+k)%(sum－1)=(8+4)%9=3，(3+k)%sum=(3+4)%10=7。
（3）第三次刪除的元素的編號為：(sum－3+k)%(sum－2)=(7+4)%8=3，(3+k)%(sum－1)=(3+4)%9=7，(7+k)%sum=(7+4)%10=1。
（4）其他輪次的刪除操作可以此類推。
根據上述求值操作可知，求第 n 次刪除元素的編號，需要執行 n 次推理公式，且每一次的計算結果都將代入下一輪次的公式中繼續運算。同時可以看出，算式的一般形式為(sum－1+k)%sum。
7.1.2 算法實現
將推導得出的結論轉換為程序，如例所示。
7.1.2 算法實現
7.1.2 算法實現
由例可見，通過數學的思想同樣可以解決約瑟夫問題。joseph()函數通過獲取新環中的元素對應的編號以及循環執行推理公式，確定原始環中刪除的元素。程序運行結果如下所示。
由運行結果可知，按順序刪除的元素為 8–24–32–5–14–16–23–23–12–7，其對應的編號（在數組中的下標值）為 3–7–1–6–2–9–8–0–5–4。
7.1.2 算法實現
3．遞歸實現
采用遞歸的編程方式同樣可以解決約瑟夫問題，遞歸操作與循環操作類似，都是循環執行推理公式。不同的是，循環實現是直接逐級計算被刪除元素在新環中對應的編號，而遞歸實現是先按輪次向下調用，然后逐級計算被刪除元素在新環中對應的編號。采用遞歸的方式解決約瑟夫問題，如例所示。
7.1.2 算法實現
例采用 joseph()函數嵌套的方式實現遞歸操作。程序運行結果如下所示。
由運行結果可知，按順序刪除的元素為 3–7–1–6–2–9–8–0–5–4。
7.1.2 算法實現
假設當前原始環中的元素總數為 10，計數值為 4，計算第四次刪除的元素的編號，結合例的程序推理該遞歸操作的過程，可知遞歸實現的操作原理如圖所示。
7.1.2 算法實現
循環實現則是直接將編號代入公式計算，其操作原理如圖所示。
對比圖可知，循環與遞歸這兩種實現方式本質上沒有區別。
7.2 球鐘問題
7.2.1
算法概述
返回目錄
7.2.2
算法實現
7.2.1 算法概述
球鐘問題是一個需要借助于棧和隊列來解決的問題。球鐘是一種利用球的移動來記錄時間的簡單裝置。它有 3 個可以容納若干個球的指示器：小時指示器、五分鐘指示器、分鐘指示器。例如，分鐘指示器中有 3 個球，五分鐘指示器中有 4 個球，小時指示器中有 8 個球，則表示當前時間為 8點 23 分。
球鐘問題的工作原理如下。
（1）每過一分鐘，球鐘就會從球隊列的隊首取出一個球放入分鐘指示器（分鐘指示器中最多可容納 4 個球）。當放入第 5 個球時，在分鐘指示器中的 4 個球就會按照它們被放入時的相反順序加入球隊列的隊尾，第 5 個球則會進入五分鐘指示器。
（2）五分鐘指示器最多可放 11 個球，當放入第 12 個球時，在五分鐘指示器中的 11 個球就會按照它們被放入時的相反順序加入球隊列的隊尾，第12 個球則會進入小時指示器。
（3）小時指示器最多可放 11 個球，當小時指示器放入第 12 個球時，原來的 11 個球就會按照它們被放入時的相反順序加入球隊列的隊尾，然后第 12個球也加入隊尾。此時三個指示器均為空，回到初始狀態。
7.2.1 算法概述
綜上所述，球鐘表示的時間范圍是 00:00 到11:59。其工作原理如圖所示。
7.2.1 算法概述
由圖可以看出，球隊列中的球遵循先進先出的原則，可以使用數據結構中的隊列來實現。而指示器中的球，放入與移出的順序剛好相反，遵循后進先出的原則，可以使用數據結構中的棧來實現。因此，解決球鐘問題需要使用 1 個隊列與 3 個棧，且完成一輪計時需要 27（11+11+4+1）個球。
7.2.2 算法實現
由節的分析可知，球鐘問題需要借助隊列與棧來解決，因此，下面將展示使用鏈式隊列實現球隊列和使用順序棧實現指示器。
自定義頭文件實現鏈式隊列的數據定義以及基本操作，示例代碼參考教材7.2.2節。
例在頭文件中實現了鏈式隊列的創建、入隊、出隊以及隊列的判斷。
自定義頭文件實現順序棧的數據定義以及基本操作，示例代碼參考教材7.2.2節。
例在頭文件中實現了順序棧的創建、入棧、出棧以及輸出棧中的數據。
測試程序需要借助于例 7-4 與例 7-5 中的函數接口，示例代碼參考教材7.2.2節。
例中，程序利用球鐘的計時規則，計算從球出隊開始到球全部回到隊列（同時保證球在隊列中的順序與初始出隊時一致）的時間。程序運行結果如下。
由運行結果可知，按照球鐘的計時規則，從球開始出隊到全部入隊（入隊后球的順序與初始出
隊時一致）的時間為 23 天。
7.3 八皇后問題
7.3.1
算法概述
返回目錄
7.3.2
算法實現
7.3.1 算法概述
八皇后問題是一個利用回溯法的典型案例，該問題是由國際西洋棋棋手馬克斯·貝瑟爾于 1848 年提出的。其具體形式為：在 8 格×8 格的國際象棋棋盤上擺放八個皇后，使其不能互相攻擊（即任意兩個皇后都不能處于同一行、同一列或同一斜線上），計算有多少種擺法。
棋盤中的任意兩個皇后都不在同一行、同一列或同一斜線上，滿足擺放規則，如圖所示。
7.3.1 算法概述
由圖可知，第二個皇后只能擺放在第二行的 A 位置或 B 位置上，按照順序，先將其擺放在A 位置，如圖 所示。
解決八皇后問題的方法有很多，本節將主要介紹通過回溯法解決這一問題。為了便于理解，可以將皇后數量及棋盤變小進行分析。
假設當前皇后數量為 4，棋盤大小為 4 格×4 格，由于每一個皇后只能占單獨的一行與一列，因此第一個皇后可以擺放在第一行的第一列上，如圖所示。
7.3.1 算法概述
由圖可知，重新將第二個皇后擺放完成后，第三個皇后只能擺放在第三行的 C 位置上，而C 位置與 D 位置在同一斜線上，因此第四個皇后將無法擺放。再次回溯到上一步（第一次擺放皇后時），重新擺放第一個皇后，將其擺放到第一行的第二列上，如圖所示。
由圖可知，在第二個皇后擺放完成后，第三個皇后只能擺放在第四行的 C 位置上，而棋盤中已經沒有位置可以擺放第四個皇后。此時就需要回溯到上一步，重新擺放第二個皇后。將第二個皇后擺放到圖 7.15 所示棋盤的 B 位置上，如圖所示。
7.3.1 算法概述
由圖可知，最后一個皇后可以擺放在最后一行的 C 位置上。擺放結果如圖所示。
由圖可知，重新將第一個皇后擺放完成后，第二個皇后可以擺放在第二行的 A 位置上，第三個皇后可以擺放在第三行的 B 位置上，如圖所示。
由圖可知，棋盤中任意兩個皇后都不在同一行、同一列或同一斜線上，滿足指定的規則。
7.3.2 算法實現
由 7.3.1 節算法分析可知，在棋盤中擺放皇后，需要考慮下一個皇后是否有位置可以擺放，如果沒有，則返回到上一步，重新擺放皇后。因此，在設計代碼時，需要采用回溯的思想，示例代碼參考教材7.3.2節。
例中，Check()函數用來檢測皇后是否可以擺放，EightQueen()函數通過嵌套的形式實現遞歸操作（函數執行一次操作棋盤中的一行），并通過循環與 Check()函數結合，確定皇后在一行中的擺放位置（即某一列上）。如果一行中的所有位置都不適合擺放皇后，則返回到上一步（上一行），重新擺放上一個皇后。程序運行結果如下。
由運行結果可知，八皇后問題的解法共有 92 種。
7.4 背包問題
7.4.1
算法概述
返回目錄
7.4.2
算法實現
7.4.1 算法概述
背包問題可以描述為：假設有 n 個物品與一個背包，物品 i 的質量為 W i ，價值為 V i ，背包的最大載重為 c，求如何裝載可使背包中物品的總價值最大。本次只討論“0-1”的情況，即物品不可拆分，只能裝入或不裝入，且不能將同一個物品裝入多次。
解決背包問題的方法有很多，如回溯法、動態規劃法、分支界限法等。本節將主要介紹通過回溯法解決背包問題，即采用探測的方式。接下來通過一個具體的示例展示探測的過程。
例如，一個背包只能載重 8kg，已知荔枝 4kg 的價格為 45 元，櫻桃 5kg 的價格為 57 元，香蕉1kg 的價格為 11 元，草莓 2kg 的價格為 22.5 元，菠蘿 6kg 的價格為 67 元，如表所示。
7.4.1 算法概述
對表中的物品進行試探，具體操作步驟如下（略去單位）。
（1）假設先將荔枝放入背包，此時背包中物品的總價值為 45，總重量為 4（背包的最大載重為 8），當前背包問題的最優解為 45（暫時）。
（2）將櫻桃放入背包，此時背包總重量為 9，大于背包的最大載重，不滿足規則，因此將櫻桃取出并進行判斷。判斷當前背包中物品總價值加未探測物品的總價值是否大于最優解（荔枝的價值與其他物品的總價值之和大于荔枝的價值），判斷結果為需要繼續探測。
（3）將香蕉放入背包，此時背包的總重量為 5，背包中物品的總價值為 56，背包總重量小于背包最大載重，可以繼續探測。當前背包問題的最優解為 56。
（4）將草莓放入背包，此時背包的總重量為 7，背包中物品的總價值為 78.5（最優解為 78.5），背包總重量小于背包最大載重，可以繼續探測。
（5）將菠蘿放入背包，此時背包的總重量為 13，大于背包的最大載重，不滿足規則，因此將菠蘿取出。至此一輪探測結束，保存當前最優解（最優解為 78.5）。
7.4.1 算法概述
（6）回溯到上一步，將草莓取出，當前背包的總重量為 5，背包中物品的總價值為 56，判斷當前背包中物品總價值加未探測物品的總價值是否大于最優解（當前背包中物品的總價值為 56，未探測物品為菠蘿，二者之和為 123，大于最優解 78.5），判斷結果為需要繼續探測。
（7）將菠蘿放入背包，此時背包的總重量為 11，大于背包的最大載重，不滿足規則，因此再次將菠蘿取出。
（8）回溯到上一步，將香蕉取出，再放入草莓……
7.4.1 算法概述
上述操作類似于窮舉法，即列出所有情況，再進行比較。不同的是，背包問題不需要探測所有結果，如果探測到某一物品時，發現當前重量已經超過最大載重，則無須再探測后續物品；如果當前背包中物品的總價值加上未探測物品的總價值小于目前的最優解，同樣也無須再探測后續物品。這種探測方式采用了解空間樹的思想，并按照深度優先搜索的方式進行探測，如圖 所示。
7.4.1 算法概述
假設當前有 3 個物品 x[1]、x[2]、x[3]，樹中結點的左孩子表示選取，右孩子表示不選取，則選取物品的方案有2 3 =8 種（n 個物品的選取方案有 2 n 種）。具體分析如下。
（1）如果第一個物品不選取，第二個物品不選取，第三個物品也不選取，則為方案 0，此時得到一個暫時的最優解。
（2）回溯到上一步，選取第三個物品，則為方案 1。比較當前值與最優解，以較大值作為新的最優解。
（3）回溯到探測第二個物品時，選取第二個物品，不選取第三個物品，則為方案 2。同樣，比較當前值與最優解，以較大值作為新的最優解。
（3）回溯到上一步，選取第三個物品，則為方案 3。再次比較當前值與最優解，以較大值作為新的最優解。
（4）以此類推，通過不斷遞歸和回溯，最終確定最優解。
采用回溯法處理背包問題時，處理的數據量不宜過大，如果有 n 個數據對象，則對應的解決方案有 2 n 種。隨著 n 的增長，其解的數量將以 2 n 級增長。
7.4.2 算法實現
采用回溯法解決背包問題，示例代碼參考教材7.4.2節。
例中，Optimal_Solution()函數用來求背包問題的最優解，函數通過嵌套的方式實現遞歸探測下一個物品，如果當前探測的物品加入背包后，背包總重量超過最大載重，則直接跳過當前探測的物品。程序運行結果如下所示。
7.4.2 算法實現
由運行結果可知，最優解的物品組合為物品 1、物品 2、物品 5，對應的重量分別為 2kg、2kg、5kg，價值分別為 6 元、3 元、6 元，最終得到的最優解為 15 元。
7.5 地圖著色問題
7.5.1
算法概述
返回目錄
7.5.2
算法實現
7.5.1 算法概述
地圖著色問題是著名的 NP 完全問題（多項式復雜程度的非確定性問題）之一。該問題可以詳細
分為以下 3 種模式。
（1）圖的著色問題，即給定無向連通圖 G 與 n 種不同的顏色，計算所有不同的著色方法，使得任意相鄰的 2 個頂點具有不同的顏色。
（2）圖的著色判定問題，即給定無向連通圖 G 與 n 種不同的顏色，使用這些顏色為圖 G 中的各頂點著色，判斷是否存在一著色法使圖 G 中任意相鄰頂點具有不同的顏色。
（3）圖的著色優化問題，即計算無向聯通圖 G 中，至少需要多少種顏色使得任意相鄰的 2 個頂點具有不同的顏色。
7.5.1 算法概述
如圖所示，創建一個虛擬的地圖，并將其轉換為一個無向連通圖（不共享一條邊的塊不記為相鄰）。
7.5.1 算法概述
由圖可知，要解決地圖著色問題，可以將復雜的地圖轉換為數據結構中的無向連通圖，然后設置頂點之間的關系來表示地圖中的區域是否相鄰。例如，設置頂點 A 與頂點 B 之間的權值為 1，頂點 A 與頂點 E 之間的權值為 0，表示區域 A 與區域 B 相鄰，區域 A 與區域 E 不相鄰。
7.5.2 算法實現
下面通過代碼展示地圖著色問題以及地圖著色優化問題。
1．地圖著色問題
地圖著色問題的解決方法與八皇后問題、背包問題類似，都是利用深度優先搜索的方式進行遞歸并回溯，找到所有問題的子集。具體代碼參考教材7.5.2節。
例中，程序使用鄰接矩陣的方式（二維數組）實現無向連通圖中頂點的存儲，函數 dfs()通過遍歷二維數組來計算著色的方案數量，并通過函數嵌套的方式遞歸調用，遞歸的目的是探測每一個頂點與其他頂點的關系。程序通過回溯的方式對已著色的頂點重新分配顏色，以便探測出所有可行的配色方案。dfs()函數通過判斷頂點是否相鄰以及顏色是否被使用決定是否分配新的顏色。
7.5.2 算法實現
程序運行結果如下所示（以圖 7.22 中的無向連通圖作為測試對象，二維數組的起始下標為 1）。
由運行結果可知，圖中的虛擬地圖在只有 3 種顏色的情況下，有 18 種配色方案。
7.5.2 算法實現
2．地圖著色優化問題
地圖著色優化問題即計算地圖的最小色數，該問題只需要求出可行著色方案中的一種，要求使用的顏色數量最少，不需要考慮頂點之間的顏色調換。具體代碼參考教材7.5.2節。
例中，graph_input()函數用來讀取終端輸入的頂點與邊以及二者之間的關系；map_overlay()函數用來實現著色，并通過函數嵌套完成遞歸調用，每一次調用的目的是對下一個頂點進行著色；colorsame()函數用來判斷頂點之間是否相鄰以及顏色是否被使用；output()函數輸出著色方案，并通過編號表示顏色種類。
7.5.2 算法實現
程序運行結果如下所示（以圖 7.22 作為測試對象）。
7.5.2 算法實現
由運行結果可以看出，圖中的虛擬地圖只需要 3 種顏色即可完成著色，其中頂點 A、頂點 E、頂點 G 使用相同的顏色，頂點 B、頂點 D、頂點 F 使用相同的顏色，頂點 C 單獨使用一種顏色，如圖所示。
圖所示的著色方案只是可行方案中的一種。
7.6 旅行商問題
7.6.1
算法概述
返回目錄
7.6.2
算法實現
7.6.1 算法概述
旅行商問題是一個經典的組合優化問題。具體的問題描述為：一個推銷員必須訪問 n 個城市，且所有城市只訪問一次，然后回到起始的城市（城市與城市之間有旅行費用，且推銷員希望旅行費用之和最?。Ｒ部梢該Q一種描述：給定一系列城市和每對城市之間的距離，求訪問每一座城市一次并回到起始城市的最短回路。
解決旅行商問題的方法有很多，如貪心算法、動態規劃法、分支界限法、遺傳算法、蟻群算法等。本節將主要介紹采用動態規劃法實現旅行商問題，并通過具體的示例展示動態規劃法的分析過程。
創建一個有向圖，表示城市及城市之間的連通關系，如圖所示。
7.6.1 算法概述
根據圖創建一個鄰接矩陣，表示頂點與頂點之間的關系，如圖所示。
（1）從城市 0 出發，經過城市 1，再從城市 1 出發，經過[2,3]這兩個城市，然后回到城市 0。
（2）從城市 0 出發，經過城市 2，再從城市 2 出發，經過[1,3]這兩個城市，然后回到城市 0。
（3）從城市 0 出發，經過城市 3，再從城市 3 出發，經過[1,2]這兩個城市，然后回到城市 0。
由上述描述可知，一個大的需求可以分為三個小問題，并且需要求得這三個小問題的最優解。因此，這個需求具有最優子集，可以用動態規劃來實現。
7.6.1 算法概述
設置一個二維的動態規劃表 dp，定義符號{1,2,3}表示經過[1,2,3]這三個城市，然后回到城市 0。因此上述需求可以用動態規劃表表示為 dp[0][{1,2,3}]，如果用 C 表示兩個城市之間的旅行費用，則dp[0][{1,2,3}]=min{C 01 +dp[1][{2,3}]，C 02 +dp[2][{1,3}]，C 03 +dp[3][{1,2}]}。其中，min 表示求最小值，C 01 表示從城市 0 到城市 1 的旅行費用，dp[1][{2,3}]表示從城市 1 出發，經過城市[2,3]，然后回到城市 0，其他以此類推。按照上述表示方法，繼續推導可以得出，dp[1][{2,3}]=min{C 12 +dp[2][{3}]，C 13 +dp[3][{2}]}，dp[2][{3}]表示從城市 2 出發，經過城市 3，然后回到城市 0。再次進行推導，dp[2][{3}]=C 23 +dp[3][{}]，dp[3][{}]指的是從城市 3 出發，不經過任何城市，回到城市 0，即 C 30 。
將城市編號設置為二進制數，城市 1 為 001，城市 2 為 010，城市 3 為 100（假設城市編號為 m，則其二進制數對應的 m 位為 1，計算的方式為 1 (m－1)），以此類推，則上述動態規劃表達式中，{1,2,3}可以表示為 111，轉換成十進制數為 7，{2,3}可以表示 110，轉換成十進制數為 6。
7.6.1 算法概述
例如，dp[0][{1,2,3}]=dp[0][7]，dp[1][{2,3}]=dp[1][6]。由此得出整個需求對應的動態規劃表，如表所示。（假設城市有 n 個，則 dp 表的列數為 2 n ，也可以表示為 1 (n－1)。）
7.6.1 算法概述
表中，第一列表示從哪一個城市出發，其余列表示經過某些城市并回到城市 0 所產生的費用。例如，表中的第 4 行第 4 列，表示從城市 1 出發經過城市 2，然后回到城市 0 的費用為 45；表中的第 5 行第 7 列，表示從城市 2 出發經過城市[1,3]，然后回到城市 0 的費用為 55。
由上述分析可以看出，整個問題的需求為計算 dp[0][7]的值，而 dp[0][7]=min{C 01 +dp[1][6]，C 02 +dp[2][5]，C 03 +dp[3][3]}，因此計算 dp[0][7]的最優解就是計算 dp[1][6]、dp[2][5]、dp[3][3]三者中的最小值，其中，dp[1][6]=min{C 12 +dp[2][4]，C 13 +dp[3][2]}。同理，計算 dp[1][6]的最優解就是計算dp[2][4]、dp[3][2]二者中的較小值。以此類推，經過層層選取即可得到最終的最優解。
需要注意的是，計算 dp[2][3]即從城市 2 出發，經過城市{1,2}，這顯然不合理，因{1,2}中已經包含了城市 2，這種情況需要忽略掉（即判斷數字 3 的二進制數的第 2 位是不是 1，如果為 1 表示不合理）。同樣，計算 dp[2][5]時，從城市 2 出發，經過城市{1,3}，如果選擇先經過城市 1，再經過城市 3（城市 3 與城市 0 不直接相連，即 dp[3][{}]的值無法計算），則最終無法回到城市 0。
7.6.2 算法實現
采用動態規劃法解決旅行商問題，如例所示。
例中，TSP()函數主要用來構建動態規劃表 dp[N][M]，通過已知的記錄頂點間距離的矩陣，推算出 dp[N][M]中每一個元素的值。其中，dp[N][M]表示從頂點 N 出發經過狀態 M，最后到達起始點的總距離。根據 7.6.1 節的分析可知，從起始點出發再回到起始點的最短路徑為 dp[N][（1 N－1 ）－1]（N 表示頂點的個數）。getPath()函數則通過動態規劃表 dp[N][M]計算出從頂點 0 出發再回到頂點 0 的最短路徑，即計算動態規劃表 dp[N][M]中的最小子集（最優解）。printPath()函數用來輸出最優的路徑。程序運行結果如下所示。
7.6.2 算法實現
由運行結果可知，最短路徑的長度為 23，經過頂點的順序為0 1 4 2 3 0。為了測試上述輸出是否正確，可以根據例中列出的矩陣畫出對應的無向圖，如圖所示。
7.6.2 算法實現
根據頂點之間的權值可以看出，從頂點 0 出發，可以直接到達頂點 1、頂點 3、頂點 4，其權值分別為 3、8、9，因此下一個到達的頂點為頂點 1。再從頂點 1 出發，可以直接到達頂點 2、頂點 3、頂點 4，其權值分別為 3、10、5，如果選擇先經過頂點 2，則接下來必須經過頂點 3、頂點 4，由于頂點 3 與頂點 4 之間的權值為 20（最大值），因此這里不能選擇經過頂點 2。選擇經過頂點 4，從頂點4 出發，可以直接到達頂點 2、頂點 3，其權值分別為 3、20，這里選擇經過頂點 2。再從頂點 2 出發，經過最后一個未經過的頂點 3，最后回到頂點 0。從圖 7.26 中可以計算得出，此路徑為最優路徑，其權值最小，為 23，與程序輸出結果一致。
本章小結
本章主要展示了一些經典算法的操作實例。其中，約瑟夫問題與球鐘問題都涉及了對數據結構的操作，包括單向循環鏈表的插入與刪除、隊列與棧的插入與刪除等。本章通過回溯法解決了八皇后問題、背包問題以及地圖著色問題，通過動態規劃法解決了旅行商問題。望讀者通過對具體實例的學習熟悉數據結構的基本操作，在理解算法設計思想的基礎上，掌握代碼操作方法，從而提高實際開發中的代碼設計能力。

展開更多......

收起↑