algorithm - 幾何学的な線を接続するためのアルゴリズム

Question

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

Answer 1

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

代わりに近似解を試す必要があります。ウィキペディアを参照してください。