ビル・ゲイツの思考に触れられるゲイツ唯一の学術論文「パンケーキ論文」とは!?

数学者、遺伝学者、コンピューター技術者、、、どれになるか迷っていたビル・ゲイツ

ビル・ゲイツは、高校時代からコンピューターに夢中になり、すでにソフトウェアを受託開発するというビジネスを始めている。しかし、そのままマイクロソフトを起業するつもりだったわけではなく、ハーバード大学に進んでからは、数学者になるか遺伝学者になるかコンピューター技術者になるか決めかねていた。

まずは数学者になることを目指して、「数学55」というハーバードの中でも最高レベルの数学の講義を受講した。しかし、ここでゲイツは人生で始めての挫折を味わったのではないかと言われている。ゲイツは数学の成績も図抜けて優秀だったが、それでは単なる優等生にすぎない。ハーバードには数学の天才としか呼びようがない学生がごろごろいたのだ。努力ではどうにもならないものをゲイツは感じたのかもしれない。

ビル・ゲイツが書いた唯一の学術論文『パンケーキ論文』

ゲイツが数学からコンピューターに転換をする時期に、ゲイツは唯一の学術論文を書いている。これが数学の論文なのだが、実にコンピューター的なのだ。

この論文は、パンケーキ問題に関するもの。パンケーキ問題とは、1975年にヤコブ・グッドマンが提案した数学問題。「あるシェフが複数のパンケーキを焼くが、腕が悪いために、大きさがまちまちになる。しかも、それをひとつに積み重ねてしまう。これを上から小さいもの順に並べ替えたいが、n枚のパンケーキを並べ替えるのに、何回操作を行えばいいか？」というものだ。

ここで注意したいのが、並べ替えるのが縦に積まれたパンケーキだということ。並んでいるパンケーキの一箇所にヘラを入れて、そこから上をひっくり返すという操作しかできない。

ゲイツは授業でこの問題を知った時「簡単じゃないか！」とバカにしたように声をあげたという。その気持ちはわかる。プログラムの基礎課程で学ぶソートアルゴリズムのうちの選択ソートの簡単な応用問題に見えるからだ。

選択ソートは、ランダムに並んだ数字の中から最小値を見つけ、これを先頭の数字と入れ替えるというもの。これで先頭に最小値がくるので、次は2番目以降の中から最小値を見つけ、2番目の数値と入れ替えるというように、先頭からソートをしていくやり方だ。パンケーキ問題も、選択ソートを応用して、最も大きなパンケーキを見つけて、最も下と入れ替える。次は下から2番目より上で最も大きなパンケーキを見つけて、下から2番目と入れ替える、とやっていけば、選択ソートの応用でできそうな気がする。

しかし、事情はそう簡単ではない。なぜなら、パンケーキではヘラをどこかに入れて、そこから上をひっくり返すことしかできず、選択ソートのように「入れ替える」ということができないのだ。

ゲイツが数日間夢中になって見つけた最適なアルゴリズムとは!?

簡単だと思ってバカにした問題が、意外に難しかった。ゲイツはそれから数日間、このパンケーキ問題に夢中になり、ようやく最適なアルゴリズムを見つけ、指導教官のクリストス・パパディミトリューに報告をした。そして、指導教官とゲイツは、この論文を仕上げ、「離散数学」1979年9月号に掲載された。これがビル・ゲイツ唯一の学術論文として、現在でもデジタルアーカイブなどで読むことができる。

ゲイツの着想はどんなところにあったのだろうか。

その前に、パンケーキ問題の一般的なアルゴリズムを紹介しておこう。パンケーキが（2,3,4,7,6,1,5)の順で並んでいるものとする。これを(1,2,3,4,5,6,7）に並べ替えるのが目的だ。

一般的なパンケーキアルゴリズムでは、末尾から大きいものを並べていくようにする。しかし、いきなり最大値を末尾に移動させることはできないので、最大値の下でひっくり返して、いったん先頭に出し、それから全体をひっくり返すという2段構えで行う。この例では、最大値の7の下にヘラを入れて、その上の（2,3,4,7）の部分をひっくり返す。

（7,4,3,2,6,1,5)

そして、全体をひっくり返す。

（5,1,6,2,3,4,7）

これで末尾に最大値の7がきたので、上6枚から最大値6を探して、そこから上の（5,1,6)をひっくり返す。

（6,1,5,2,3,4,7）

末尾の7は定位置なので触らず、その上にヘラを入れて（6,1,5,2,3,4）をひっくり返す。

（4,3,2,5,1,6,7)

これで、末尾の6と7が決まったので、その上から最大値を探し…ということを繰り返していく。

以下、

（5,2,3,4,1,6,7)

（1,4,3,2,5,6,7）

（4,1,3,2,5,6,7）

（2,3,1,4,5,6,7）

（3,2,1,4,5,6,7)

（1,2,3,4,5,6,7)

となる。

とても堅実な方法だが、1つのパンケーキの位置を決めるのに2手かかる。並び順の関係でうまく手数が少なく済む場合もあるが、最悪のケースでは2n回かかることになる。堅実だが、どうもバカ正直で面白くない。もっと手数の少ないアルゴリズムがあるのではないか。ゲイツが悩んだのはここだった。

「連続ブロック」を利用すると、より洗練されたアルゴリズムになることを発見

そして、ゲイツは「連続ブロック」を利用すると、より洗練されたアルゴリズムになることを発見した。連続ブロックとは[2,3,4]などのように、数字が連続している並びのことだ。

初期状態（2,3,4,7,6,1,5)では、（[2,3,4]7,6,1,5)のように[2,3,4]の部分が連続ブロックになる。また、[6,7,1]は連続ブロックと考え、[4,3,2]は逆順になるので連続ブロックとは考えない。

ゲイツは、この連続ブロックに注目をして、連続ブロックの先頭がさらに連続ブロックを伸ばすようにひっくり返していくと、ステップ数の少ないアルゴリズムになることを発見した。

（[2,3,4]7,6,1,5)

では、[2,3,4]という連続ブロックがあり、この連続ブロックの先頭の2が、さらに連続ブロックを伸ばすために1の隣にくればいい。つまり、6と1の間にヘラを入れて、（2,3,4,7,6)をひっくり返せば、連続ブロック先頭の2が1の隣にきて、連続ブロックが伸びていくことになる。

（[6,7],4,3,2,1,5）

[2,3,4]の連続ブロックは反転されたので、連続ブロックではなくなってしまったが、1と隣接して、[1,2,3,4]という潜伏する連続ブロックとなった。一方で、新たに[6,7]という連続ブロックが生まれている。この先頭の6がさらに連続ブロックを伸ばすには5の隣にくればいい。そのためには、1と5の間にヘラを入れて、（6,7,4,3,2,1）をひっくり返す。

（[1,2,3,4],7,6,5)

最小値である1と最大値である7は隣り合っていると考え、連続ブロックの先頭の1が7と隣り合うようにするため、4と7の間にヘラを入れ、（1,2,3,4)をひっくり返す。

(4,3,2,1,7,6,5)

ここで連続ブロックがひとつもなくなった。連続ブロックがない場合は、基本のアルゴリズムを適用する。最大値でひっくり返し、それから全体をひっくり返す。

（7,1,2,3,4,6,5)

（[5,6],4,3,2,1,7）

（6,5,4,3,2,1,7)

（1,2,3,4,5,6,7)

「プログラマーというものは、楽をするためであれば、どんな苦労もいとわないものだ」

いかがだろうか。時間のある時に、メモ帳に適当な数字を並べて、一般的なパンケーキアルゴリズムとゲイツのアルゴリズムを手段計算して、比べてみていただきたい。あるいはプログラムを組んでみてもいいだろうし、数学の力がある人はn枚のパンケーキを並べる時のパンケーキアルゴリズムとゲイツアルゴリズムの最小手数の一般解を求めても面白い。

一般的なパンケーキアルゴリズムは堅実だがどこか無駄のある緩さを感じるが、ゲイツのアルゴリズムは一手も無駄にしない鋭さを感じる。ゲイツは後年、「プログラマーというものは、楽をするためであれば、どんな苦労もいとわないものだ」と語っている。

ゲイツが発見したアルゴリズムをなぞることで、ゲイツの思考に触れることができ、ゲイツのエンジニアとしての大きさを実感できるはずだ。数学の知識がある方は、※ゲイツの論文そのものを読んでみるもの楽しいと思う。

『マイナビIT AGENT』なら、IT業界に精通した専任アドバイザーと豊富な求人で、あなたの転職を丁寧にサポートします。