algorithm - 是否有一种链接点的算法，可以最小化曼哈顿长度？

Question

我正在尝试链接平面中的点，即绘制图形，但仅使用轴对齐的线。我找到了 KDTree 算法

非常有希望并且接近我需要的东西，但它并不能确保细分尽可能小。我正在寻找的结果更接近

I have also read up on https://en.wikipedia.org/wiki/Delaunay_triangulation because initially, I thought that would be it; but it turns out its way off: - based on circles and triangles - traces a perimeter - nodes have multiple connections (>=3)

Can you point me towards an algorithm that already exists? or can you help me with drafting a new algorithm?

PS: Only 1000-1100 points so efficiency is not super important. In terms of Goals and Costs, reaching all nodes is the Goal and the length of all segments is the Cost.

标签： algorithmtreegeometry

Answer 1

感谢MBo，我现在知道这被称为“施泰纳树问题”。这是 1992 年的一本书（同名）的主题，证明这是一个 NP 难题。

这是它的直线变体。有一些已知的近似算法或启发式算法可以（帮助）解决它。

（HAN、HAN4、LBH、HWAB、HWAD、BEA 列在 https://www.sciencedirect.com/science/article/pii/0166218X9390010L内）

我还没有发现任何“从业者”可能能够实际使用的东西。还在寻找。