算法一  (精确法)

    这一算法的基本步骤是：

    (1) 求固定点集 在矩形距离下的最小生成树 和它的费用。

    (2) 添加可能的虚拟点集 ， 内点的数目不超过 ，，其中为所有可能的虚拟点组成的集合，求点集 在矩形距离下的最小生成树 和它的费用，比较 和 的费用，留下费用较小的一个树，记为 。

    重复步骤(2),直到点集取完所有可能的 种不同情况为止。最后得到的树 即为要求的斯坦纳最小树。

    这个算法有点类似于穷举法，取遍了所有可能的虚拟点集 ，故计算量相当大。在这个算法中，可能的斯坦纳点集的个数 ，其中 为固定点集 中各点的不同 坐标的个数，为 中各点的不同 坐标的个数，为 中点的个数。对于我们所研究的通讯网络的最小生成树问题而言， 所以可能的斯坦纳点集的个数 ，因此所有可能的虚拟点组成的集合数为 。这是相当大的一个数字，有这么多种不同的虚拟点集 的取法，可见这个算法用起来相当复杂。

【关闭】