そこで、巡回セールスマン問題の 2-opt 改善の説明を探していて、大まかに理解できましたが、1 つのことがわかりません。
生成されたパスの 2 つのエッジが交差している場合、2 つのポイントを切り替えるだけで交差しなくなることを理解しています。ただし、2 つのエッジが交差するかどうかを判断する方法がわかりません。
私の質問を明確にするために、これは私がこれまでに行ったことです:(Javaで行いました)
Pointx 座標と y 座標を持つ都市を表す というオブジェクトがあります。- に含まれる
PointSetのセットを持つ があります。PointsList - Nearest Neighbor アルゴリズムを介してかなり短い方法で PointSet を配置するメソッドが
PointSet呼び出されました。computeByNN()
これで、ソートされた PointSet (最適ではありませんが、まだ短い) があり、2-opt を実行したいと考えています。ただし、どこから始めればよいかわかりません。すべての線分をチェックして交差するかどうかを確認し、交差する場合は 2 点を切り替える必要がありますか? それはヒューリスティックの目的を破り、一種のブルート フォース ソリューションになるような気がします。ツアーの 2 つのセグメントが交差しているかどうかを効率的に確認する方法はありますか?
私の質問が明確でない場合、私は承認します。誰かが私を必要とする場合は、より明確にするために編集しようとします。