Ich habe eine Reihe von Reviewern, die eine Menge von n Objekten bewerten. Jeder Prüfer erstellt unabhängig eine geordnete Liste der Objekte, die er oder sie auswählen möchte. Das Ziel besteht darin, eine Liste zu erstellen, die die Sortierung der verschiedenen geordneten Listen darstellt. Wir können davon ausgehen, dass der Standpunkt jedes Rezensenten gleich gewichtet ist.
Dies unterscheidet sich von den meisten zusammenführenden und geordneten Listenfragen dadurch, dass es keine globale Reihenfolge gibt. Ein Rezensent kann A & gt; B, während ein anderer B & gt; A. Wie bereits erwähnt, wird jedes Objekt nicht unbedingt von jedem Rezensenten bewertet.
Mein aktueller Gedanke ist es, die Liste jedes Reviewers in eine Menge geordneter Tupel für jedes der m * (m-1) * .5 eindeutigen Paare von Einträgen in der Liste zu zerlegen, wobei m die Anzahl der bewerteten Objekte ist. Nimm nun alle Tupel von allen Reviewern. Finde für eine gegebene Kombination (a, b) alle solche Tupel und nimm die Mehrheit der Stimmen (der Stimmberechtigten) als den Determinator davon, ob ein & lt; b.
Jetzt habe ich eine Reihe von geordneten Tupeln, die die Weisheit aller darstellen. Aber wie mache ich daraus eine geordnete Liste? Ich kann mit einem zufällig ausgewählten Paar von Objekten beginnen und sie ordnen, dann einen weiteren in der richtigen Reihenfolge hinzufügen, aber die Ausgabe hängt davon ab, mit welchem ich anfange. Auch dort können Schleifen sein.
Ich würde mich über irgendwelche Ideen freuen.
Eine Lösung, die elegant aussieht und immer noch das tut, was sie tun muss, wäre, jede Bestellung in eine Bewertung von 1 bis 0 zu konvertieren, wobei 1 der erste (oberste) bewertete Artikel in der Liste eines bestimmten Rezensenten und 0 der letzte ist (unterer Eintrag) und alle dazwischen liegenden Punkte erhalten eine linear skalierte Punktzahl. Wenn also Rezensent 1 nur 3 Elemente rankt, erhält er für diese Liste Werte von 1, 0,5 und 0. Dann nimmt man einfach die durchschnittliche Punktzahl jedes Elements, um eine sortierte Liste zu erstellen. Krawatten könnten durch die Anzahl von "Bewertungen" für einen Artikel unterbrochen werden (so dass ein Artikel, der von 3 Prüfern einstimmig als bestes markiert wurde, in der endgültigen Liste höher erscheint als ein Artikel, der von 2 Prüfern einstimmig als bestes markiert wurde, etc.) >
Ihre Anforderung "Das Ziel besteht darin, eine Liste zu erstellen, die die Sortierung der verschiedenen geordneten Listen darstellt. Wir können davon ausgehen, dass der Standpunkt jedes einzelnen Prüfers gleich gewichtet ist." wird definitiv von diesem einfachen Algorithmus erfüllt, aber oft haben solche Probleme etwas komplexere Anforderungen, wenn man sich erst einmal damit beschäftigt.
Der Problemraum, den Sie navigieren, ist im Wesentlichen (isomorph zu) einer Teilmenge der Wahltheorie, dem Teil, in dem sowohl die Abstimmungen als auch die Ergebnisse geordnete Kandidatenlisten sind.
Sie könnten davon profitieren, Folgendes zu lesen:
Basierend auf meinen Kenntnissen der Wahltheorie werde ich Ihnen eine Empfehlung geben: Wenn Sie vernünftigerweise glauben, dass ein O (n 3 ) Algorithmus für Ihren bestimmten Datensatz geeignet ist, probieren Sie < a href="http://de.wikipedia.org/wiki/Schulze_Methode"> Schulze-Methode . Ansonsten ist Borda Count die einzige gelistete Methode, die in O (n) Zeit läuft und eine Rangfolge als Stimmzetteleingaben annimmt, also bleiben Sie dabei.
Das Zusammenführen von Rankings ist etwas nicht trivial. Ich denke, vielleicht müssen Sie eine klarere Vorstellung davon haben, was Sie unter "die Zusammenstellung der geordneten Listen" verstehen - d. H. Welche Eigenschaften möchten Sie haben?
Siehe zum Beispiel diese CS Kursnotizen von Cornell . Angesichts einiger einigermaßen vernünftiger Eigenschaften, die das globale Ranking haben sollte, ist es tatsächlich unmöglich, einen Algorithmus zu erstellen, der diese Eigenschaften definitiv erfüllt. Sie müssen möglicherweise Kompromisse bei dem eingehen, was Sie als angemessene Eigenschaften Ihres globalen Rankings akzeptieren.
Artikel: Herzog für immer Beben UT3 Duke3d Halo
%Vor%Logischer Abzug:
Am meisten gewählt:
Entfernen Sie #, die widersprechen, indem Sie widersprüchliche Paare erstellen und in = konvertieren Akzeptiere%, die paarweise übereinstimmen. Gruppe mit alles zählen. Wenn es & lt; und = Widersprüche das Wahre ist dasjenige mit mehr Zählung.
Gefiltert und dann nach Logik sortiert:
Die Sortierung sollte jedoch durch die Anzahl der Stimmen (Bayes-Sortierung) beeinflusst werden. So würde Duke3d gewinnen.
Halo kann nicht irgendwo platziert werden, weil es nicht gewählt wird ...