算法二  (迭代算法)

    迭代算法的原理很简单，我们以教材中图9.5 所示三点 为例来说明。如果用水平和垂直线段来连接这三点，必然会产生重叠(如图9.5(a))。若在重叠边的一个端点上加一个斯坦纳点 (如图9.5(b))，此时四点组成的最小生成树其长度小于原先三点组成的最小生成树的长度(在矩形距离下)。因此我们可以说，存在重叠边的连接树不可能是矩形距离下的斯坦纳最小树。

    基于这样的原理，我们可以归纳这一算法的基本过程如下：

    (1) 求点集 在矩形距离下的最小生成树。

    (2) 寻求重叠边，在重叠边的端点上寻求可能的斯坦纳点，以消去重叠边，直到没有重叠边为止。

    有兴趣的同学可以自己试着利用这个算法来求问题 B 的第一部分的解。结果详见教科书的图9.7，其中连结两点的边实际上表示的是两点之间的矩形距离，边上的权为两点之间的矩形距离权。

【关闭】