Erstellen einer Gesamt- oder Teilbestellung aus einer inkonsistenten Beziehung
Stellen Sie sich vor, ich möchte eine Gesamtreihenfolge aus einer Reihe von Elementen erstellen. $E$Die Vergleichsfunktion liefert jedoch nicht deterministische Ergebnisse. Ich erstelle eine Liste von Elementpaaren (e, e) durch wiederholte Anwendung der Vergleichsfunktion, so dass jedes Element in der Menge mindestens einmal dargestellt wird.
Wie kann ich diese Eingabe verwenden, um eine Gesamtbestellung zu erstellen? Welche Klasse von Algorithmen kann hier angewendet werden?
Zur Verdeutlichung werde ich ein konkretes Beispiel geben.
Was sind die besten Pizzabeläge?
Meine Reihe von Elementen $E$ Enthält einige beliebte Pizzabeläge: Peperoni, Käse, Pilze, Ananas, Paprika, Oliven.
Dann wähle ich für jeden meiner Freunde zufällig große Teilmengen von Belägen aus und fordere meinen Freund auf, sie vom Besten zum Schlechtesten zu ordnen. Meine Freunde antworten pflichtbewusst und erstellen die Eingabe für meinen Algorithmus:
- Käse, Peperoni, Oliven
- Käse, Ananas, Pilz, Oliven
- Paprika, Pilz, Olive
- Peperoni, Käse, Oliven
- Käse, Paprika
Hier scheint es eine unscharfe Reihenfolge zu geben (alle sind sich einig, dass Oliven die schlechtesten sind), aber meine Freunde sind sich nicht einig, welches das bessere Pizzabelag ist: Käse oder Peperoni. In Anbetracht dessen, wo Elemente in den Eingaben vorkommen und wie häufig sie auftreten, würde ich wahrscheinlich eine Bestellung wie diese erstellen.
- Käse> Peperoni> Paprika> Ananas> Pilz> Olive
Ich bin mir nur nicht sicher, wie ich das formalisieren und für viel größere Eingaben verwenden soll.
Ich denke, die Lösung beinhaltet wahrscheinlich Diagramme und gewichtete Kanten, aber ich bin nicht ausreichend mit Diagrammalgorithmen vertraut, um zu erkennen, ob dies ein benannter Untersuchungsbereich ist. Ich bin bereits auf "topologische Sortierung" gestoßen, aber das funktioniert nur für gerichtete azyklische Graphen, und ich bin speziell an Eingaben interessiert, die keine DAG erzeugen können.
Mir ist auch aufgefallen, dass dieses Problem der Abstimmung für gewählte Vertreter ähnelt. Ist es tatsächlich dieselbe Problemklasse?
Antworten
Es ist schwer zu sagen, ohne mehr Kontext und mehr Modellierung. Es werden einige Annahmen erforderlich sein, wie sich die Ergebnisse der Vergleichsfunktion auf die (versteckte) gewünschte Gesamtreihenfolge beziehen.
Möglicherweise möchten Sie das Bradley-Terry-Luce-Modell . Wenn ja, gibt es viele Standardalgorithmen. Siehe auchhttps://cs.stackexchange.com/a/85204/755.
Möglicherweise möchten Sie ein Rangsystem wie Elo usw.
Möglicherweise möchten Sie ein Ranglisten-Abstimmungssystem wie IRV, Condorcet-Methode, Borda-Zählung oder eines von vielen anderen. Sie alle haben verschiedene Mängel und Kompromisse. Es gibt einen Beweis dafür, dass kein System alle Eigenschaften haben wird, die wir uns wünschen könnten - siehe z. B. den Satz von Arrow und das Problem der Nichttransitivität (selbst wenn jede der individuellen Präferenzen Ihres Freundes transitiv ist, dh eine Gesamtreihenfolge) Es gibt keine Garantie dafür, dass es eine globale Gesamtbestellung gibt, die mit allen übereinstimmt.