プレイヤーとプレイヤーの決闘結果からトップリストを作成

Question

私はプレイヤーの間にデュエルのリストを持っています。データは2つのユーザーIDで構成されます。最初のユーザーIDは2番目のユーザーIDです。

ベストプレイヤーを見つけるためにこのリストのグラフを作成するにはどうすればよいですか？

また、どのように最適であることを決定するのですか？ おそらく、選手は殴られた対戦相手の数とその対戦相手のランク（再帰的）によってランク付けされるべきです。 私はこれまでPageRankアルゴリズムを使ってこれをやってみましたが、良い方法で損失を考慮していません（つまり、ランクは損失から下がるはずです）。例えば

： - 高いランクを有するものを決闘するために必要とされなければならない、それはこれが一つの問題を提示1.

を倒すため

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

このリストには、先頭に2を入れなければなりません。 特定のランク以上のプレイヤーに対戦していないプレイヤーは、トップリストに入るように指示する必要があります。

Answer 1

プレーヤーX叩きプレーヤーYを、頂点XとYが存在するような関係で定義し、のYからXへのエッジが存在すると定義します。

その後、すべてのゲーム情報を処理した後、グラフ上にDFSを実行して、一部の配列Aにの深さにあるノードを記録します。。 指定されたグラフがツリーであると指定していないので、エッジが方向付けられていることを考慮して、ノードから開始するDFSは単一のルートに収束するという保証はありません。そのようなノードのリストビート他。

最初のトラバーサルが完了したら、すべてのエッジを逆転させ、グラフのルートである各ツリーのDFSを実行し、それぞれのルートはAの要素です。A [i ]、ルートノードA [i]に対する相対的な位置を各ノードに記録する。

次に、のトップのプレイヤーの定義に応じて、Aのルーツを横断して、その定義に遭遇して、遭遇するすべての要素を選ぶことができます。あなたが必要とする最終的なリストが、実際にAの異なる根の子孫をソートする必要がある場合は、深さを比較基準としてリストを持つ最終構造をソートすることができます。私が言及した最後のソートとは別に、これまでDFSが行っていたのはすべてO（V + E）であり、Vは頂点の数であり、Eはエッジの数です。異なるツリーの要素のソートを考慮すると、O（（V + E）+ VlogV）の全体的な複雑さがあります。

もう少しパフォーマンスを犠牲にしたい場合は、AのルートをグローバルルートRに接続します（つまり、ノードRをグラフに追加し、Rを各A [i]に追加して） Dijkstraのアルゴリズムでは、最初に深度の低いノードを訪れ、基本的に各訪問ノードをあなたのリストに追加することを考慮するまで、の定義の定義に基づいて十分に大きくなります。

最終的なトラバースにDFSまたはDijkstraを使用するかどうかにかかわらず、グラフにサイクルがある場合、この解決策は機能しません。しかし、それは、正の重みを有するエッジを使用することによって複数のマッチを有するプレーヤーに適合させることができる。ウェイトkのXからYまでのエッジは、XがYを敗北させた回数を示します。これは、DFSでのトラバーサル中にノードの深さを更新する際に考慮されます。