论文部分内容阅读
该文首先提出一个约束最小Ｓｒｅｉｎｅｒ树问题。即考虑欧氏平面上有一直线Ｌ，在直线一侧有ｎ个点，记点集为Ｎ，要在Ｌ上找一个点Ｐ使关于关于Ｎ∪｛Ｐ｝最小Ｓｔｅｉｎｅｒ树长度最短。该文给出了ｎ＝２时的详解，并对ｎ＝３时的情形给出解的一般性描述。鉴于问题的复杂性为ＮＰ－Ｃ，文章给出了一个近似解，并对其性能比给予讨论。