《Python算法教程》——第1章 引言 1.1 這是一本怎麼樣的書

本節書摘來自異步社群《python算法教程》一書中的第1章，第1.1節，作者[挪威]magnus lie hetland（赫特蘭）， 淩傑 譯，更多章節内容可以通路雲栖社群“異步社群”公衆号檢視。

1．提出問題。

2．思考真正困難所在。

3．提出解決方案。

——摘自《the feynman algorithm》，murray gell-mann著

讓我們先來考慮一下下面這個問題：我們想要訪遍瑞典境内所有的城市、小鎮和村莊，然後再傳回出發地點。顯然，這段旅程肯定要耗費掉不少時間（畢竟我們要通路24 978個地方），因而我們希望能最小化該旅行路線。也就是說，我們既要能按計劃逐個參觀這些地方，又要盡可能地走出一條最短路線來。作為一個程式員，我們當然不屑于用手工方式來設計該路線，顯然會更傾向于用寫代碼的方式來完成相關計劃。然而，這似乎是一件不可能完成的任務。的确，想要寫出一個針對少量城鎮的簡單程式并不難，但如果想要進一步用它來解決實際問題，相關的改進就會變得極其困難。這是為什麼呢？

其實，早在2004年就已經有一個五人的研究團隊發現了這個被稱為瑞典之旅的問題，之後陸續有多個别的研究團隊也都試圖解決過這個問題，但是都失敗了。該五人團隊采用了一款帶有智能優化技術的、能模拟交易技巧的軟體，并将其運作在一組由96台機器（xeon 2.6ghz）組成的工作站叢集上。結果，該軟體從2003年3月一直運作到2004年5月。最終不得不在列印出該問題的最佳解決方案之前被中止運作。因為綜合各方面的因素，他們估計程式所需要的總cpu時間竟然長達85年！

下面再來思考一個類似的問題：我們想要在中國西部的喀什市到東海岸的甯波市之間找出一條最短路線。目前，中國境内有3 583 715千米長的公路和77 834千米長的鐵路，之間有着數以百萬計的路口可供我們考慮，其中可供選擇的路線千千萬萬，難以估算。這個問題似乎與前一個問題是密切相關的，都是希望通過gps導航和線上地圖服務找出最短路線的規劃問題，并且不能有太明顯的滞後現象。也就是說，隻要向您最愛的地圖服務程式輸入這兩個城市，您就應該能在短時間内得到它們之間的最短路線。這又應該怎麼做呢？

關于這些問題，讀者将來都可以在本書中找到相關進一步的讨論。例如，第一個問題其實叫作旅行商問題（traveling salesman，或推銷員問題（salesrep）），這将是本書第11章所要涵蓋的内容。而所謂的最短路徑問題（shortest path），則是第9章中所要介紹的内容。但我們更希望讀者能從中學會如何深入分析問題的困難所在，并且掌握那些已被承認的、高效的知名解決方案。更為重要的是，我們将在本書中傳授一系列常用的算法處理技術，及一些與計算機運算相關的問題，以便幫助讀者熟練掌握書中所介紹的技術和算法，以及所示範的針對困難問題而提出的最接近期望值的解決方案。在這一章中，我們将對本書的主要内容做簡單介紹——我們可以期望什麼，我們應該期望什麼。另外，我們還會列舉本書各章節所要介紹的具體内容，以便讀者可以直接跳到自己想閱讀的内容附近。

簡而言之，這是一本為python程式員解決算法問題的書。正如書上所說，它的内容涵蓋相關的面向對象模式和一些常見問題的處理方式——也就是相關的解決方案。對于一個算法設計者，我們需要的不是簡單地實作或執行一些現有算法的能力。相反，我們期望能拿出一個新算法——一個能解決一般性問題的、前人沒有提過的全新解決方案。在本書中，我們要學習的就是此類解決方案的設計原則。

但這又不是一本傳統意義上的算法書。畢竟，大部分這類題材的權威書籍（例如knuth那部經典著作，或是由cormen等人合著的那本标準教科書）都屬于理論研究型的，顯得有些過于嚴肅，盡管其中也不乏一些側重于可讀性的作品（例如kleinberg與tardos合寫的書就是其中之一）。當然，我們在這裡并不是要取代這些優秀的作品，而隻是希望能在此基礎上做一些補充。我希望利用自己多年的算法教學經驗，盡可能清楚地為讀者诠釋算法的工作方式，以及一些需要共同遵守的基本原則。對于一個程式員來說，這種程度的诠釋可能就已經足夠了，讀者需要有更多的機會去了解為什麼相關的算法是正确的、如何将這些算法運用到他們所面對的新問題中去。但這就需要去閱讀一些更形而上的、百科全書式的教科書。我希望這本書能為讀者打下一定的基礎，這将有助于他們了解相關的定理以及其相應的證明。

請注意：

除此之外，市面上還有另一種算法類書籍。它們通常以“（資料結構與）算法（blank版）”為題，這裡的blank通常為作者本人所使用的程式設計語言。有不少這樣的書（而且似乎都是以blank=java的情況為主），但其關注點多集中在與基本資料結構有關的東西上，以至于忽略了某些更為實質性的内容。如果說這是某一門資料結構基礎課程的教科書，或許還可以了解，但對于python程式員來說，學習單向或雙向連結清單并不是一件能讓所有人興緻勃勃的事情（盡管我們在下一章中還是會提到一些）。即便是哈希這樣重要的技術，我們也可以通過python中的字典類型免費獲得相應的哈希表，完全不需要再去考慮重新實作它們。恰恰相反，我将注意力集中在更進階的一些算法。但這樣一來，許多重要的概念在python語言本身或标準庫對相關算法（如查找、搜尋、哈希等）的“黑盒”化實作中被淡化了。為此，我們在文中加入了一些特定的“黑盒子”專欄，以做補充。

當然，本書與那些“java/c/c++/c#”算法流派還有一個顯著的差別，即這裡的blank為python。這使得本書更接近那些與語言無關的算法書（例如knuth、cormon等人以及kleinberg與tardos的作品），這些書常常使用僞代碼來說明問題。這實際上是一種側重于可讀性的僞程式設計語言，因而它不具備執行能力。而可讀性正好是python最顯著的特點之一，是以它或多或少可以被視為是一種具有執行能力的僞代碼。就算我們從沒用過python，也能看懂絕大部分python程式。總之，這本書中代碼示例都是高度可讀的——我們不需要成為python方面專家，也能輕松讀懂這些示例（盡管有時候還是需要讀者去查閱一些與内置函數有關的資料）。當然，您也可以把這些示例當作僞代碼來了解。綜上所述……

算法分析，主要側重于漸近運作時間分析。

算法設計的基本原則。

如何用python描述那些常用的資料結構。

如何用python實作那些知名算法。

python中直接可用的算法，它們通常是語言本身或其标準庫的一部分。

純思想性及形而上的内容（盡管本書會對它們做一些證明，并提供相關的證明示例）。

與數值計算或數學理論有關的算法（隻有第2章中涉及了一些浮點運算）。

并行算法與多核程式設計。

正如大家所知，“用python實作”隻是整個拼圖的一部分。我們所希望的是，讀者能掌握其中的設計原則與理論基礎，以便能設計出屬于自己的算法與資料結構。