單列繞線之演算法

Abstract

當系統複雜而龐大時，自動化的製作多層印刷電路板更顯得重要。製作印刷電路板最 耗費精神的步驟就是繞線工作。 本文所討論的單列繞線是多層印刷電路板燒線工作的重要環節。 本文首先略述一些己發表的演算法，按著舉出反例以證明唐（音譯）的演算法不能達 到最佳化的目標。然後提出區域範圍處理的觀念，列舉區域範圍可繞性的分及必要條 件，並且發展出一個有效率的、直覺的演算法以求得更接近最佳化的結果。