4.3　實(shí)際應(yīng)用——求解TSP

我們先看一下TSP問(wèn)題的定義。TSP是一個(gè)著名問(wèn)題，在20世紀(jì)30年代作為一個(gè)挑戰(zhàn)被提出來(lái)。TSP是一個(gè)NP難問(wèn)題。首先，我們可以在不關(guān)心最優(yōu)解的情況下，隨機(jī)生成一個(gè)旅行路線來(lái)滿足訪問(wèn)所有城市這一條件。然后，我們可以在每一輪迭代中對(duì)解進(jìn)行改進(jìn)。在迭代過(guò)程中生成的每條旅行路線被稱為候選解（也可以稱為可行解）。證明一個(gè)可行解是最優(yōu)解需要呈指數(shù)級(jí)增長(zhǎng)的時(shí)間，取而代之的是使用各種基于啟發(fā)式規(guī)則的解，這些解生成的旅行路線接近最佳路線，但并非最佳路線。

旅行商需要訪問(wèn)所有給定城市構(gòu)成的列表才能完成工作：

請(qǐng)注意以下兩點(diǎn)：

• 列表中各城市之間的距離是已知的。
• 在給定的列表中，每個(gè)城市只訪問(wèn)一次。

我們可以為旅行商生成旅行計(jì)劃嗎？什么樣的旅行計(jì)劃才是最小化旅行商所走總路程的最優(yōu)解呢？

以下是我們用于演示TSP的五個(gè)加拿大城市之間的距離：

請(qǐng)注意，我們的目標(biāo)是得到一條在出發(fā)城市開始和結(jié)束的旅行路線。例如，一條典型的旅行路線可以是Ottawa-Sudbury-Montreal-Kingston-Toronto-Ottawa，這條路線總的開銷是484+680+287+263+450=2164。這是不是旅行商要走的路程最短的旅行路線？能使旅行商所走總路程最短的最優(yōu)解是什么？我們將把這些問(wèn)題留給讀者思考和計(jì)算。

4.3.1　使用蠻力策略

要求解TSP，我們首先想到的求解方案是使用蠻力策略來(lái)找出最短路線（任何路線都必須使得旅行商恰好訪問(wèn)每個(gè)城市一次，且最后返回出發(fā)城市）。蠻力策略的工作原理如下：

1. 評(píng)估所有可能的旅行路線。

2. 選擇距離最短的一條。

問(wèn)題是，對(duì)于n個(gè)城市存在（n-1）！條可能的旅行路線。這意味著5個(gè)城市將產(chǎn)生4！=24條可能的旅行路線，我們選擇距離最短的那條路線。顯然，只有在城市不太多的情況下，該方法才有效。隨著城市數(shù)量的增加，這種方法產(chǎn)生大量的排列組合，蠻力策略變得不穩(wěn)定。

我們看一下如何在Python中實(shí)現(xiàn)蠻力策略。

首先注意，旅行路線{1, 2, 3}表示從城市1到城市2再到城市3。旅行的總距離是旅行中經(jīng)過(guò)的總距離。我們假設(shè)城市之間的距離是它們之間的最短距離（即歐幾里得距離）。

我們先定義三個(gè)實(shí)用函數(shù)：

• distance_points：計(jì)算兩點(diǎn)之間的絕對(duì)距離。
• distance_tour：計(jì)算旅行商在給定的旅行路線中需要經(jīng)過(guò)的總距離。
• generate_cities：隨機(jī)生成位于長(zhǎng)500、寬300的矩形中的n個(gè)城市。

這些函數(shù)的代碼如下：

在上面的代碼中，我們用itertools包的permutations函數(shù)來(lái)實(shí)現(xiàn)alltours（用來(lái)生成所有城市的排列組合），我們還用復(fù)數(shù)來(lái)表示距離。這意味著以下幾點(diǎn)：

• 計(jì)算兩個(gè)城市a和b的距離如計(jì)算distance(a, b)一樣簡(jiǎn)單。
• 我們只需調(diào)用generate_cities(n)就可以創(chuàng)建n個(gè)城市。

現(xiàn)在，我們定義一個(gè)函數(shù)brute_force，該函數(shù)會(huì)生成所有可能的城市旅行路線。一旦生成了所有可能的旅行路線，它將選擇距離最短的路線：

下面，我們定義實(shí)用函數(shù)來(lái)幫助我們繪制城市，這些函數(shù)包括：

• visualize_tour：繪制特定旅行路線中的所有城市及其之間的連接。它還會(huì)突出顯示旅行開始的城市。
• visualize_segment：在visualize_tour中使用，用于繪制一段路線中的城市和城市之間的連接。

請(qǐng)看下面的代碼：

最后，我們實(shí)現(xiàn)函數(shù)tsp()，它可以完成以下工作：

1. 根據(jù)算法和請(qǐng)求的城市數(shù)量生成旅行路線

2. 計(jì)算算法運(yùn)行所需的時(shí)間

3. 生成一個(gè)圖，展示運(yùn)行結(jié)果

一旦定義了tsp()，我們就可以用它來(lái)創(chuàng)建一條旅行路線（如圖4-6所示）。請(qǐng)注意，在圖4-6中我們使用tsp函數(shù)生成了10個(gè)城市的旅行路線。當(dāng)n=10時(shí)，它將生成（10-1）!=362 880種可能的排列組合。如果n增加，排列組合的數(shù)量就會(huì)急劇增加，這樣就不能使用蠻力法了。

4.3.2　使用貪心算法

如果用貪心算法來(lái)求解TSP，則在每一步中我們都可以選擇一個(gè)看起來(lái)比較合理的城市，而不是尋找一個(gè)可以得到最佳總體路徑的城市。因此，每當(dāng)需要選擇一個(gè)城市時(shí)，我們只需要選擇離當(dāng)前位置最近的城市，而不需要去驗(yàn)證這個(gè)選擇是否會(huì)帶來(lái)全局最優(yōu)的路徑。

貪心算法的方法很簡(jiǎn)單：

1. 從任何一個(gè)城市出發(fā)。

2. 在每一步中，繼續(xù)訪問(wèn)以前未訪問(wèn)過(guò)的下一個(gè)最近的相鄰城市，以繼續(xù)旅行。

3. 重復(fù)第二步。

我們定義一個(gè)名為greedy_algorithm的函數(shù)來(lái)實(shí)現(xiàn)上述邏輯：

現(xiàn)在，我們用greedy_algorithm來(lái)為2000個(gè)城市創(chuàng)建一條旅行路線（如圖4-7所示）。

請(qǐng)注意，貪心算法僅花費(fèi)0.514秒即可為2000個(gè)城市生成旅行路線。如果我們使用蠻力法，它將會(huì)生成（2000-1）！種排列組合，這幾乎是無(wú)窮大。

需要注意的是，貪心算法是基于啟發(fā)式規(guī)則的，并不能證明所得到的解就一定是最優(yōu)的。

下面，我們討論P(yáng)ageRank算法的設(shè)計(jì)。