Santa 2022 - The Christmas Card Conundrum の解法(kaggle)

本記事はkaggleコンペ「Santa 2022 - The Christmas Card Conundrum」に私がどのような解法でこの問題にアプローチしたかをまとめた記事です。(私自身は140thなのでメダル獲得解法でも上位解法でもないですが)何かの参考になれば幸いです。

この記事の想定する対象読者は「この問題の中身をチュートリアルレベルでも理解している人」です。なので、ところどころ問題自体初見の方にはわからない用語とかがあると思います。(というのも、、、概要とか説明していると膨大な量になり本当に伝えたいことが記事の半分も満たない、みたいなことになるのであえて伝えたいことを全面に出すためにこう言うふうにしました)

ただ、最初から理解したいという人向けにリンクは貼り付けておきます。チュートリアルまでやればある程度この記事で書いてある専門用語は理解できるかと思います。

- 本コンペトップページ

https://www.kaggle.com/competitions/santa-2022

- 評価方法

https://www.kaggle.com/competitions/santa-2022/overview/evaluation

- チュートリアル

https://www.kaggle.com/code/ryanholbrook/getting-started-with-santa-2022



# 私のアプローチ

最終的に私が提出したcsvを構築するために取ったアプローチは、

- 最初にpixelベースの経路を構築し、次にpixelベースの経路に沿ってconfigベースのpath(submission用のフォーマット)を構築です。

ほとんどのKagglerがこの方法をとったんじゃないでしょうか。
それではこの部分のアイデアを以下の段落に分けて説明していきます。

- (1) pixelベースの経路構築
- (2) pixelベース経路 -> configベースのpathへ変換
- (3) 領域分割して考える

私の解法の主要な工夫ポイントは(1)と(3)なので、メインはこの部分の説明になります。

## (1) pixelベースの経路構築

全てのpixelを通る経路の中でコストがなるべく小さいものを求めることを考えます。ここで「pixelベースの経路のコストを、『隣のpixelに移動した時にかかったcolor cost + 1』」とします(configのstepごとのコストで、動かすlinkは1つのみを想定したコスト)

解法として「グリッドベースのグラフにおける巡回セールスマン問題に帰着させて解く」が思いつきます。しかし、この時の私の巡回セールスマン問題に関する知識は教科書レベルの知見しかなく、「完全グラフでない」このケースにおける対処の仕方がわかりませんでした。(完全グラフであれば、いくらでもサンプルコードとか落ちています。焼きなましの方法やら2-opt, 3-optとかもさくっと出てきます)

そこで、私は **「グリッドグラフの最小全域木をベースにした」方法** で構築しました。
その方法のアウトラインは以下の通りです。帰着先のグリッドグラフは「4つのpixelをグルーピングした 2 x 2の正方形タイルをnodeとしたもの」になります。

![スクリーンショット 2023-01-20 0.57.05.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/14989/7cdc1960-240c-8f9f-2ca8-ba6c737e8590.png)

上のフローで説明しきれていない部分として、

1. (2)のedgeのコストはどうやって算出したか？
2. この方法は対象画像の縦横の大きさが偶数なら使えるが、対象画像257 x 257だとそのまま適用できない。この問題をどう解決したか？

があるので、このセックションでは以下、この2つを説明します。

### 1. (2) のedgeのコストの算出方法

下図のように、2x2タイル ABCD と2x2タイル EFGH間に張るケースを考えます。この図を使ってedgeのコストをどうやって算出したかを説明します。

![スクリーンショット 2023-01-23 14.30.38.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/14989/dff2ee96-afc0-3837-ad84-ca560ee0a42f.png)

結論から言うと、edgeのコストは以下のように計算しています。

```
[B→EのColorCost] + [D→GのColorCost] - [B→DのColorCost] - [E→GのColorCost]
```

これは「edgeを貼った場合、復元されるpixelパスのコスト削減にどれだけ寄与するか」を意味しています。
edgeを貼らない場合、復元されるpixelパスはB→E, G→Dと通過し、[B→DのColorCost],[E→GのColorCost]分がpixelパスに寄与します。(紫の線がpixelパスの一部になります)
edgeを貼った場合、復元されるpixelパスはB→E, G→Dを通過せずB→E, D→Gを通過し、[B→EのColorCost] + [D→GのColorCost]分がpixelパスに寄与します。(赤い点線がpixelパスの一部になります)
このことから、edgeのコストの意味合いが「復元されるpixelパスのコスト削減にどれだけ寄与するか」と言うふうになってきます。(移動コストはどうした？と思うかもしれませんがpixelの移動なので移動コストは一律1にしている)

そして、全域木の全edgeのコストを最小にすることは、復元されるpixelコストが限りなく小さくなることを意味しています。



### 2. サイズ257 x 257 の対象画像に

この考え方は、縦横が偶数サイズであれば綺麗に行くのですが、対象となる画像のサイズは奇数 x 奇数です。このままだと適用できないので以下の図のように2つ領域に分割し、出来上がった2つの領域のパスを結合する、ということで対応しました。

![スクリーンショット 2023-01-23 15.03.49.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/14989/839dbeec-d7bc-dd54-f62f-c6eb135c0db3.png)

(A) の領域は 254 x 254の正方形領域です。これであればこのセクションで説明している「最小全域木ベースでpixelパスを作る方法」が適用できます。
(B) の領域は 257 x 3, 3 x 257の長方形領域の和集合です。この部分に関しては手で経路を見つけてそのままベタ打ちコーディングして対応しました。

![スクリーンショット 2023-01-23 15.06.39.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/14989/1a13ce09-a1ec-0422-fce2-450f8a154104.png)



上図における(B)の紫の丸は(B)でつくったpixelパスの端点で、これを(A)でつくったpixelパスとくっつけることにより、対象画像を網羅する1つのpixelパスを構成します。


## (2) pixelベース経路 -> configベースのpathへ変換

ここに関しては、pixelベースのパスに沿って「現在のconfig(現在のpixel)から次のpixelまでの最短のconfig遷移を求める」というのを逐次的に行なっています(一種の貪欲法)
これはpixelを状態としたdijkstra法を使って解きました。(configをstateとすると膨大な量になるが、pixelだと数がたかが知れている)
この部分に対しては、多くの解答者が一度は思いつくアイデアだと思うので、ここではきちんと説明しません。

## (3) 領域分割して考える

pixelベースからconfigベースのパスに変換する際、原点やx軸、y軸付近をまたぐ移動の時にconfigを何十回とstep踏んで変化させないといけなくなるケースが発生しました。この部分が頻発すると、いくらpixelベースのパスのコストを削っても、最終的なconfigコストを大きくしてしまうので工夫をする必要があります。

これはconfigの1stepによる変化やconfigの変化の仕方により、隣のpixelにすらいけないということが原因で起こります。例えば、最初armのconfigは原点(0, 0)を指しており、 `64 0;-32 0;-16 0;-8 0;-4 0;-2 0;-1 0;-1 0` となっています(下図参照)この状態だとarmは上下に動かすことはできても、1step目からは左右に動かすことができません。特に左((0, 0) -> (-1, 0))に行くようなarmの動かし方は長さ64のlinkが上下どちらかに64step行かないといくことができません。(長さ32step以下のlinkはxが正の部分に中心があり、その周りでしか動きません。そして、辛くもマイナスの領域を擦りもししません。。)
無理やり(0, 0) -> (-1, 0)と行こうとすると1stepでいけず、長さ64linkを64step以上動かして長さ32以下のlinkたちが $x < 0$  の領域に行けるようにする必要があるためです(ここで1pixel分動かすのに64step分のコストが余計にかかる)

![スクリーンショット 2023-01-23 21.39.25.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/14989/67b2390e-0e36-7466-8011-8722d4fa3e43.png)



そこで問題となる遷移をしないように、あらかじめ領域を分割し、その上で最小全域木を構築するようにしました(その後領域間を結ぶようにコスト最小なedgeを選んで結合)
x軸, y軸をまたぐpixel移動を必要最低限にするため、両座標軸で領域を分断。さらに、x, yの絶対値が64以下である(x, 0), (0, y)の周辺は跨ぐタイミングによっては何百step分もコストがロスするのでここに関しては決まったタイミングでだけpixelが走るように領域を設計しました(図で言う(5))

![スクリーンショット 2023-01-23 20.04.35.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/14989/07536eb5-be6f-306b-ef91-6f6172986de2.png)


これにより、無理な移動をさせたことによるconfigコストの増大の頻発を防ぐことができました。


# 所感とか

今回、kaggle毎年恒例のサンタコンペという最適化コンペに参加できたのはよかったです。kaggleの中では珍しいコンペだと思いますが、AtCoder Heuristic Contest(以下、AHC)とかやっていた自分としては比較的力が出せそう、というので参加しました。

結果としては、76165.63992ポイントで875チーム中140位というなんとも言えない結果で終わってしまったのですが、今回のように自分で頭を使ってロジックを考え、実装し、スコア向上に繋げられたのは嬉しかったです(この方法を適用する前は、configの遷移だけみて貪欲にcost最小のものをとる、ということをやっていて 81870.97373ポイントだったんですが、この方法で約5000ポイントも改善できた!)

AHCと違って、コード提出でなく結果提出なので途中でどんなライブラリとか使ってもいいし、なんなら数秒でおわらくても2時間程度かけても問題ない的なこともできてしまいます。この辺りはわりと実務よりというか、、、そういうことが得意のな人はより向いているのかな、と思いました。

-------

ちなみに上位のチームやメンバーも、同じくpixelベースのパス → configベースのパスと言うふうに変換していましたが、pixelベースのパスを作るのに [Lin-Kernighan法](https://en.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuristic) を使った方法をとっていました。こちらの方が精度が良く、すでに[LKH-3](http://webhotel4.ruc.dk/~keld/research/LKH-3/)とか[Concordo](https://en.wikipedia.org/wiki/Lin%E2%80%93Kernighan_heuristic)などのソルバーが提供されているので、 **巡回セールスマン問題についてある程度知見があれば** Lin-Kernighan法を使ったんじゃないかなと思います。

コンペ中に存在は知っていたのですが、「アカデミックと非商用ならOKだけどkaggleのようなコンペでもOK?」というのがわからなかったのと、ちょっと手を出すのに気持ち的な障壁があったので出せなかったでした。でも、今思うとみんな使っているのでkaggleのようなコンペではライセンス潔癖症レベルなまで神経質にならなくてもいいし、LKH3は普通にmacでコンパイルできたりしたので・・・思ったより問題なさそうと言うのがコンペ後わかりました。今からLKH3とかつかってどうなるかは見てみたいと思います。というのと何よりこう言うライブラリを使える、というのは非常に勉強になりました。(もちろん上位解法の考え方はばっちり抑えていて、勉強になることばかりで。。。)

----

また次回もリベンジとして参加したいと思います。