'Saucy' software update finds symmetries dramatically faster
http://www.physorg.com/news132325206.html
June 10, 2008
在 Michigan 大學的電腦科學家開發出一種開放原碼（open-source）軟體，在某些例子中甚至能將尋找複雜等式中對稱的時間，從數日縮減為數秒。
找尋對稱是一種能突顯通往答案捷徑的方法，例如，驗證火車時刻表的安全性、確認軟體與硬體設計中的臭蟲，或著，加速一般搜尋任務。
此演算法是為一種稱為「saucy（鹵莽）」的軟體所進行的更新。這套軟體由研究者在 2004 年開發出來，並與同僚共享。Paul Darga，電機工程與電腦科學系的畢業生，6/10 將在加州 Anaheim 舉辦的 Design Automation Conference（http://www.dac.com/）中呈現此演算法。Darga 的共同作者是 Igor Markov，該系副教授，以及該系的 Karem Sakallah 教授。
這套軟體的應用延伸到人工智慧與後勤（logistics）。它加速基礎電腦科學問題的解法，且能迅速解答所謂的圖自同構問題（graph automorphism problem，http://en.wikipedia.org/wiki/Graph_automorphism）。"在現實生活應用中，我們新演算法解決圖自同構問題的速度如此之快，以致於這種問題開始看起來很容易，" Markov 說。
就某種意義來說，對稱是種可交換的選項，那導致同樣的結果。
在複雜方程式中，對稱指出搜尋解法的反覆分支，那只需要被算出一次。當前尋找對稱的程式有時會花上幾天才得到答案，甚至那時它們還找不出實例來，Darga 說。這種新方法能在數秒鐘內結束，即便那裡有幾百萬種變量。
為了要描繪發現對稱如何能簡化等式，Markov 指向鴿洞原理（pigeonhole principle，又名：鴿籠原理、抽屜原理）。舉例來說，這個原理是指你無法將 10 隻鳥兒放入 9 個鴿洞中（除非牠們有共用）。這個特殊的問題有 9重（9-fold）對稱性，因為那無關每隻鳥佔哪一個洞。總有隻鳥會無家可歸。它也有 10 重對稱性，因為鳥兒們被認為是可交換的。
"如果你要求一部電腦將 20 列火車放入 19 條鐵軌上，計算可能會一直進行下去，" Markov 說。"但如果你使用一種具對稱性破壞（symmetry breaking）的方法，這些例子能在幾秒鐘內解開。"
在火車時刻表與後勤中的對稱性破壞也能夠幫忙算出最短路線（itineraries）。在人工智慧中，能迅速識別對稱性的能力可協助電腦產生一種方案或最佳化的排程。電腦將知道何時任務的次序是可交換的。
這個新演算法開始工作的方法與現存的對稱性破壞軟體相同。它將複雜等式轉換成圖（graph），並在頂點（vertices）的排列中尋找相似性。如同原始版本的 saucy，它在窄化搜尋的同時利用 Darga 所謂的「sparsity（稀疏）」 --「在圖上的每一個節點幾乎都只與其他幾個節點相連」這個事實。
saucy 更新了辨識，（因為）不是只有節點連結屬於稀疏。
原來，大部分重要的對成本身也都是稀疏，因為它們每一次都只涉及到幾個節點而已。其他對稱性能源自於稀疏對稱，而有所區別的對稱數量能隨著系統的大小以指數方式成長。
"正如同雪花，許多在科技與自然中互連的系統都是稀疏的並展現出結構上的對稱，" Sakallah 說。"我們所處理過的網際網路連接圖讓我想起一片巨大的雪花。它有 25 萬個頂點以及 50 萬個邊，不過它比宇宙中的電子展現更多對稱性。"
在不到 0.5 秒內，這套新軟體在全世界路由器的網際網路連接圖中捕捉到 1083,687 個不同的對稱。在這種圖中的對稱性意味著路由器可以被移來移去（be shuffled）而不會改變（網路的）運作。
在這些實驗中，先前的方法在他們給定的 30 分鐘內都無法產生結果。 Darga 說這麼複雜的問題可能會讓較舊程式跑上好幾天才能解出來。在搜尋Illinois 州城市與鄉鎮之間公路網對稱性的過程中，這種新演算法在 0.5 秒內捕捉了 104,843 個對稱，而先前最強的演算法花了 16 分鐘。
這篇論文標題是：「Faster Symmetry Discovery Using Sparsity of Symmetries」，可由下列網址下載：http://www.eecs.umich.edu/~imarkov/pubs/conf/dac08-sym.pdf
此軟體可透過下列網址取得：
http://vlsicad.eecs.umich.edu/BK/SAUCY/
※ 相關報導：
＊ 連結 - 讓60億人串在一起的無形網路
＊ 雪花的數學模型
＊ 數學家揭開古老且普遍的對稱藝術之謎
＊ 一國的「產品空間」決定經濟成長
＊ 史丹佛科學家將 2D 影像變成 3D 模型
＊ 新演算法從 2D 照片重建 3D 景致
＊ 蒼蠅眼可強化機器人視覺
＊ 研究者完成 25 年來首度「網際網路普查」
＊ Network coding 突破網路瓶頸（更新）
＊ 法國科學家計算平均首度通過時間
＊ 蜜蜂的策略能幫助 server 跑的更愉快
＊ 尋找網路的演算法 -- 用於基因或網際網路
＊ 研究者為「電腦蟲」帶來新意
＊ 超立方體能成為奈米電腦的基石
＊ 化學家創造「設計師酵素」
＊ 研究者排除藥物發現的瓶頸
＊ 預測新興傳染病的下一波「熱點」
＊ 工程師激起第一個長壽的奈米泡泡
＊ 衝浪老兄的萬有理論讓物理學家驚嘆
＊ 大霹靂之前：攣生宇宙？
沒有留言:
張貼留言