Build Top-Liste von Spieler-Spieler-Duell Ergebnis

Question

Ich habe eine Liste der Duelle zwischen den Spielern. Die Daten bestehen aus 2 Benutzerkennungen, wobei die erste der Gewinner ist.

Wie kann ich ein Diagramm dieser Liste erstellen, um die besten Spieler zu finden?

Wie kann ich entscheiden, was es heißt, das Beste zu sein? Vielleicht sollten Spieler nach der Anzahl der geschlagenen Gegner und dem Rang dieser Gegner (rekursiv) geordnet werden. Ich habe zuvor versucht, dies mit dem PageRank-Algorithmus zu tun, aber es berücksichtigt Verluste nicht auf eine gute Weise (d. H. Der Rang sollte von einem Verlust ausgehen).

Zum Beispiel:

1 won against 3 
1 won against 4 
1 won against 5 
2 won against 1 

Diese Liste 2 oben setzen sollte, weil es 1. schlagen

Dies stellt ein Problem - es erforderlich sein sollte diejenigen mit einem hohen Rang duellieren. Wer keine Spieler oberhalb eines bestimmten Ranges duelliert hat, sollte dazu aufgefordert werden, um in der Top-Liste zu stehen.

Answer 1

Definieren Sie Spieler X schlagen Spieler Y als eine Beziehung, so dass es gibt Scheitelpunkte X und Y und gibt es eine Kante von Y bis X.

Dann, nach der Verarbeitung aller Spielinformationen, können Sie DFS in der Grafik ausführen, Aufnahme in einem Array A die Knoten, von denen Sie tiefer nicht durchqueren können. Da Sie nicht angegeben haben, dass der angegebene Graph ein Baum ist, können Sie auch unter Berücksichtigung der Kanten keine Garantie dafür geben, dass DFS, das von einem Knoten startet, zu einem einzigen Stamm konvergiert Liste solcher Knoten, die schlagen andere.

Sobald diese anfängliche Traversierung abgeschlossen ist, kehren Sie alle Kanten um und führen Sie ein DFS für jeden Baum in der Gesamtstruktur aus, der Ihr Diagramm ist und die Wurzel jedes Elements ein Element in A. Wenn Sie den in A [i ], notieren Sie in jedem Knoten die Tiefe, in der er sich befindet, relativ zum Wurzelknoten A [i].

Dann, abhängig von Ihrer Definition von Top Spieler, können Sie die Wurzeln in A durchqueren und gehen so tief wie die Definition ermöglicht es Ihnen, jedes Element, das Sie begegnen. Wenn die endgültige Liste, die Sie benötigen, eigentlich die Nachkommen von verschiedenen Wurzeln in A sortieren soll, können Sie die endgültige Struktur, in der Sie Ihre Liste haben werden, sortieren, indem Sie die Tiefe als Vergleichskriterium verwenden. Abgesehen von der letzten Sortierung, die ich erwähnt habe, ist DFS bisher O (V + E), wobei V die Anzahl der Ecken und E die Anzahl der Kanten ist. Wenn Sie die Sortierung von Elementen in verschiedenen Bäumen berücksichtigen, haben Sie eine Gesamtkomplexität von O ((V + E) + VlogV).

Wenn Sie bereit sind, etwas mehr von der Leistung zu opfern, dann können Sie die Wurzeln in A mit einem globalen Wurzel R verbinden (dh Knoten R zum Graphen hinzufügen und Kanten von R zu jedem A [i]) und ausführen Dijkstra-Algorithmus, der zuerst die Knoten mit geringerer Tiefe besucht und im Prinzip jeden besuchten Knoten an Ihre Liste anfügt, bis Sie eine Liste als groß genug ansehen, basierend auf Ihrer Definition von top Spielern.

Beachten Sie, dass diese Lösung nicht funktioniert, wenn Sie Zyklen im Diagramm haben, unabhängig davon, ob Sie DFS oder Dijkstra für die endgültige Traversierung verwenden.Es kann jedoch für Spieler mit mehreren Übereinstimmungen angepasst werden, indem Kanten mit positiven Gewichten verwendet werden. Eine Kante von X nach Y mit dem Gewicht k würde dann angeben, wie oft Y Y besiegt hat, was Sie berücksichtigen werden, wenn Sie die Tiefe des Knotens während Ihrer Traversierung mit DFS aktualisieren.