要素が複数の関係を持っているときにセットをソートする方法

Question

要素間の関係が互いに矛盾する場合、ある種の拡張配列並べ替えを実行するアルゴリズムを探しています。

ので、我々は

に関係が間に画定されたMからなるセットR（関係）があり... N項目I1からなるセットI（アイテム）を有しますの項目は、

であり、その関係は互いに矛盾している可能性があります。たとえば、1つの関係ではA>Bと他のth A<B。

r1:i1<i35 

r2:i100<i4 

... 

rm:i45>i3 

概して、RとM（セットのサイズ）は、任意の正の整数であることができます。

タスクはそう項目は、私はアルゴリズムを探しています（関係に基づいて）好ましく下のものは...高いものの前に

を行くように行くIを並べ替えることです可能な限り「最適な」順序に近いようにセットをソートします。私はこのような問題を解決するためのよく知られたアルゴリズムがなければならないと思います。

ありがとうございます！

Answer 1

特定の順序の品質を測定する最も賢明な方法は、それが違反する特定の関係の数であると思います。このメジャーを使用する場合、問題は(Minimum) Feedback Arc Setと同じです。残念ながら、この問題はNP困難であるため、効率的な（多項式時間）アルゴリズムは存在しない可能性があります。

フィードバックアークセットの問題では、有向グラフが与えられ、削除された場合、グラフのすべてのサイクルを破壊するエッジの最小サイズのセットを見つけるよう求められます。

これがあなたの問題にどのように対応しているかを見るには、各項目をグラフの頂点として表現し、各関係を2つの頂点間の有向枝として表現できることに注意してください。このグラフにサイクル（）がある場合にのみ、競合が発生します。つまり、2つ以上の別個の頂点v_1、v_2、...、v_kの順序付きリストがある場合、v_i < v_ +1）、すべてのi < k、v_k < v_1。少なくとも1つの制約に違反することなくこれらのk個の頂点を順序付けることは不可能である。逆に、サイクルが存在しない場合、すなわち、グラフがdirected acyclic graphである場合、topological sortは、制約条件に違反する有効な順序を素早く（線形時間内に）見つけることができる。したがって、フィードバックアークセットのサイズは、制約に違反することなくオーダーすることができるグラフを取得するために削除する必要のある最小のエッジ数です。つまり、最小限のエッジ数をに変更する必要があります任意注文します。