[決定版] カンケツセン最小手数問題

最小手数とは

以下の記事で考察しているのだが、カンケツセンには理論的下限と実際に実現可能な最小解が存在します。

理論的下限というのはカンケツセン数だけから計算できる値で、カンケツセンが理想的な水脈で連結している場合に達成可能な解です。

しかし、実際にはカンケツセンは理想的な連結をしていない場合も多く、実際に達成できる解はそれよりも大きくなります。

カンケツセン考察

理論的下限

難しいことはさておき、カンケツセン数をn、理論的下限の手数をwとするとその値は以下の式で計算できます。

[mathjax]
\begin{alignat}{3}
\sum_{k=1}^w2^{k-1} &\geq n \\
2^w – 1 &\geq n \\
w &\geq \log_{2}(n+1) \\
\end{alignat}

対数を計算するので計算結果が整数にならないこともあります。

その場合、例えば「3.32回カンケツセンをあける」ということは不可能なのでこれは切り上げて4回というように考えます。

カッコ内は整数に切り上げした理論的下限です。

この結果から、どのステージでも必ず2回以内でアタリを見つけるような手順は存在しないことがわかります。

また、通常潮ではトキシラズとポラリス以外はどんなに上手い手順を考えても、最悪の場合4回はかかってしまうようなアタリの位置があることもわかります。

達成可能な最小解

これも難しいことはさておき、最小解を達成するためには完全二分木が構成できるかだけがポイントになってきます。

全部解説するのも大変なので、一番簡単なポラリス満潮のカンケツセンについて実際に達成可能な最小解を計算してみましょう。

有志による解析によって、ポラリス満潮は以下のようにカンケツセンが連結していることがわかっています。

ここから、合法的な開栓手順について考えていきましょう。

合法的な開栓手順とは

これを定義しないと始まらないので、まずはしっかりとしておきましょう。

合法的な開栓手順とは簡単に言えば「無駄な開栓をしない」ということです。

上記のポラリスの例でいうと、Aをあけて大であれば「BかEがアタリとわかる」にもかかわらずDをあけるような愚かな行為を「合法的でない開栓」というわけです。

手順の評価

ある開栓手順が見つかったとして、その手順がどのくらい素晴らしいものかどうやって評価すれば良いでしょうか?

あるルーチンを評価する際に一般的に用いられるのは最悪計算量と平均計算量です。

それぞれどういう意味を持つのか簡単に説明すると、最悪計算量というのは「どんなに悪く(失敗しても)てもこのくらいの計算(開栓)しかしない」というものを保証し、平均計算量というのは「何百回も繰り返せば、平均的にはだいたいこのくらいの計算(開栓)で済む」というものを保証してくれます。

最悪手数/平均手数を計算する

ポラリス満潮の全ての合法的な開栓手順を列挙すると十通りになります。

これが何を意味するかというと、(全開け以外の)ポラリス満潮のあけ方は上記の十通りしかないということです。

当たり前ですが、それぞれの手順を同時に行うことはできません。

なので、カンケツセンの最も良い手順を考える際はこの十通りの中から「どれが一番良さそうか」吟味する必要があるのです。

そして、その際に指標となるのが先述した最悪計算量(手数)と平均計算量(手数)になるのです。

Aからあける手順

Aからあける手順は二つありますが、左右対称なのでこのような形のものしかないと考えても差し支えありません。

Aからあける手順

ちなみにこの図は「初手Aをあけて小ならD、大ならB→Dとあける」を意味します。

カンケツセンのアタリは長期的に見れば偏りがないと思われているので、どれがアタリかは当確率と考えて良いことになります。

つまり、平均手数は以下のように計算できます。

[mathjax]
\[
\frac{1}{4}(1+2+2+3)=2
\]

最悪手数はEがアタリの場合でこれは簡単に3だとわかります。

Dからあける手順

Dからあける手順

Dからあける手順は上記のように二つありますが、左のような手順をとる人はいないので(最悪の場合全開けすることになる)より手数が少なくて済む右の手順を考えます。

[mathjax]
\[
\frac{1}{4}(1+2+3+3)=2.25
\]

最悪手数はAからあける場合と同じく3ですが、平均手数が2.25になっています。

このことから、初手Dをあけるのは良くないとされているのです。

他の評価手法があればぜひ導入したいです。いい案があればご連絡ください。

各ステージの最小手数解

解説すると長くなりすぎるので予め計算した値とその値を達成するための手順の一例を掲載していきます。

「手順の一例」と書いたのは最小手数を達成する手順がいくつか存在する場合があるためです。

計算ミスしている可能性も十分あるので「この値違いませんか?」という連絡お待ちしております。

シェケナダム

通常

wiki手順はアタリの位置が悪い(約11%の確率で発生する)と、移動距離がとんでもないことになるので非推奨。

複数人であけるならまだしも、一人であける場合にこの手順ではノルマ不足が心配である。

最小手順の場合は初手が大ならいいが、小だった場合(約56%の確率で発生する)は無駄にコンテナ近くのカンケツセンをあけることになってしまうのでマズい。

おまけに、干潮側がアタリだったときにはさんざん移動させられておいて灯台下暗し状態になってしまう。

ノルマが足りず、時間も危ないときに博打でチャレンジするような利用法が考えられるだろうか。

効率化された手順は初手が大の場合に二手目にコンテナ近くをあけるので心配だが、ここは足元が塗れる上に段差があるのでそこまで問題にはならない。

ここが小だと雑魚シャケが邪魔になるめんどくさい場所がアタリなのだが、確率は約11%なのでそのときは運が悪いと思って諦めよう。「ものすごく移動させられる」ということよりはマシなはずです。

満潮

何故かwiki手順が神聖化されている気がするのだが、個人的には圧倒的に最小手順を推したい。

わざわざ金網方向を先にあけにいく必要があるかは疑問が残る。

ドンブラコ

通常

最小手順は別にあるのだけれど、いろいろ考えるとこのwiki手順が最速で安定しています。

覚えることがちょっと多いけれど練習して慣れてしまいましょう。

満潮

満潮はとっても簡単。

奥からあけていくだけの作業です。

シャケト場

通常

未だに最良の開栓手順が議論されているステージ。

最小手数解は四回以内でアタリを見つける方法が知られています。。

ただし、この手順は最初にあけた二つがどちらも小の場合に移動距離がとても長くなるのが玉に瑕です。

二つ目をもうちょっと手前をあければそのパターンについては移動距離が軽減されますが、別のケースで雑魚シャケに囲まれる可能性もあり一長一短。

wikiなどで提案されている手順は、最悪の場合の移動距離がとんでもないことになるので個人的にはナシかなあという気がしています。平均手数とか最悪手数がいいわけでもないですし。

オススメは効率化された手順で、金網側をなるべく早くあけつつ移動距離を抑えつつボムを使うことで時間短縮ができる方法です。

なんでこの手順がいいかということは以下の記事で解説しているので御一読ください。

満潮

通常がものすごく難しいのに対して満潮はとても簡単です。

タマヒロイに回収されやすいのでそこだけ気をつければ失敗は殆どありません。

最小手順は二つありますが、右の方がわずかに良いです。

なんで右の手順のほうがいいかということについては以下の記事で詳しく解説しています。

一番最初は右の手順がオススメですが、二回目以降はどちらかあけやすい方を選択していくのがベターだと思います。

繰り返しますが、このステージは満潮だと全開けしない限りはクリアできるくらい簡単です。

トキシラズ

通常

必ず三回以内でアタリをみつけることができる最小手順解はあるものの、wiki手順のほうがわかりやすくこれも安定するので問題ない気がしますね。

満潮

通常潮のwiki手順の便利なところは満潮でも全く同じ手順が通用するというところ。

ポラリス

通常

最小手順の方が僅かに得なのでこちらがオススメだが、wiki手順ともあまり変わらない。

それよりも大事なことは初手はさっさとあけることと、ボムであけることです。

満潮

別にこの手順だけが正解というわけではないので各自好きにあけていただきたい所存です。

解説動画

多分、全ステージの動画載せているのでぜひ見てください。

単純にカンケツセンをあけるだけではなくてボムを使って効率的にあけていくテクニックについても解説していたりします。

まとめ

ここまでの総括を簡単にまとめます。

載せている数字はそれぞれ平均手数と最悪手数です。

通常

ステージ下限最小手順wiki手順
シェケナダム2.78/3.322.78/4.002.89/4.00
ドンブラコ2.62/3.172.75/4.00*12.88/4.00
シャケト場2.78/3.322.78/4.003.00/5.00
トキシラズ2.43/3.002.43/3.00*22.85/4.00
ポラリス2.43/3.002.57/4.002.71/4.00

[1]ドンブラコの最小手順は手数こそ最小になるものの現実的でないあけ方になるので本記事では紹介を差し控えました。

[2]トキシラズは最小手順を踏めば理論的下限と一致するのだが、wiki手順でも十分安定するので、下手に覚える必要はまったくない。

満潮

ステージ下限最小手順wiki手順
シェケナダム2.20/2.582.20/3.00*12.40/3.00
ドンブラコ2.00/2.322.00/3.002.00/3.00
シャケト場2.20/2.582.20/3.002.20/3.00
トキシラズ2.20/2.582.20/3.00*22.40/3.00
ポラリス2.00/2.322.00/3.002.00/3.00

満潮では多くのステージで下限を達成することができた。

つまり、カンケツセンの満潮は簡単だから失敗してはいけないということです。

[1]シェケナダムは最小手順であれば理論的下限と一致する。

[2]トキシラズは最小手順であれば理論的下限に達するが、wiki手順のほうが安定性が高いのでその手順については本記事では紹介しない。

適当に書き始めた記事だったのですが、手順の評価から全ステージの最小手順やwiki手順をまとめていたら結構な内容になりました。