algorithm - 切断された線分を通る最短経路

Question

私は非常に一般的な問題を抱えていますが、それを解決するための名前やアルゴリズムが見つかりません。

ユークリッド 2 次元空間の一連の線分が与えられた場合、すべての線分を通る最短経路を見つけるのが好きです。

この問題は、たとえば、ペンを使用して紙に描画し、描画するもの間の無駄な移動時間を最小限に抑える必要があるプロッティング マシンで発生します。

この問題の名前は何ですか? 既知の単純な近似解はありますか?

Answer 1

プロット ペンの描画以外の移動距離を最小化する問題は、線分の端点を頂点とし、描画された線分の両端間にコスト 0 を割り当てる巡回セールスマンの問題に非常に近いものです。

TSPとは異なり、あなたの問題では、線分の途中で線の描画を開始および停止できます。電源アイコンの垂直線 は、一度にすべてではなく、2 つのセグメントに分けて線を引きたい場合の例です。ただ、このようなケースは、描き始めと終わりが違う場合に限られるのではないかと思います。私の推測が正しければ、巡回セールスマンの問題を解くことによって得られる解は、最大でもグラフの幅だけ最適解と異なることになります。

Answer 2

これには、tsp のソリューションを適応させる必要があります。

これは、遺伝的アルゴリズムを介して行うことができます。最適なソリューションが得られるとは限りませんが、通常は短時間で非常に近い結果が得られます。

基本的に、一連のランダムなソリューションから始めます。次に、ソリューションごとにわずかなランダムな変更を加え、移動距離を測定します。最短距離のものを保持します。新しい世代が最適化を提供しなくなるまで、または時間がなくなるまで、このプロセスを繰り返します。