1

次の問題に対するアルゴリズムまたは関連する作業はありますか?

2Dの一連の線分が与えられた場合、線分を(水平または垂直に)移動して交差をなくし、全体的な動きを最小限に抑える方法は? エンドポイントでの交差は許可できます。

4

1 に答える 1

0

セグメントの移動回数を最小限に抑えたい場合:

線分の問題をグラフの問題に変換できます。各線分はグラフの頂点であり、2 つの線分が互いに交差する場合、2 つの頂点間にエッジがあります。すべてのエッジの少なくとも 1 つの端点を含む頂点の最小数を見つけたいと考えています (これらのセグメントをすべて移動すると、交点がなくなるため)。これは頂点カバーの問題で、残念ながら NP 困難ですが、近似アルゴリズムは存在します。

参照: http://en.wikipedia.org/wiki/Vertex_cover_problem

于 2011-04-08T14:24:32.120 に答える