Abstract
在這篇論文中, 我們提出了一個新的演算方法，稱為一般化分割解決方法。我們用這個方法解決三個知名的問題：(一) P個圓中心問題, (二) P個離散中點問題, (三)旅行推銷員問題。這三個問題都是定義在平面圖上的。對第(一)個問題, 以前最好的演算方法可以在0(n logn)才能解決。第(三)個問題,以前是0(n 2 )才能解決。在這篇論文中，我們解決第(一)、(二)和(三)個問題, 分別用了0(n ), 0( )和0( )的時間。很明顯的，用我們的方法解決這些問題，比用以前的方法快了很多。我們所用的分割法，和以前的分割法 (divide-and-conquer) 不同之處在於: 傳統的分割法，只分割一次，以後各自求解，合起來就是全部的解。而我們的分割法，分割非常多次，從各種角度將問題分割；而分割後只有其中一組分割是正確的。因此我們將分割後，各個小問題各自求解的同時將解答最好 ( the solution with smallestcost) 合起來就得到我們所要的最佳解。我們以前知道有許多的問題是很難用傳統的分割法 (traditional divide-and-conq-er) 求出解來，如很多 NP-hard的問題。可是套用我們所提一般化的分割后解決法 (Generalized divide-and-conquer) 就可以解決這一類很難的問題了。我們的方法主要引用 Miller 在 1986 年所提的Simple cycle Separator Theorem。其方法可以在平面圖上找出很好的分割, 因此我們所解決的問題，目前都還是限制在平面圖上，我們相信或許以後可以應用在一般的圖上 (general graph)。