幾何学的線を結ぶためのアルゴリズム

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

2010-11-23 surana4u

私は間違っているかもしれませんが、これはTraveling Salesmanの問題のようなものです。 –

はい、確かにそれのように聞こえます –

この場合、解決する前に、今後の解決策を得るために、旅の未来の問題を解決する必要があります。 –

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

代わりに近似解を試してください。wikipediaを参照してください。

2010-11-23 12:06:58 ybungalobill

さて、ここにお尋ねするのは最初のショットです –

特定の解決策を教えてください。 – surana4u

@ surana4uはい、私が指摘したウィキペディアの記事では、正確な解決策と正確ではない解決策の大きなリストがあります。 – ybungalobill

幾何学的線​​を結ぶためのアルゴリズム