1986年ACM圖靈演講:演算法設計

Casimir Kuratowski的一個優美定理指出，一個圖形是平面的，當且僅當它不包含由五個頂點構成的完全圖（K5）或由兩組各三個頂點構成的完全二分圖（K3,3）作為子圖（見圖2）。


**圖2. Kuratowski的「禁止」子圖**

正如A. Jay Goldstein在1963年所指出的，必須確保演算法選擇的環路會產生兩個或更多個段；如果只產生一個段，演算法可能會無限循環。Rob Shirey在1969年提出了一個版本的演算法，它在一個n頂點圖形上運行時間為 O(n^3)。John和我致力於開發該演算法的更快版本。

關於平面圖的一個有用事實是它們是稀疏的：一個n頂點圖形可以包含 n(n - 1)/2 條邊，而一個平面圖形最多只能包含 3n - 6 條邊（如果 n >= 3）。因此，John和我希望（大膽地）設計一個 O(n) 時間的平面性測試。最終，我們成功了。

第一步是確定一個適當的圖形表示法，一個能夠利用稀疏性的表示法。我們使用了一個非常簡單的表示法，包括為每個頂點列出其入射邊的列表。對於一個可能的平面圖形，這種表示法的大小是 O(n)。

第二步是發現如何進行必要的預處理。路徑加法法要求圖形是雙連通的（即沒有移除後會使圖形斷開的頂點）。如果一個圖形不是雙連通的，它可以被分解為最大的雙連通子圖形或雙連通分量。一個圖形是平面的當且僅當它的所有雙連通分量都是平面的。因此，可以通過首先將圖形分解為其雙連通分量，然後測試每個分量的平面性來測試平面性。我們設計了一種在 O(n + m) 時間內找到一個n頂點、m邊圖形的雙連通分量的演算法。這個演算法使用深度優先搜尋，這是一種系統地探索圖形並訪問每個頂點和邊的方法。

我們現在面臨平面性測試本身的問題。有兩個主要問題需要解決。如果將路徑加法法從遞迴改為迭代 формулируем，該方法就變成了嵌入一個初始環路，然後一次添加一條路徑到一個正在成長的平面嵌入中。每條路徑與先前的路徑除了在終點頂點處是分開的。通常有多種方式可以嵌入一條路徑，而後續路徑的嵌入可能會迫使改變先前路徑的嵌入。我們需要一種方法來將圖形分割成路徑，以及一種方法來追蹤迄今為止處理過的路徑可能的嵌入方式。

在仔細研究了深度優先搜尋的特性後，我們開發了一種使用深度優先搜尋在 O(n) 時間內生成路徑的方法。我們最初用於追蹤替代嵌入的方法使用了一種複雜且專門的嵌套結構。為了使這種方法正常工作，路徑必須以特定的、動態確定的順序生成。幸運的是，我們的路徑生成演算法足夠靈活，能夠滿足這個要求，我們得到了一個運行時間為 O(n log n) 的平面性演算法。

我們嘗試將該演算法的運行時間降低到 O(n) 失敗了，於是我們轉向一種稍微不同的方法，其第一步是生成所有路徑，第二步是建構一個圖形來表示它們的成對嵌入約束，第三步是使用兩種顏色對這個約束圖形進行著色，對應於每條路徑兩種可能的嵌入方式。這種方法的問題在於可能存在二次數量的成對約束。獲得線性時間上限需要僅明確計算足夠多的約束，使得它們的滿足能保證所有剩餘約束也得到滿足。發展這個想法導出了一個 O(n) 時間的平面性演算法，這成為了我博士論文的主題。這個演算法不僅理論上高效，而且在實踐中也很快：我的實作，用 Algol W 編寫並在 IBM 360/67 上運行，測試包含900個頂點和2694條邊的圖形約需12秒。這比我在文獻中能找到的任何其他聲稱的時間上限快約80倍。該程式約500行，不包括註釋。

然而，這並非故事的結局。在準備該演算法的期刊發表描述時，我們發現了一種方法，可以避免建構和著色一個圖形來表示成對嵌入約束。我們設計了一種資料結構，稱為「雙疊堆棧」（pile of twin stacks），它可以表示迄今為止處理過的所有可能路徑嵌入，並且易於更新以反映新路徑的添加。這導出了一個更簡單的演算法，其時間上限仍為 O(n)。我的學生Don Woods對更簡單的演算法進行了程式設計，該演算法在 IBM 370/168 上測試包含7000個頂點的圖形只需8秒。程式的長度約為250行 Algol W，其中平面性測試只需約170行，其餘用於實際建構平面表示。

從這項研究中，我們不僅獲得了一個快速的平面性演算法，還獲得了一種演算法技術（深度優先搜尋）和一種資料結構（雙疊堆棧），這些對解決許多其他問題很有用。深度優先搜尋已被用於各種圖形問題的高效演算法；雙疊堆棧已被用於解決排序和識別平面自相交曲線代碼的問題。

我們的演算法並非唯一能在 O(n) 時間內測試平面性的方法。另一種方法，由Abraham Lempel、Shimon Even和Israel Cederbaum提出，是通過一次添加一個頂點及其入射邊來建構嵌入。該演算法的直接實作給出了 O(n^2) 的時間上限。當John和我進行研究時，我們看不到改善這個上限的方法，但後來Even和我以及Kelly Booth和George Lueker的工作，產生了該演算法的 O(n) 時間版本。同樣，該方法結合了深度優先搜尋（作為預處理步驟以確定頂點添加順序）和一個複雜的資料結構，即Booth和Lueker的 PQ-tree，用於追蹤可能的嵌入。（該資料結構本身也有其他幾種應用）。

還有第三種 O(n) 時間的平面性演算法。我最近才發現，一種稱為「手指搜尋樹」（finger search tree）的新型搜尋樹，由Leo Guibas、Mike Plass、Ed McCreight和Janet Roberts在1977年發明，可以用於John和我開發的原始平面性演算法中，將其運行時間從 O(n log n) 改善到 O(n)。推導時間上限需要解決一個分而治之的遞歸關係。手指搜尋樹發明後的幾年裡沒有特別引人注目的應用，但現在有了，例如在排序和計算幾何領域，以及在圖形演算法中。

歸根結底，選擇正確的資料結構對於高效能演算法的設計至關重要。這些結構可能很複雜，可能需要數年時間才能將一個複雜的資料結構或演算法提煉到其精髓。但一個好想法最終總會變得更簡單，並為其最初設計之外的問題提供解決方案。就像數學一樣，電腦科學中看似不同的部分之間存在豐富而深刻的聯繫。

## 資料結構效率與分攤分析

我現在想將重點從圖形演算法轉移到資料結構，稍微思考一下最差情況運行時間是否是衡量資料結構效率的適當標準。圖形演算法通常一次在一個圖形上運行。然而，對資料結構的操作不是孤立發生的；它是一長串類似操作中的一個。在大多數應用中，重要的是整個操作序列所花費的時間，而不是任何單個操作的時間。（實時應用中需要最小化每個單獨操作時間的情況是例外。）

我們可以通過將單個操作的最差情況時間乘以操作次數來估計操作序列的總時間。但這可能會產生一個過於悲觀以至於無用的上限。如果在這個估計中，我們將單個操作的最差情況時間替換為單個操作的平均情況時間，我們可能會獲得一個更緊密的上限，但這個上限取決於概率模型的準確性。這兩種估計的問題在於它們未能捕捉到連續操作可能對資料結構產生的相關效應。一個簡單的例子可以在用於平面性測試的雙疊堆棧中找到：n個操作序列中的單個操作可能需要與n成比例的時間，但n個操作序列的總時間總是 O(n)。在這種情況下，適當的衡量標準是**分攤時間**，定義為在最差情況操作序列中對單個操作進行平均所花費的時間。 [1] 在雙疊堆棧的情況下，每個操作的分攤時間是 O(1)。

[1] 有關此概念的詳細討論，請參閱 R. E. Tarjan，Amortized computational complexity，SIAM J. Alg. Disc. Math. 6, 2 (Apr. 1985)，306-318。

分攤效率的一個更複雜的例子可以在表示不相交集合並執行集合聯合操作的資料結構中找到。在這種情況下，每個操作的最差情況時間是 O(log n)，其中 n 是所有集合的總大小，但每個操作的分攤時間實際上是常數，但理論上隨著 n 增長得非常緩慢（分攤時間是 Ackermann 函數的泛函逆）。

這兩個例子說明了利用分攤分析來對已知資料結構進行更緊密的分析。但分攤分析有更深層次的用途。在設計資料結構以減少分攤運行時間時，我們採取的方法會與試圖減少最差情況運行時間不同。我們無需精心設計一個具有恰到好處屬性的結構來保證良好的最差情況時間上限，而是可以嘗試設計簡單的局部重組操作，這些操作在重複應用時可以改善結構的狀態。這種方法可以產生「自行調整」或「自行組織」的資料結構，這些結構能夠適應其使用情況，並且在一大類競爭結構中具有接近最佳的分攤效率。

## Splay Tree：自行調整式搜尋樹

splay tree 是我與Danny Sleator共同開發的一種自行調整式二元搜尋樹，就是這樣一種資料結構。為了討論它，我需要首先回顧一些關於搜尋樹的概念和結果。一棵二元樹要麼是空的，要麼由一個稱為根的節點和兩棵節點不相交的二元樹組成，這兩棵樹分別稱為根的左子樹和右子樹。左（右）子樹的根是樹根的左（右）孩子。一棵二元搜尋樹是一棵包含來自一個全序集合的項目的二元樹，每個節點包含一個項目，項目按對稱順序排列；也就是說，左子樹中的所有項目都小於根中的項目，而右子樹中的所有項目都大於根中的項目（見圖4）。


**圖4. 二元搜尋樹**
項目按字母順序排列。

儘管平衡搜尋樹具有重要的理論意義，但在實踐中也有缺點。維護平衡約束需要額外的節點空間來儲存平衡資訊，並且需要具有許多情況的複雜更新演算法。如果樹中的項目被訪問的頻率大致均勻，則在實踐中根本不平衡樹更簡單、更高效；隨機插入序列將產生一棵深度為 O(log n) 的樹。另一方面，如果訪問分佈顯著偏斜，那麼平衡樹將無法使總訪問時間最小化，即使在一個常數因子內也做不到。據我所知，實踐中廣泛使用的唯一一種平衡樹是Rudolph Bayer和Ed McCreight的 B-tree，它通常每個節點有遠多於兩個孩子，適合在磁碟等輔助儲存媒體上儲存非常大的資料集。B-tree之所以有用，是因為平衡的好處隨著每個節點的孩子數增加以及最大深度相應減少而增加。在實踐中，B-tree的最大深度是一個小的常數（三或四）。

splay tree 的發明源於我與我的兩個學生Sam Bent和Danny Sleator在1970年代末期在Stanford進行的研究工作。我從Cornell和Berkeley工作一段時間後，回到Stanford擔任教職。Danny和我當時正試圖設計一種計算網路中最大流的高效演算法。我們將這個問題簡化為建構一種特殊搜尋樹的問題，其中每個項目都有一個正權重，並且檢索一個項目所需的時間取決於其權重，權重較重的項目比權重較輕的項目更容易存取。最難滿足的要求是能快速執行劇烈的更新操作；每棵樹都要表示一個列表，我們需要允許列表的分割和串接。Sam、Danny和我經過大量工作後，成功設計了平衡搜尋樹的適當泛化，稱為 biased search trees，這成為Sam博士論文的主題。Danny和我將 biased search trees 與其他想法結合起來，獲得了我們一直在尋找的高效最大流演算法。這個演算法反過來成為了Danny博士論文的主題。這個演算法的核心資料結構，稱為 dynamic tree，有多種其他應用。

biased search trees 和我們最初版本的 dynamic trees 的問題在於它們很複雜。一個原因是我們試圖設計這些結構來最小化每個操作的最差情況時間。在這方面我們並不完全成功；對這些結構的更新操作只有在分攤意義上才具有所需的效率。在1980年底Danny和我都轉到AT&T Bell Laboratories後，他建議可以通過明確地僅尋求分攤效率而不是最差情況效率來簡化 dynamic trees。這個想法自然導致了設計一種「自行調整」搜尋樹的問題，這種樹在分攤意義上能像平衡樹一樣高效。提出這個問題後，我們只花了幾週時間就想出了一個候選資料結構，儘管分析它花費了我們更長的時間（分析仍未完成）。

## Splay Tree 操作

在 splay tree 中，每次檢索一個項目後，都會進行一次樹的重組操作，稱為「展開」（splay）操作。（Splay作為動詞的意思是「展開」）。一次展開操作會將被檢索的節點移動到樹的根部，大約將檢索過程中存取的所有節點的深度減半，並且樹中任何其他節點的深度最多增加兩。因此，一次展開操作會使檢索過程中存取的所有節點在以後更容易存取，而樹中其他節點的存取難度最多略微增加。展開操作的細節如下（見圖6）：要對節點 x 進行展開，重複以下步驟直到節點 x 成為樹根。

**展開步驟。**
應用以下三種情況中適當的一種：
*   **之字（Zig）情況。** 如果 x 是樹根的孩子，則在 x 處進行旋轉（此情況為終端情況）。
*   **之字之字（Zig-zig）情況。** 如果 x 是左孩子，其父節點也是左孩子，或者如果兩者都是右孩子，則先在 x 的父節點處進行旋轉，然後在 x 處進行旋轉。
*   **之字之叉（Zig-zag）情況。** 如果 x 是左孩子，其父節點是右孩子，或反之，則先在 x 處進行旋轉，然後再次在 x 處進行旋轉。


**圖6. 展開步驟的各個情況**
在之字之字和之字之叉情況下，圖示的樹可以是更大樹的一部分。

事實上，在一個 n 節點的 splay tree 中，分攤檢索時間是 O(log n)。Splay tree 甚至有更驚人的理論屬性。對於任意但足夠長的操作序列，splay tree 的效率在一個常數因子內與為最小化給定序列的總檢索時間而專門建構的最佳靜態二元搜尋樹一樣高。Splay tree 在分攤意義上的表現與 biased search trees 一樣好，這使得Danny和我能夠獲得 dynamic trees 的簡化版本，這正是我們最初的目標。

基於這些結果，Danny和我推測 splay tree 在以下意義上是一種普遍最佳的二元搜尋樹：考慮一個固定的 n 個項目集合和一個包含 m >= n 次檢索這些項目的任意序列。考慮任何演算法，它通過從一個初始二元搜尋樹開始，以標準方式從根節點搜尋來執行每次檢索，並間歇性地通過在樹中任何地方執行旋轉來重組樹。演算法的成本是被檢索項目（在檢索時）深度的總和加上旋轉的總次數。我們推測，從任意糟糕的初始樹開始，splaying 演算法的總成本在任何演算法的最小成本的一個常數因子範圍內。也許這個推測太好了，難以成真。支持這個推測的一個額外證據是，使用 splaying 依序訪問二元搜尋樹中的所有項目只需線性時間。

除了其引人入勝的理論特性外，splay tree 在實踐中具有潛在價值。Splaying 易於實作，並且它也簡化了樹的更新操作，例如插入和刪除。Doug Jones 的初步實驗表明，splay tree 在離散模擬系統中實現事件列表的目的方面，與所有其他已知資料結構具有競爭力。它們可能在各種其他應用中很有用，儘管驗證這一點需要大量系統和仔細的實驗。

splay tree 的發展提出了幾個結論。持續研究已經解決的問題，可以帶來重大的簡化和額外的見解。為追求分攤效率而設計，可以帶來簡單、自適應的資料結構，它們在實踐中比其最差情況下高效的同類結構更有效。更廣泛地說，選擇的效率衡量標準指出了解決演算法問題應採取的方法，並指導了解決方案的發展。

## 演算法設計的未來展望

我想就我認為演算法設計領域的需求發表幾點評論。說我們需要更緊密的理論與實踐結合，這聽起來老套，但卻是事實。實踐世界為研究人員提供了豐富多樣的問題來源。研究人員不僅可以為實踐者提供針對特定問題的實用演算法，還可以提供在各種應用中有用的廣泛方法和通用技術。

有兩件事將支持理論與實踐之間更好的互動。一是對演算法進行更多的實驗分析工作。演算法的理論分析建立在堅實的基礎上。實驗分析則不然。我們需要一個有紀律、系統化、科學的方法。實驗分析在某種程度上比理論分析困難得多，因為實驗分析需要編寫實際的程式，而且很難避免通過編碼過程或樣本資料的選擇引入偏差。

另一個需求是一種程式語言或標記法，它既易於人類理解，又能在機器上高效執行。傳統的程式語言強制規定了太多不相關的細節，而較新的超高階語言則帶來了具有挑戰性的實作任務，這需要對資料結構、演算法方法及其選擇進行更多的工作。

現在，理論和實踐社群對於並行性問題存在巨大的熱議。對理論家來說，並行性提供了一種新的計算模型，從而改變了理論分析的基本規則。對實踐者來說，並行性提供了在解決某些類型問題時實現巨大加速的可能性。然而，並行硬體並不會使理論分析變得不重要。事實上，隨著可解決問題的規模增加，漸近分析變得越來越重要，而不是越來越不重要。新的演算法將被開發來利用並行性，但為序列式計算開發的許多想法也將轉移到並行環境中。重要的是要認識到並非所有問題都適合並行解決。理解並行性的影響是當今演算法設計領域許多研究的核心目標。

我進行演算法設計研究不僅因為它提供了影響現實世界計算的可能性，還因為我熱愛這項工作本身，它揭示的問題與解決方案之間豐富而令人驚訝的聯繫，以及它提供了一個與富有創造力、有啟發性和深思熟慮的同事共同發現新思想的機會。我感謝 Association for Computing Machinery 和整個計算社群給予我的這個獎項，它不僅認可了我自己的想法，也認可了我曾有幸與之共事的人們的想法。他們人數眾多，無法在此一一列舉，但我要感謝他們所有人，特別是John Hopcroft和Danny Sleator，感謝他們在這個發現過程中分享了他們的想法和努力。

---

CR 分類和主題描述：
*   A.0 [General Literature]: General--biographies~autobiographies
*   F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems
*   G.2.2 [Discrete Mathematics]: Graph Theory
*   K.2 [Computing Milieux]: History of Computing--people

通用術語：
*   Algorithms
*   Design
*   Performance
*   Theory

額外關鍵詞和詞組：
*   John E. Hopcroft
*   ROBERT E. TARJAN
*   Turing Award

作者現任地址：
*   ROBERT E. TARJAN, Computer Science Dept., Princeton University, Princeton, NJ 08544;
*   and AT&T Bell Laboratories, Murray Hill, NJ 07074.

---

允許複製本資料的全部或部分，無需支付費用，前提是複製不用於直接商業利益，顯示 ACM 版權聲明以及出版物的標題和日期，並註明複製已獲得 Association for Computing Machinery 的許可。如需以其他方式複製或重新出版，則需支付費用和/或特定許可。