wie man einen Satz sortiert, wenn Elemente mehrere Beziehungen miteinander haben

Question

Ich bin auf der Suche nach einem Algorithmus, um eine Art erweiterte Array-Sortierung durchzuführen, wenn Beziehungen zwischen Elementen einander widersprechen können.

so haben wir eine Reihe I (Artikel), bestehend aus n Artikel i1 ... in

Es gibt eine Reihe R (Beziehungen), bestehend aus m Beziehungen, die zwischen Artikel in I

die Beziehungen können einander widersprechen, so dass zB eine Beziehung besagt, dass A>B und die anderen th um A<B.

z.B.

r1:i1<i35 

r2:i100<i4 

... 

rm:i45>i3 

Allgemeinen r und m (Größen von Sets) kann eine beliebige positive ganze Zahlen sein.

die Aufgabe zu sortieren ich so die Elemente so gehen, dass vorzugsweise die unteren (basierend auf Beziehungen), bevor höhere diejenigen gehen ...

Ich suche nach einem Algorithmus Dadurch wird die Menge so sortiert, dass sie der "optimalen" Reihenfolge möglichst nahe kommt. Ich denke, es muss einen wohlbekannten Algorithmus geben, um solche Probleme zu lösen.

Danke!

Answer 1

Ich denke, der beste Weg, um die Qualität einer bestimmten Reihenfolge zu messen, ist die Anzahl der gegebenen Beziehungen, die es verletzt. Wenn Sie sich für die Verwendung dieser Kennzahl entscheiden, entspricht das Problem (Minimum) Feedback Arc Set. Unglücklicherweise ist dieses Problem NP-schwer, so dass wahrscheinlich kein effizienter (polynomialer) Algorithmus existiert.

Im Feedback-Arc-Set-Problem erhalten Sie ein gerichtetes Diagramm und werden aufgefordert, eine Mindestgröße von Kanten zu finden, die, wenn sie gelöscht werden, alle Zyklen im Diagramm zerstören würden.

Um zu sehen, wie dies Ihrem Problem entspricht, beachten Sie, dass wir jedes Element als einen Eckpunkt in einem Diagramm und jede Beziehung als eine gerichtete Kante zwischen zwei Vertices (z. B. auf das kleinere) darstellen können. Es gibt einen Konflikt, wenn und nur wenn in diesem Graphen ein Zyklus vorliegt - das heißt, wenn es eine geordnete Liste von 2 oder mehr verschiedenen Scheitelpunkten v_1, v_2, ..., v_k gibt, so dass v_i < v_ (i +1) für alle i < k, und auch v_k < v_1. Es ist unmöglich, diese k Ecken zu ordnen, ohne mindestens eine Beschränkung zu verletzen. Umgekehrt, wenn kein Zyklus existiert - das heißt, wenn der Graph ein directed acyclic graph ist - dann kann topological sort schnell (in linearer Zeit) eine gültige Reihenfolge finden, die keine Beschränkungen verletzt. Daher ist die Größe eines Feedbackbogens die kleinste Anzahl von Kanten, die Sie entfernen müssten, um einen Graphen zu erhalten, der ohne Verletzung einer Einschränkung bestellt werden kann - oder äquivalent die kleinste Anzahl von Kanten, die in verletzt werden müssen alle Bestellung.