さっきソファーに突っ伏して仮眠して起きたら,解法っぽいものを思いついた.アルゴリズムが正しいかどうかは知らん.
http://www.kmonos.net/wlog/53.php#_1604050908
前提として,人数は2のべきと仮定します.
まず,表記を導入します.
(A, B, C, D)
といったような表記で順序付き集合を現します.上は要素数が4の順序付き集合です.
次に,上の表記の順序付き集合に対して「連結」という3項演算を定義します.「連結」は,
(a, b, ..., s)
と
(t, u, ..., z)
と
(a, t)
という3つの順序付き集合から
(a, b, ..., s, t, u, ..., z)
という1つの順序付き集合を得る演算です.これを「(a, t) による (a, b, ..., s) と (t, u, ...,z) の連結」と呼ぶことにします.ただし,演算の結果要素が重複するような「連結」,つまり (a, b, ..., s) と (t, u, ...,z) に同じ要素が含まれる場合は定義されない,とします.
例えば,(A, B) と (C, D) の (A, C) による「連結」の結果は (A, B, C, D) となります.また,(A, B) と (C, B) の (A, C) による連結は,(A, B) と (C, B) で B が重複するため,このような連結は定義しません.
以上の表記を用いて問題に対するアルゴリズムを述べます.トーナメントの参加人数をNとします.Nは2の整数べきです.
まず,勝敗表から (勝つ人, 負ける人) という2要素の順序付き集合を全て作る.この集合をとおく.今,k = 1 として以下を繰り返す.
- の任意の異なる2つの要素を x, y とし,の任意の要素を z とする.x と y の z による連結を考え,その演算結果が定義されるようなものを全て列挙し,その演算結果の集合をとする.
- k <- k + 1
- ならば4へ,それ以外ならば1へ戻る.
- の要素のうち,x で始まるものが x が優勝するトーナメントを表す.以下でd.y.d.の具体例でアルゴリズムを動かして見ます.
k=1
勝敗表に対応する2要素の順序付き集合を全て列挙します.
(A, B), (A, E), (A, G)
(B, C), (B, F)
(C, A), (C, D), (C, E), (C, F), (C, G)
(D, A), (D, B), (D, E), (D, F), (D, G), (D, H)
(E, B)
(F, A), (F, E)
(G, B), (G, E), (G, F), (G, H)
(H, A), (H, B), (H, C), (H, E), (H, F)
以上がとなります.
k=2
の要素の異なる2つとの要素で,連結が可能な組み合わせを全て列挙します.例えばの要素である (A, B) と (G, E) は (A, G) によって連結できて (A, B, G, E) となります.一方,(A, B) と (E, B) の (A, E) による連結は,B が重複するため定義されません.以下,このような連結の結果をすべて列挙します.
(A, B, G, E), (A, B, G, F), (A, B, G, H), (A, E, B, C), (A, E, B, F), (A, E, G, B), (A, E, G, F), (A, E, G, H)
(B, C, F, A), (B, C, F, E), (B, F, C, A), (B, F, C, D), (B, F, C, E), (B, F, C G)
(C および D で始まるのはめちゃくちゃ多いので省略します.E で始まるものはありません.)
(F, A, E, B), (F, E, A, B), (F, E, A, G)
(G と H で始まるのも多いので省略.)
以上がとなります.ちなみに A で始まるの要素は,「A を含めた適当な4人で構成された(部分)トーナメントのうち,A が優勝できるもの」を表しています.
k=3
以下同様です.例えばの要素である (A, E, G, H) と (B, F, C, D) は の要素である (A, B) によって連結できて (A, E, G, H, B, F, E, D) となります.
(A, E, G, H, B, F, C, D)
(以下,計算が超面倒だったので省略)
以上がとなります.
なのでここで終了します.
結果
の要素のうち,A で始まるもの,つまり (A, E, G, H, B, F, C, D) が A が優勝できるようなトーナメントの組み合わせで,実際d.y.d.で紹介されている結果です.このアルゴリズムにおいて, A が優勝できるようなトーナメントとして出力されるのはこれだけです.
いろいろ
要するに単純なDP.このアルゴリズムが十分であることは容易に証明可能なはず.必要かどうかは分からない.多分必要もO.K.だと思うんだけれどにゃー.計算量的には全然考えてないけれど,最悪でぐらい?少なくとも指数にはならないよ〜な気がする.要素の重複チェックでもう1個がかかるかも.
ちなみにNが2のべきじゃなくてシードがあったりすると,優勝させたい者とシードの組み方全てを試さないとならないはず.少なくとも優勝させたい者を単純にシードにすれば良いと言うことはない(反例がすぐ見つかる).
間違ってたらごめんなさい.眠いので寝る.おやしみ.
#ありゃ?か?
#って,途中の演算結果が膨れ上がって指数入るんじゃないかこれ?む〜むむむ.
#いや,やっぱりめちゃくちゃ緩く見積もってもで,ぎりぎり指数じゃないよ〜な?
#ちげーよ.だよ.これだと思いっきり指数だよ.なんかうまい上限見つかるかにゃー?
#って,この程度じゃやっぱ全然ダメダメかにゃー.他のアプローチ考えるべきか?
#で,ムダに時間を浪費してたら誰かにさらっと「NP-complete でしたよ」と言われたりしたりして.あるあるwwww
#優勝させたい候補が given だから pruning ができるけれど,それで指数じゃなくなるかと言えば……う〜?