1
次の問題のアルゴリズムまたは関連する作業はありますか？最小限の移動で交差点をなくすために線分を移動するにはどうすればよいですか？
2次元の線分の集合が与えられている場合、全体の動きを最小限に抑えるために線分（水平または垂直）を移動して交点を削除する方法はありますか？終点の交差点を許可することができます。
A
答えて
0
あなたは、セグメントの動きの数を最小限にしたい場合：
あなたはグラフの問題に線分の問題を変換することができますに： 各セグメントは、グラフの頂点であるとあれば、2つの頂点間のエッジがあります2つのセグメントが互いに交差する。すべてのエッジの少なくとも1つの端点を含む頂点の最小数を探したいとします（これらのすべてのセグメントを移動すると交差がなくなるためです）。これは頂点カバーの問題ですが、残念ながらNPハードですが、近似アルゴリズムがあります。
関連する問題
- 1. 倉庫間の移動品の移動距離を最小限に抑えるにはどうすればよいですか？
- 2. スペースがないときに浮動小数点数を強制的にリサイズするのではなく、浮動小数点数を浮動小数点以下の表の下に移動するにはどうすればよいですか？
- 3. iOSでGoogleマップの移動に伴いマーカーを移動するにはどうすればよいですか？
- 4. 明示的な移行で自動移行をキャプチャするための最小限の方法ですか？
- 5. 限られたエリアでのみ画像を移動するにはどうすればよいですか？
- 6. SciPy最小化：有限差分Jacobianの値を印刷するにはどうすればよいですか？
- 7. Amazonのマイクロインスタンスを小さなインスタンスに移動するにはどうすればよいですか？
- 8. 最初のクリックでスライドを移動させ、最初のクリックで左に動かないようにするにはどうすればよいですか？
- 9. C++でポインタを移動するにはどうすればよいですか？
- 10. IntelliJでツールバーを移動するにはどうすればよいですか？
- 11. node.jsでファイルを移動するにはどうすればよいですか？
- 12. iPhoneでMkMapView.userLocationを移動するにはどうすればよいですか？
- 13. フッターを右に移動するにはどうすればよいですか？
- 14. イメージファイルをフォルダに移動するにはどうすればよいですか？
- 15. ボタンにカーソルを移動できないようにするにはどうすればよいですか？
- 16. デスクトップツールバーの下でプログラムウィンドウを移動しないようにするにはどうすればよいですか？
- 17. ジャイロやエンコーダをロボットの直線移動に使用するにはどうすればよいですか？
- 18. 部分的なメソッドの他の部分に移動するにはどうすればいいですか？
- 19. pygameでキャラクターが移動できる場所を制限するにはどうすればよいですか？
- 20. リストアイテムを移動するにはどうすればよいですか？
- 21. bazelビルドターゲットを移動するにはどうすればよいですか？
- 22. アクティビティインジケータを移動するにはどうすればよいですか？
- 23. Googleマップを移動するにはどうすればよいですか？
- 24. ツールチップを移動するにはどうすればよいですか？
- 25. スクイーク - サークルを移動するにはどうすればよいですか？
- 26. Androidビューの原点を中心に移動するにはどうすればよいですか？
- 27. 浮動小数点数を制限値以下にクリップするにはどうすればよいですか？
- 28. Richfaces popupPanelがJavaScriptで移動されないようにするにはどうすればよいですか？
- 29. pygameで多くの移動可能なテキストボックスを作成するにはどうすればよいですか？
- 30. Perlデバッガで命令点を移動するにはどうすればよいですか？
どのように最小限に定義しますか？最小の移動回数または距離の距離/二乗の合計の最小値？ – biziclop
また、ラインエンドポイントを別々に移動できますか？または、ラインの長さと向きがconstですか？ – LumpN