幾何学線を接続するためのアルゴリズム - アルゴリズム、幾何学、計算幾何学、グラフアルゴリズム

私は3Dでn個の幾何学的線​​を開いています。 線の終点間の追加の線の最小長さの基準に基づいて単一線に結合する必要があります。最小の複雑さを持つアルゴリズムを提案してください。

回答：

最もよく知られているアルゴリズムは、O（2ⁿ）時間。 Andrewがコメントに言ったように、これは旅行のセールスマン問題のより一般的なバージョンです。あなたがより良いアルゴリズムを見つけたら、あなたは$ 1000000の賞を授与されます。

代わりに近似解を試す必要があります。 ウィキペディア.