當時稚嫩的大學專題，來自ICCAD 2017年B題目。

• 學生：陳佳琳、劉湘怡
• 指導教授：鄭維凱
• 完整書面報告請見：pdf

起源： 在 IC 設計繞線（routing）時，為了節省成本及避免障礙物干擾，希望連接的 線路能越短越好。以此為背景，此專題實作的過程我們討論了各種可能，運 用資料結構及演算法，以及曾經學過的數學方法，達到線路之成本最小化。

• 此專題配合 2017 國際積體電路競賽 ICCAD 之 Problem B 做延伸。
• 將所有給定的藍色矩形相連接、並避免經過灰色矩形。
• 層與層間用給定的 via 或自訂 via 連接。
• 根據題目給的公式算出 cost，cost 越小分數越高。

• Overall Cost = ∑Cost(Pq)

• 若 Pq是 H-line 或 V-line，Cost(Pq)即為 H-line 或 V-line 的長度。

• 若 Pq是 via，Cost(Pq) = Cv。

• 目標是將 overall cost 最小化

• 其中還有一些路徑是不合法(invalid)的，如：

我們針對此題目提出一些原創方法，詳見：pdf

在 via 之 cost 小於 100、layer 層數超過三層的情況下，雖然使用大量 via 造成 via 之 cost 增加，但整體 cost 比起層層之間只有一條 via來的好。