2D平面にはn個の点があります。ロボットはそれらすべてを訪問したいのですが、水平または垂直にしか移動できません。それがカバーする総距離が最小になるように、どのようにそれらすべてを訪問する必要がありますか？
1 に答える
4
これは巡回セールスマン問題であり、ポイントの各ペア間の距離は| y2-y1 | + |x2-x1|です。（直線距離またはマンハッタン距離と呼ばれます）。これはNP困難であり、基本的には既知の効率的な解決策がないことを意味します。
ウィキペディアでそれを解決する方法。
最も単純なアルゴリズムは、単純なブルートフォース検索です。この検索では、ポイントのすべての可能な順列の距離を計算し、最小値を見つけます。これの実行時間はO（n！）です。これは最大約10ポイントで機能しますが、ポイント数が多いとすぐに遅くなります。
于 2009-12-05T22:43:52.700 に答える