diam 钻矿问题 已探明某钻石矿区中钻石的分布情况，如图1 所示。要开采出全部钻石就要挖掘通往所

有钻石埋藏地点的矿道。矿道可以沿着东南西北4个方向挖掘。每一矿道可以连接多个钻石

埋藏点。按照矿道施工要求，可以平行开挖矿道，但不允许交叉。钻矿问题要求对于给定的

钻石分布，设计一个矿道长度总和最小的挖掘矿道方案-diam diamond mine issue has proven a diamond mine in the diamond distribution, shown in Figure 1. All diamonds must be mined diamond mining leading to the burial sites of all the mine shafts. Old Mine Road, four directions along the excavation. Each channel can connect more than one diamond mine buried points. Mine Road construction in accordance with the requirements of mining can be parallel to the open road, but not cross. Diamond mine for a given problem requires the diamond distribution, to design a channel length of the sum of the smallest mine ore mining road program