四边形中的最小网络-史坦纳问题

hujunhua

先作出A，B，然后作出C，C是三角形1AB的费马点。

数学星空

zeroieme

依然没有连接方向判别方法

数学星空

其实对于凸五边形内的斯坦纳点(3个 例11#楼中的C,D,E), 11#只是其中一种可能,这取决于第一点C是以凸五边形中的哪个顶点作出(11#是以第1点作出的,类似可以分别以其它点作出点C),最小网络树是取这五种情形中总长最小的一个.
当然,我们可以根据前面的几何运算出各个变量.....只是表达式比较复杂,因为有了11#的简单作图方法,我们只需画图便可量出各个线段的长度,无需复杂的计算.

wayne

13# zeroieme
这可是老大难的题啊

数学星空

关于斯坦纳树问题,有以下三大类经典的斯坦纳树问题:
(1) 欧氏斯坦纳最小树:给定欧氏平面上有限多个结点,求联结所有结点的长度最小网络?
(2)纵横斯坦纳最小树:给定纵横平面上有限多个结点,求联结所有结点的长度最小网络?
(3)网络斯坦纳最小树:给定一个边赋权图(称作网络)G=(V,E)及一个子集合$P sube V$(P
       中的顶点称为结点),求联结P中所有结点的权最小的G的子网络?

由于此问题被广泛的应用于生活中,因此这些问题也被称为经典的难题,实际上主流的算法都是利用智能算法或者近似算法来解决对于规模比较小的问题

在堵丁柱,葛可一,胡晓东 编著的<近似算法的设计与分析>中对此类问题有很多很好的描述,也有了很好的算法来解决此类问题(主要是建立在一个近似算法性能比的基础上)