問題タブ [tournament]

「n+2k-3 回の比較で、サイズ (2^k +1) の配列で 3 番目に大きい要素を見つけます。」

これは、アルゴリズム コースの最終試験で出題された問題で、すべてのポイントを獲得できませんでした。徹底的なインターネット検索の後、正しい答えが何であるかはまだわかりません。

私はそれが 2 番目に大きい同じ問題の拡張バージョンであることを認識していますが、要求された厳密な比較境界により、質問がトリッキーになりました。ここでK 番目の要素を見つけるための数学的説明も見つけましたが、複雑すぎて理解できませんでした。

配列サイズを n = 2^k + 1 とします。

試験自体では、私の答えは次のようなものでした。

トーナメント ツリーを使用します。まず、任意の要素を除外します。
次に、2^k 要素で構成されるツリーを構築します。したがって、ツリーには K 個のレベルがあります (log(2^k))。

勝者を見つけるには、n-2 回の比較が必要です。

勝者に負けたものの中で最大の要素を見つけます。(K-1 コンプ)

決勝の敗者に負けたものの中で最大の要素を見つけます。(K-2 コンプ)

これらと最初に省略したものを比較します。(2 コンプ)

3 つの中で最大のものは、配列の 3 番目に大きいものです。

合計比較: n - 2 + k - 1 + k - 2 + 2 = n + 2k - 3。

25点満点中10点でした。

私は2つの間違いをしました。主なものは、目的の要素が勝者のサブツリーにある場合、私の答えは正しくないということです。また、最終的に比較した3つのうち、2番目に大きいものが正解のはずです。

私が見つけたもう 1 つのアルゴリズムは次のとおりです
。(これもトーナメント ツリーによる) (k - 1)
- 答えは、最大の敗者から 2 番目の最大の敗者まで、敗者から最初のツリーの決勝で負けた者までのいずれかにあります。(log(k+1) + K-1-1)

-この解決策は、省略した要素が配列内で最大ではないことを前提としています。もしそうなら、私はそれがどのように機能するかわかりません。また、比較の数を正しく理解していなかったのかもしれません。

より適切に説明されたアルゴリズムがあるかどうかを確認できれば幸いです。また、L 番目に大きい (K が取られました..) の一般化されたものがあるかどうかも知りたいと思います。

前もって感謝します、イタイ

現在、私は 1 日トーナメント スケジューリング アプリケーションに取り組んでいます。毎年参加チーム数が違うので、スケジューリングを自動化したい。

チームは 2 つのグループに分けられます。各グループは 1 回のラウンド ロビン トーナメントを行います。プレイするゲームをすべて生成することができましたが、計画に苦労しています。

さらに、チームはそれぞれ専用のフィールドを持つ 3 つの異なるスポーツ分野で競う必要があります。（例：サッカー場、バレーボール場）

与えられた: - プレーするゲーム - スポーツごとのフィールド + フィールドごとに利用可能なタイムスロット (+-15 分のスロット)

仮定: - タイムスロットは制限されていません - スポーツごとに 1 つのフィールドが利用可能です - 最初の反復でスケジュールのバランスをとる必要はありません

問題点: - スケジュールの質があまりよくありません。実際、解決策があるとしても、すべてのタイムスロットが完全に埋まっているわけではありません。私のスケジュールの「密度」は、処理されるゲームの順序にも依存します。

コードスニペット：

アプローチ、利用可能なアルゴリズムなどの概要を誰か教えてもらえますか?

前もって感謝します

ここに、配列のようなトーナメント構造を降順でソートするコードがあります。1 つの数値を除くすべての数値を並べ替え、並べ替えた最小の整数として常に-1を返します。このコードを何度も読みましたが、正しく並べ替えられていない理由がわかりません。私の目が欠けているか、どこかに小さなタイプミスがある場合。

エラーは、トーナメント構造を構築する関数だけにあると思いますが、間違った場所を探しているかどうかはよくわかりません。

この問題にさらに詳細を追加する必要がある場合は、コメントでお知らせください。

編集:これは、私が受け取っている出力を表示するためのリンクです。 http://imgur.com/a/KNDO8

EDIT 2: 数字 20 14 1 3 8 を使用してソートすると、20 8 1 3 -1としてソートされます。

現在、私は実際に私の問題に固有の用語を探しています:

4 チームを超えるリーグを作成しました リーグは 3 ラウンド続きます (数字は簡単にするためです) マッチアップは、チームがまだ対戦していないチームからランダムに割り当てられます。

現在のコードをフリンジ ケースごとに実行するのに苦労しているので、そのようなケース用に開発された「標準」アルゴリズムを調べたいのですが、探している用語が見つかりません。

1 つのスケジュールの例は次のとおりです。

リーグ/トーナメントで使用される可能性は非常に低いように思われるため、その点については何も見つかりませんでしたが、それが私の要件です.

これは、ONE Round を作成する現在のコードです。このコードでは、ラウンド 3 で各チームに対戦相手が割り当てられない可能性があります (6 チームでテスト済み、ラウンド 3 で発生する可能性があります)。

私がグーグルするものについての助けをいただければ幸いです

ある種のトーナメントを提示する単純なデータベースを設計しようとしています。そのため、「試合」(2 つのチーム ID が含まれる) を提示するテーブルがあり、「ラウンド」(1 つのラウンドにいくつかの試合が含まれる) テーブルも作成しました。そして、私の質問があります。ラウンドの ID を (引数を介して、または select 命令で「where」を使用して) 指定した後、トーナメントのランキングを表示できるようにする「何か」(テーブル/ビュー/プロシージャ/関数) を作成したいと考えています。たとえば、チーム A とチーム B の 2 つのチームがあり、1 回戦と 2 回戦でチーム A が勝ちました。したがって、何か番号「1」を通過した後、出力を取得したい:

そのようなことを達成する最も簡単な方法は何ですか?

ラウンド ロビン トーナメントを作成したいのですが、ひねりがあります。

ラウンド ロビンの実装はたくさんありますが、これまで見てきたすべての実装でスケジュールが生成され、誰もがそれに従います。これに関する私の主な問題は、トーナメントの終わりに向かって、プレーヤー A がプレーヤー B と対戦することがよくありますが、プレーヤー A は、結果がどうであれ、最終ランクが固定されていることを知っているのに対し、プレーヤー B のランキングはプレーヤー A との試合に依存することです。 . つまり、プレーヤーは結果を気にせず、他のプレーヤーは気にします。これにより、A がベストを尽くせず、スケジュールが異なる場合 (たとえば、A 対 B がトーナメントの最初のゲームであった場合) よりも高い最終スコアを B が得る可能性が残るという厄介な可能性が残ります。 . これが「悪い」一致の私の定義です

この問題をできるだけ長く回避できるように、ラウンド ロビン トーナメントの各ステップで次のゲーム セットを計算する方法があるかどうか疑問に思っていました。常に可能であるとは限りません (10 人のトーナメント、9 人の非常に熟練した参加者、1 人の非常に熟練していない参加者。0-8 の後、他の全員が 5-3 または 4-4 の場合、最後の試合は「悪い」試合です)

追加情報を 1 つ許可します: Elo ランキング。直観的には、競争相手よりもはるかに劣っている 2 人のプレーヤーがいる場合、その 2 人は他の全員に負けることが予想されるため、2 人の直接対決のみが問題となります。したがって、「悪い」試合を回避する唯一の方法は、対戦を最後に行うことです。

私のメトリックは次のとおりです。N 人のプレイヤーをそれぞれの Elo で取得し、このスケジューラが最初の「悪い」試合の出現の平均時間を最大化するように、各ステップでスケジュールを出力するラウンド ロビン スケジューラを考え出します(つまり、トーナメントで可能な限り遅く）。より簡単なバージョンは、スケジュールを最初に 1 回出力することです。

プレーヤーの結果は Elo レーティングによって正確に表すことができ、このレーティングは固定されており、既知であると想定できます。

これにより、「悪い」試合の定義も変更されます。「この試合とその後の試合によって最終順位が変更されることはないと確信しています」から「この試合とその後の試合によって最終順位が変更されることはないと 99% の確率でわかっています」 "。もちろん99%は変えられる

つまり、結果はおそらく、すべてのプレイヤーを E_1 から E_n までの Elo で並べ替え、最後の試合を (E_1 vs E_2) .... (E_n-1 vs E_n) にするというものです。しかし、私はいくつかの洞察が欲しい

編集 ：

明確にするために、「プレイヤーの結果は Elo レーティングで正確に表すことができると仮定できます」とは、レーティングが R_A と R_B の場合、A の勝率は、ここでElo の式によって与えられるものとまったく同じであることを意味します。

トーナメントでの順位は単純に勝利数によって決まります

近々行われる試験の 1 つについて、過去の試験問題を調べています。次の質問があります。

母集団が 6 人であると仮定します。最初の解の適合度 f(S1)=2; 第２の解ｆ（Ｓ２）＝４。f(S3)=8; f(S4)=16; f(S5)=19; f(S6)=27。トーナメント サイズを 6 に置き換えてトーナメント選択を使用すると仮定します。交叉と突然変異を無視して、次の世代で可能な人口を書き留めます。

私がこの質問にどこから答え始めるか知っている人はいますか? 私はかなり混乱していて、何らかの指示が必要です。

私はこれまでのところこれを持っています：

私は正しい方向に進んでいますか？

どうもありがとう