习题四解答
4. 已知点、、和点，试求连接这四个点在矩形距离下的斯坦纳最小树。
解：可用近似算法来求解。
先将4个点按坐标由小到大依次排序为、、、。然后按近似算法的步骤，用折线连接这4个点得树(见图2)，其矩形距离权为29。
【关闭】
、
、
和点
，试求连接这四个点在矩形距离下的斯坦纳最小树。、、和点，试求连接这四个点在矩形距离下的斯坦纳最小树。
坐标由小到大依次排序为
、
、
、
。然后按近似算法的步骤，用折线连接这4个点得树
(见图2)，其矩形距离权为29。