草稿:最小曼哈顿网络问题

计算几何与组合优化问题

最小曼哈顿网络问题（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:图论问题