第539章 穀山豐誌村五郎猜想
Jacob Holm和Eva Rotenberg是兩位計算機科學家，2019年10月，他們在arXiv上提交了一篇論文，論文的主題與數學中的“可平麵圖”（planar graph）概念有關。在論文提交後不久，他們突然意識到，這篇論文中所涵蓋的內容，包含了一個很了不起的洞見，可以為改進一個算法問題解決主要障礙。
計算機科學家Eva Rotenberg和Jacob Holm在2019年提交的一篇論文，成為了他們破解一個數學謎題的文章的指引。
近幾十年來，數學家和計算機科學家就一直在努力尋找一個可以用最快速度解決一個圖論問題的算法，我們可以用一個腦筋急轉彎問題來解釋這個圖論問題討論的是什麽。
1913年，《斯特蘭德雜誌》（The Strand Magazine）上刊登了一個叫做“三個公用設施問題（three-utilities problem）”的腦筋急轉彎，問題中有三間房子，以及三種公用設施——水、氣、電。它問的是：如果每一間房子都要與三種公用設施相連，是否可以讓所有的這些連線互相之間不交叉。
三個房子與三種公用設施相連的問題。
用不了多久你就會發現，這個問題中的要求是不可能做到的。
如果用簡單的數學語言來加以說明，可以說這個問題的本質就與圖論中的可平麵圖概念有關。在圖論中，圖形是由連線和節點構成的集合，它們可以用來表示許多事物，從社交網絡到道路係統，再到電路板上的電子連接等等。
由連線與節點組成的圖形的例子。
因此，“三個公用設施問題”在實質上討論的是，對一個圖形來說，如何在連線不交叉的情況下將節點連接；以及如何利用算法，來確保當對一個圖形被更改後，仍然能保持可平麵性。
這種可平麵性具有很強的應用意義，無論是建造巨大的道路網絡，還是設計電子設備中的微小電路板，都需要考慮到線路的交叉問題。以電路板為例，如果圖形不是可平麵的，就意味著兩根線交叉，電路板出現了短路。那麽，當一個可平麵圖被隨機的添加了額外的連線時，是否有算法可以快速判斷新形成的圖形是否仍然維持了可平麵性呢？
這正是許多計算機科學家希望能找到的算法，能幫助他們快速地確定當一個圖形在進行了所需的修改之後，是否仍然保持了可平麵性；且這種算法可以在當圖形隻有部分被改變時，並不需要對圖形的每個部分都進行檢查。
終於在1996年，4名計算機科學家發表了一種測試圖形的可平麵性的算法。可惜的是，這個算法所涉及到的計算步驟非常多，其步驟數量基本上與圖形中的節點數的平方根成正比。作為一個算法，這並不算很高效。而自這一算法被發表以來，一直沒能得到改進。直到現在。
Holm和Rotenberg在翻閱他們去年發表的論文時，驚喜地發現論文中含有一個可得出更好算法的重要見解，解決了改進這個算法時會遇到的一個主要障礙。今年6月，他們提交了一份新的論文，文中詳細描述了一種方法，能指數級地改進檢驗圖形的可平麵性的算法。
在檢查圖形的平麵性方麵，新算法的步驟數量正比於圖形中的節點數的對數的立方，這比1996年的算法要快得多。他們利用了可平麵圖的這樣一個特點，即一個相同的可平麵圖有著多種不同的繪製方式，在不同的繪製方式中，點與點之間的連接仍是相同的，但連線之間的相對位置卻有可能不同。
現在，如果添加一條連接平麵圖中的兩個節點的額外的連線，比如讓這節點1和6相連，那麽假如從A開始，它需要連續翻轉兩次才能使節點1和6的相連不與其他任何邊交叉。
Holm和Rotenberg發現，在2019年的論文中涵蓋了這樣一個信息，利用這個信息，可以為可平麵圖找到“更好的繪製方法”。這裏的更好的繪製方法，指的是當有額外的連線被添加到圖中時，“更好”的繪製方法能比其他繪製方法提供更優的起始位置，使得當額外的連線被添加之後，隻需經過很少步驟的翻轉，就能維持圖形的可平麵性不被破壞的狀況。
當他們很快意識到這一點，就產生了一個概念上的非常簡單的新算法。新的算法在每次執行一次翻轉時，都會生成兩種結果中的一種：要麽是算法找到了一種能維持可平麵性的添加所需邊的方法；要麽是算法得出結論發現沒有可以添加所需邊的方法，於是在下一個翻轉時撤銷上一個翻轉。這對於從事該領域研究的科學家來說，是一個重大的啟發。
新的方法或許目前來看還不夠完美，對於大多數解決現實問題的應用程序來說，它所需要的步驟還是沒有最小化，但這已經是在朝著解決這類問題的最佳可能算法靠近的一個重大突破。對Holm和Rotenberg來說，能夠精進算法固然重要，但其中所涉及的新洞見更讓他們激動，他們相信基於這種理解，很快會有新的概念出現。並最終應用到實際問題中。
而這一概念的發現，也讓許多研究人員開始期待，或許許多構成了謎題答案的要素已經存在，它們正在一堆陳舊的論文中靜靜等待能發現它們的人。何時會出現更快的算法，沒有人知道，但全新的突破可能就藏在意想不到的驚喜中。