Kaggle/Competition/Santa 2021 - The Merry Movie Montage
概要
Your job is to help the elves by giving them the shortest viewing schedules that shows them every combination of movies so they can get SantaTV+ live as soon as possible!
7種類の番組を組み合わせて放送スケジュールを作る、という課題。機械学習ではなく最適化問題。
データ
🎅, 🤶, 🦌, 🧝, 🎄, 🎁, 🎀
の7種類の並び順を調整する。条件は以下
3つの文字列を作成する
3つの文字列のいずれかに7種類の並びの組全てが含まれている必要がある
🎅🤶🦌🧝🎄🎁🎀だっり🤶🦌🧝🎄🎁🎀🎅だったり
🎅🤶🦌🧝🎄🎁🎀🎅には🎅🤶🦌🧝🎄🎁🎀と🤶🦌🧝🎄🎁🎀🎅が含まれている
こういう感じで短くしていく
7*6*5*4*3*2*1 で全部で5040パターン
🎅🤶から始まるパターンは3つの文字列すべてに含まれている必要がある
5*4*3*2*1 で全部で120パターン
各文字列に2つワイルドカード(🌟)を設定できる
ただしパターンの中にワイルドカードが2つある状態は認めない
🎅🌟🦌🧝🎄🎁🎀は🎅🤶🦌🧝🎄🎁🎀と認める
🎅🌟🌟🧝🎄🎁🎀は🎅🤶🦌🧝🎄🎁🎀と認めない
以上の条件を満たす3つの文字列の組で、一番長い文字列の長さをスコアとする。(文字列の長さが3,4,5だったらスコアは5)
提出形式
以下の４行を記載したテキストファイルを
schedule
<文字列1>
<文字列2>
<文字列3>
考察
必須パターン + その他のパターン / 3 = 1760
ということで単純に全部くっつけると1文字列あたり1760パターン*7=12320となる。
ベースライン
3つの文字列に最初に1パターンずつ割り振って、以後くっつけて一番短くなるものをくっつけ続ける。
これでだいたい2650 ~ 2700くらいの長さになる。
巡回セールスマン問題
これ、巡回セールスマン問題の変種だよね？というDiscussion。
たしかに、パターンを都市、文字列をくっつけたときに増える長さを移動コストとみなすとそう解けそう。
つまりこれNP困難だかNP完全だかの計算量になる。。。総当りは無理。
PuLP
Pythonで巡回セールスマン問題のライブラリとしてPuLPというのがあるらしい。
使ってみたけど全然短くなっている気配がしないし、どこがおかしいのかもわからなかったので断念。。
2-opt
他に巡回セールスマン問題を解く方法として2-optというものもあるらしい。
最初にランダムな順列を作って、スコアが低くなるように順番を入れ替え続ける。
実装してみたけど終わらないしベースラインを超える気配がなかったので断念。
ベースライン拡張
深さを加える
一番短くなるものではなく、X個くっつけたときに一番短くなるものを探す。
計算量がエグくなるのでキャッシュしておくとか途中で見切りをつけるとかが必要。
文字列を分割して考える
1つの文字列を複数のパターンの組と考える。
条件を満たすパターンの組を作って、最後に組み合わせて文字列を作成する。
行列演算として解く
今の文字列とくっつける文字列を行列で表せそうな気がする。
行がくっつけられる側、列がくっつる側の5040 * 5040にくっつけたときのスコアが入った行列(join_score)があって、そこに実際にくっつけられる側が存在するかとくっつける側が存在するかの0-1行列を掛ける
join_score * (candidates.T * heads) # 先頭にくっつける場合
join_score * (candidates * tails.T) # 最後にくっつける場合で、一気に求められる。
ただやってみたけどあんまり速くなかった。。。numpyの使い方が悪いかな？
行列の計算の改善ができるスキルがないので、いったん諦め。
他に良いやり方が見つかって高速化したくなったらまた行列に挑戦してみよう。
その他
上記で2550くらいまではいけるけど、2500切れる気がしないので多分全く違う考え方があるんだろうな。
と思ったら↓のnotebook通りにやれば2500くらい簡単に出る。
これベースにパラメータ調整だけもうちょっと頑張ってみよう。
Using a MIP solver (cplex) I found a lower bound of 2440 without widlcard.
cplex 使うと2440まで行くらしい。自分で書いたコードだけでローカルで回すだけだと限界がありそう。
とはいえAWSとかでお金かけてやる気は今の所無し。
小ネタ
It is 6 wildcards, not 2
英語読み間違えてて、3つの文字列でワイルドカード2つ使うんだと思ってたorz
実際は”Each string may have up to two wildcards 🌟”だから1文字列あたりワイルドカード2つまで、だった。。。
気づかせてくれた投稿に感謝のupvote m(_ _)m