「何人の選手で全チーム所属達成できるか」問題について：プレミアリーグ編 (追記:20190125)

2019年1月9日 13:48

追記の内容(20190125)

・確率的な列挙法を思いついたので実行しました．組み合わせがたくさん見つかりました！具体的には下に書いてあります．

上記のtkqさんのノートやツイートを眺めて，「何人の選手で全クラブ所属達成手できるか問題」についていろいろと作業してツイートしたのが2018年の11月でした．以下のツイートからのスレッドです．

Jリーグの公式データベース内で記録されている所属クラブのデータを取り出して，数理計画問題のうちの「集合被覆問題」として定式化し，それをソルバ(普段使っているMATLABに関数があった)に渡して解が出ました．めでたしめでたし．Twitterのインプレッションもかつて無く伸びました．

プレミアリーグでも同じ話題が盛り上がっていたようです．だいぶ遅れて気づきました．

ということで，プレミアリーグ公式サイトのデータベースの仕様を確認し，ちまちまと選手IDから所属クラブを引き抜いていきます．

これはアラン・シアラー選手のページですが，URL内の番号(89)が選手IDのようなので，ここの値を変えてひたすら当たっていきました．結果として，そのクラブがプレミアリーグに所属している年に(ここ重要)在籍経験のある選手5836名について，それぞれ在籍経験のあるクラブの一覧を作成できました．

結果です．6名が最小，と求まりました．

5名，という方の回答とは条件が違っているようです．

ドリンクウォーター選手を例に挙げると，公式データベースではカーディフやハダースフィールドの所属履歴が載っていません．

これは，カーディフは10-11シーズンではプレミアリーグではなくチャンピオンシップに所属していたことが反映されています．

1シーズンでもプレミアリーグの経験があるのは49クラブです．全49クラブの在籍は12人でカバーできました(というか，プログラム作成の都合上最初にこっちを解いていたんですが)．

プレミアリーグはほとんど見ていなかったので，選手がぜんぜんわかりません．詳しい方，この表はどんな印象なんでしょうか？

上の方法だと1組しか出せないんですが，最小の人数がわかってしまえばそれは制約式に組み込んで，評価関数の係数を適当に変えることで縮退した解空間の中から解を確率的に列挙できるんじゃないの？と思いついて実装しました．多分既知の手法だと思うんですが，調べ方が悪いのか同様の方法がなかなか見つかりません．

で，結果です．

係数をランダムに振った評価関数を2万通りくらい試して28通りしか見つからなかったので，残っていてもそこまで多くないのでは？という感覚．証明は全くできない方法ですが！

そりゃーそうだよね，という結果ですが，ためしに係数をランダムに振った評価関数を1000通り試したら890通りも見つかってしまい，これは手に負えんなーという感想です．

で，結果をエクセルにしたものを公開します．タイトル未定とありますがエクセルファイルへのリンクです．

Webや記事などでこのデータを使いたい場合(使い方が想像つかないですが)は，このnoteへの言及をお願いします．