22-铺设电缆-最优工程布线

6.4　铺设电缆——最优工程布线

在实际工程中，铺设电缆等设施时，既考虑障碍物的问题，又要考虑造价最低。随着电子设备的普及，工程中需要大量的电路板。每个电路板上有很多线路，我们在设计电路时，尽可能地节约成本，如果一个电路板省下一分钱，也将是一笔很大的财富。布线问题就是在m×n的方格阵列中，指定一个方格的中点a，另一个方格的中点b，问题要求找出a到b的最短布线方案。布线时只能沿直线或直角，不能走斜线。为了避免线路相交，已布过线的方格做了封锁标记（灰色），其他线路不允许穿过被封锁的方格。