一個圖形上史丹納問題之分枝界定演算法

Abstract

此篇論文中，我們提出一個演算法來處理無向圖中史丹納問題的精確解。這個演算法 是以分枝界定的技巧來完成。它的上界是經由裁剪最小擴張數而獲得，而下界是由sh ore 所提出。為了增快執行速度，找上界時利用啟發性的技巧。這個演算法所解的問 題可達３０個點４３５條線之多。