アルゴリズム｜Webシステム開発の株式会社フラッツ

こんにちは、森です。
研修のカリキュラムにデザインパターンが8時間分含まれていたこともあり、いい機会なので、今回は僕が昔、アルゴリズムとデザインパターンを学ぶのに使って役に立った本を紹介してみます。

アルゴリズム、デザインパターンの順に、

1. C言語によるアルゴリズムとデータ構造 柴田 望洋、辻 亮介 (著)
2. Javaデザインパターン徹底攻略 日立ソフトウェアエンジニアリングインターネットビジネス部 (著)

この2冊が、僕にとってはすごく有益でした。

よく研修などで、「知識を詰め込むよりも論理的思考力を身に付けることが大切」というセリフを聞きます。疑う価値のある内容だとは思いますが、「細かい業務知識以前に、論理的に物事を考えられることは大前提」という考えになら、頷けます。そして、基本的なアルゴリズムとデザインパターンの勉強をすることは、「プログラマにとっての論理的思考力」を身に付ける格好の題材になるんじゃないかなー、と思っています。上記2冊はそのための教材として、十分とは言えないのかもしれませんが、満足のいく内容でした。

まず、(1)に関して。この本の魅力は、話題が読み返す価値のある基礎的なものに絞られている点。具体的には、探索、ソート、再帰です。より実践的なアルゴリズムについて知ろう・考えようとした場合、これらが前提知識としてもとめられるくらいの、基本中の基本です。また、いくつかのデータ構造についての説明も充実しているので、類書より優れているといえると思います（ただし、他の入門書を精読していないので断言はできません）。もちろん、アルゴリズム体操ができるくらいのアルゴリズム愛好家の人でしたら、この本だけでは満足できないかもしれません。

次に(2)に関して。これは端的にまとまっているにもかかわらず、論理的な飛躍が少ない点が良かったです。世間で名著といわれている本で23パターン、というのは、小生には少々長すぎました。また、ネット上で見かける短い解説のいくつかは、既にパターンを知っていることが前提だったり、ほぼ結論のみを言葉を変えて繰り返しているだけだったりで、自分はイマイチ面白みを感じられませんでした。

ここで挙げたものよりも分厚くて評判が良い、名著・定番とされている本はありますよね。だけど、大切なのは細かいことを知るよりも、まずは論理的思考力を身に付けることだったはず。だったら、この程度の軽めの本で良くないでしょうか。ダメでしょうか。いいって言ってください、先輩！

久末です。

ルービックキューブをやったことがありますか？
最近私はこの古き良きパズルにはまっています。

ルービックキューブが流行ったのは1980年ころなので、私(31歳)くらいの年代だと小学生とか幼稚園生くらいですね。
私の家にも一つありましたが、2面を揃えるのがやっとで、バラバラにして組み替えて揃えるというチートをよくやりました。

ところでこのルービックキューブ、組み合わせの数はどの程度あるでしょうか？
ルービックキューブをバラバラにしてみると、6つの中心キューブが固定されているのが分かります。
また、角のキューブや角の間にあるキューブはそのキューブがもつ色の組み合わせが固定です。また、全く同じキューブは2つとありません。
このことから以下のように導き出すことが出来ます。

角のキューブ(コーナーキューブ)の組み合わせ

コーナーキューブは8カ所にありますので、色の向きを考えないと 8!(8の階乗 = 8×7×….2×1)通りあります。
また、色の向きが各3通り(3色)ありますので、3^8(3の8乗)通りあります。つまり、コーナーキューブの組み合わせは

8! × 3^8 =  264,539,520通りです

次に角の間のキューブ(エッジキューブ)の組み合わせ

エッジキューブは12カ所にありますので、色の向きを考えないと 12!(12の階乗 = 12×11×…2×1)通りあります。
また、色の向きが各2通り(2色)ありますので、2^12(2の12乗)通りあります。つまり、

12! × 2^12 = 1,961,990,553,600通りです

各面の真ん中のキューブ(センターキューブ)の組み合わせ

センターキューブは固定されているので1通りです。

全体で何通り？

各キューブの位置の組み合わせが分かったので、全体の組み合わせはこれらを掛ければよいということになりますので、

(8! × 3^8) × (12! × 2^12 ) x 1 = 519,024,039,293,878,272,000通り

が、全体の組み合わせと言うことになります。

がしかし、これは、単純に組み合わせた場合の組み合わせで、実は、全面がそろった状態から回転させるだけでは（バラバラにしたりしない）出来ない組み合わせも含まれています。Wikipediaの解説ではこう説明されています。

ルービックキューブ - Wikipedia

1. 位置がずれているコーナーキューブの個数と位置がずれているエッジキューブの個数の偶奇は一致する
2. 全てのエッジキューブの位置が揃っている場合、向きが異なっているエッジキューブの個数は偶数個である
3. 全てのコーナーキューブの位置が揃っている場合、時計回りに向きがずれているコーナーキューブの個数と反時計回りに向きがずれているコーナーキューブの個数は3を法として合同である

1, 2, 3のそれぞれが先ほど求めた全体の組み合わせの、2分の1、2分の1、3分の1ずつ存在するためルービックキューブを全ての色がそろった状態から遷移できる組み合わせは

(全ての組み合わせ) / (2 × 2 × 3) =  43,252,003,274,489,856,000通り(4325京203兆2744億8985万6000)

と言うことになります。(Wikipediaに全部載ってますね…)

何手で揃えられるか

さて、このように組み合わせの数が分かったところで、全ての色がそろっているわけではない状態から最低何手で全ての色が揃えられるのかという疑問がわいてきませんか？この問題の解はまだ出ていませんが、多くとも25手以内に揃えられることが証明されています。また、少なくとも24手かかるパターンがあることも分かっています。

※ 「多くとも25手」は上界(じょうかい Upper bounds)といい、「少なくとも24手」を下界(かかい Lower bounds)といいます。

さてさて、この上界と下界が一致していないのは、まだすべてのパターンで検証されていないからです。この膨大なパターンはコンピュータを使っても膨大な時間がかかりますが、すべてのパターンを一つ一つ上げていくのではなく、工夫すれば少なく考えることはできます。
例えば、全面そろった状態から、上面を一回だけ回したものと、全面そろった状態から下面を一回だけ回したものは、その状態から揃える方法は同じと見なせます。
こうして、同じと見なせるパターンをいくつも考えて、計算量を減らすことで、膨大なパターンを全てあげるのではなく、本質的な部分だけに置き換えていきます。

ここでちょっと数学を。

y = x²

という式があるとき、yの最小値はいくつでしょうか？

答えは0ですね。

さて、何でこんな数式と問題が出てきたかというと、ルービックキューブの問題も数式に置き換えることが出来るからです。
そして、数式が分かれば、その数式でとりうる値の内、もっとも小さい値(とか大きい値)を求めることが出来ることがあります。
その、最も小さい値(とか大きい値)のことをルービックキューブのような問題では最適解といいます。

この最適解を求めるという行為は、産業界でも多く導入されています。もちろん、私たちの生活にもそこそこ密着していて、例えば、ある駅からある駅までの乗り換えはどういう経路が最適かを教えてくれるサービスなどで利用されています(と思います)。

ルービックキューブの問題を解くのは結構大変だと思いますが、めちゃめちゃ難しいというわけでもありません。アルゴリズムに興味があって課題を探しているならちょっと挑戦してはいかがでしょうか？←無責任

では、また。