算法三  (近似算法)

    (1) 将点集 中所有点 按 坐标大小有效到大排序为。为叙述方便起见，这 个点依次称为点1，点2，，点。

    (2) 用折线(先水平后垂直)连接点1和点2。

    (3) 如果点1，点2，，点已连接得到树 。在 上找点 (不必为 中的点)使点与点 的折线距离最小。连接 和点得树 。

    (4) 当 时，连接完毕得到树 。

    (5) 按实际情况进行适当的调整。

    对于1991年美国数学模型的通讯网络问题B，各步骤为：

    (1) 将9个点按坐标由小到大依次排序为a、b、i、c、d、f、h、e、g，分别标为1、2、3、4、5、6、7、8、9。

    按步骤(2)到步骤(5)，用折线连接这9个点得到树，其矩形距离权为96(见下图)。

【关闭】