[洛谷第一篇全繁體休閒娛樂]哈密爾頓迴路的最新研究進展

· · 休闲·娱乐

沒活整了，隨便寫了點東西。

0. 引入

衆所周知，哈密爾頓迴路是一個經典的 NPC 問題，這代表着判定是否存在一個哈密爾頓迴路無法在多項式複雜度內完成。

根據一些做題中的經驗，我們都知道普通哈密爾頓迴路的寫法是 O(2^npoly(n)) 的。而近日，作者發現了關於該問題的一些新解法，或許能突破這一上界。

1. 過程

該做法過程如下：

衆所周知一個圖的哈密爾頓迴路是一個 1\sim n 的排列 p，其中 p_i 和 p_{i+1} 之間有邊相連。

於是我們直接從排列入手。我們知道排列是一個長度爲 n，每個數在 1\sim n 之間的序列。這種序列一共只有 n^n 種，因此我們直接暴力枚舉所有序列並依次判斷合法，複雜度變爲 O(n^n)。

看到這裡，讀者們可能會表示，O(n^n) 不是比 O(2^n) 慢嗎？但是我們接下來將要證明，這個複雜度不僅快於 O(2^n)，而且可以認爲是多項式複雜度。

2. 證明

首先我們需要探究 O(n^n) 和 O(2^n) 的快慢。爲了證明其速度我們順便將 O(n^2) 也列入考慮範圍。

畫出 f(x)=x^x,g(x)=2^x,h(x)=x^2 三個函數的圖像，能夠得到下圖：

三個函數在最右側的豎線略往左處從上往下依次爲 g(x),f(x),h(x)。不難看出，雖然 x^x 最開始較大，但是在 x 持續變化之後來到了 2^x 下面，並且最後直逼 x^2。不難猜測如果我們繼續畫出更右邊的圖像，綠色線會到達紅色線的下方。

這說明在 x 足夠大時，x^x 要比 2^x 快，可能甚至比 x^2 要快。

但是這並不足以說明 x^x 是多項式複雜度。畢竟 NPC 問題的要求就是不能在多項式複雜度內完成判定，我們還是希望能夠說明這一點的。

首先基本的代數技巧告訴我們，x^x 不是初等函數。不過沒關係，我們可以把初等函數都列出來。

顯然的，初等函數中增長最快，值也最大的就是指數函數了。這對應的就是指數級的複雜度。

之後，就不難想到冪函數了。雖然理論上增長速度也是很快的，但是顯然屬於多項式複雜度。

再小的初等函數其實不需要考慮了，因爲我們知道讀入整個圖至少是線性的。那我們已經發現 x^x 比指數級的複雜度都要快，而且和一個 x^2 速度相當甚至更快，這說明 x^x 可以被歸類到多項式複雜度。

這樣我們就說明了 O(n^n) 的速度。

3. 展望

在得到了上述的重要性質之後，我們首先說明了哈密爾頓迴路問題的一個新的解法，而這可能已經突破了以前證明的理論下界。

更進一步的，因爲哈密爾頓迴路是一個 NPC 問題，而我們現在已經找到了一個多項式複雜度的解法，或許這也能對 P=NP 的證明有一些幫助。

總之，這無疑是算法界的一大重要發現。

4. 後記

我真的編不下去了。放兩張圖說明一下為什麼寫這篇專欄吧。

實在難以評價。文化水平還是很重要的。