草稿:最小曼哈頓網絡問題

計算幾何與組合優化問題

最小曼哈頓網絡問題（Minimum Manhattan Network，MMN）是計算幾何與組合優化中的經典優化問題：給定平面上的一個有限點集（稱為終端），目標是在只允許使用軸對齊（平行於坐標軸）的線段構成的網絡中，使得任意兩終端之間都存在一條長度等於其曼哈頓距離（L1距離）的路徑，同時使網絡中所有線段長度之和最小。該問題與VLSI布線、城市柵格路網設計以及生物信息學中的結構匹配等應用密切相關，被廣泛研究並被認為是計算上困難的問題。

定義

設點集為$T=\{t_{1},t_{2},\dots ,t_{n}\}$，在平面$\mathbb {R} ^{2}$上採用L1度量。對任意兩點$p=(x_{p},y_{p}),q=(x_{q},y_{q})$，其曼哈頓距離為 $d_{1}(p,q)=|x_{p}-x_{q}|+|y_{p}-y_{q}|.$ 一個曼哈頓網絡是由若干水平或垂直線段組成的集合$N$，使得對每一對終端$(p,q)\in T\times T$，在$N$內存在一條僅沿軸對齊線段行進的路徑，其長度等於$d_{1}(p,q)$。最小曼哈頓網絡問題要求在所有滿足上述可達性的曼哈頓網絡中，最小化總長度 $L(N)=\sum _{e\in N}\mathrm {len} (e).$ 對問題的形式化與路徑性質，參見期刊與會議文獻的定義章節。

問題性質

• 可行性與完備性：在軸對齊網絡中構造兩點之間的曼哈頓路徑需滿足對齊可達性等條件，相關性質可見算法論文中的路徑保持與網絡結構討論。
• 計算複雜性：一般MMN問題被認為是計算困難（與NP-難相關的結論及近似難度討論），研究多集中在近似算法與特殊情形。
• 與斯坦納樹的關係：MMN允許引入斯坦納點，但必須保證所有終端對的路徑為L1最短；與矩形斯坦納樹相比約束更強。

近似算法

由於最優化的計算難度，研究集中在近似解法：

• 近似算法綜述與構造：多篇論文給出常數近似算法並分析時間複雜度；例如針對有向/雙向與一般化MMN的構造與捨入算法。
• 分層與分塊策略：將平面按終端坐標分層或網格分塊，先局部構造再合併全局網絡，以減少冗餘並保持最短路徑性質。
• 後處理壓縮：對初始網絡進行冗餘邊刪除、共享走廊合併與對齊修正，以降低總長度且保持所有終端對的L1可達。

應用

• VLSI與電子設計自動化（EDA）：晶片布線在正交金屬層上進行，MMN結構與實際約束相符，用於估算走線資源與延遲。
• 城市柵格路網設計：在柵格化城市中，軸對齊路段滿足交通組織習慣，可用於在保證點對通達的同時減少總長度。
• 計算生物學與網絡設計：在某些對齊任務中，以L1度量衡量差異並需要軸對齊連接結構，MMN提供理論基線與算法思路。

相關問題

• 矩形斯坦納樹：最小化連接所有終端的總長度，但不要求所有終端對路徑恰為L1距離，約束較弱。
• 最短路徑保持網絡（Distance-preserving network）：在指定度量下保持點對最短距離的網絡構造，與MMN在L1與軸對齊約束下的情形密切相關。

參考文獻

Category:計算幾何 Category:組合優化 Category:圖論問題