一個單繞線問題之分枝界定演算法

Abstract

在這篇論文文中，我們提出一個演算法以尋求單繞線問題之精密解。這個演算法的設 計建基於界定分枝的技巧。在演算法執行的每個階段，將產生一個啟發性的繞線以得 到上界，同時使用時在不完整圖形區間表示法中的切割數以得到下界。我們採用外部 軌道先分枝的策略與資料樹的結構以縮減計算時間。如果預定將耗費許多CPU 時間， 此演算法亦提供一個ｅ－最佳化的繞線：最後，一些大小在５０個網路及１５０個端 點以下的測試問題被引用為實驗之計算結果。