線形探索と二分探索を使って、高速化するアルゴリズムを考えよう #パズルのアルゴリズム問題

前回（一度計算した値を再利用して、高速化するアルゴリズムを考えよう #パズルのアルゴリズム問題）再帰とメモ化を使って、高速にパズルを解く方法を紹介しました。再帰を使うとプログラムがシンプルになる一方で、工夫しないと処理量が膨大になってしまいます。今回の問題も、再帰を使って解くことができますが、他の解き方を紹介しています。ぜひ以下の解き方を参考にして、複数の解き方を考えてみてください。

今回は教科書でもよく登場する「線形探索」と「二分探索」がキーワードです。実際にどのような場面で使えるのかを知り、実装できるようになりましょう。よく使われるアルゴリズムでも、パズルを解くときに使ってみるとその効果を実感できます。

【先月の問題】
山手線には現在29個の駅があります。
n人をそれぞれ異なる駅に、間隔ができるだけ離れるように配置することにしました。
この配置におけるn人の間隔の最小値を求めてください。
（つまり、間隔の最小値が最大になるような配置を求め、その間隔の最小値を求める。）

なお、各駅の間の距離はWikipedia（https://ja.wikipedia.org/wiki/山手線）による値を使用します。
このページによると、各駅の間の距離(単位：km)は、東京駅から内回りで以下のリストのようになっています。

[1.3, 0.7, 1.0, 0.6, 1.1, 1.1, 0.5, 0.8, 1.6, 0.7, 1.1, 1.8, 1.2, 0.9, 1.4, 1.3, 0.7, 1.5, 1.2, 1.6, 1.5, 1.2, 0.9, 2.0, 2.2, 1.5, 1.2, 1.1, 0.8]

例えば、n=3のとき、大塚駅と恵比寿駅、有楽町駅に配置すると、それぞれの間隔は以下のようになります。
大塚駅 ←11.6km→ 恵比寿駅 ←11.6km→ 有楽町駅 ←11.3km→ 大塚駅
このとき、その間隔の最小値は11.3となります。

なお、nは1<n<15の整数とします。

今回の問題での注意点

今回の問題ではそれぞれの駅間の距離を調べるのですが、注意しなければならないのは与えられた距離が「小数」だということです。私たち人間が計算する場合は、10進数で計算するため小数でも問題ありませんが、コンピュータでは一般的に浮動小数点数を使います。

浮動小数点数で小数の計算をすると、欲しい結果とは異なる値になる場合があります。例えば、以下のソースコードを実行してみましょう。

結果は「1.7」ではなく、「1.7000000000000002」のようになります。このような誤差を防ぐため、今回はすべて10倍して整数の値を距離として使うことにします。これを踏まえて、いくつかの解き方を考えていきます。

組み合わせを使って考える

まず、単純な解き方を考えてみましょう。n人の配置としてすべてのパターンを調べると、その配置の中から間隔ができるだけ離れるようなものを見つけられそうです。例えば、n=3のとき、29個の駅から3つを選ぶ組み合わせを考えます。

例えば、問題文にある「大塚駅と恵比寿駅、有楽町駅」の3つの駅を選んだとします。このときの距離は、それぞれの駅間の距離を格納した配列から、要素の一部分を合計することで求められます。

東京駅を0番目とすると、大塚駅は11番目、恵比寿駅は20番目、有楽町駅は28番目です。つまり、以下の配列で駅間の距離を表していると、11番目〜20番目、20番目〜28番目、28番目〜11番目を求めると欲しい値を求められます。

[13, 7, 10, 6, 11, 11, 5, 8, 16, 7, 11, 18, 12, 9, 14, 13, 7, 15, 12, 16, 15, 12, 9, 20, 22, 15, 12, 11, 8]

実際に計算してみると、

18+12+9+14+13+7+15+12+16=116
15+12+9+20+22+15+12+11=116
8+13+7+10+6+11+11+5+8+16+7+11=113

となります。

組み合わせの生成にはRubyに用意されている「combination」という関数を使うと簡単です。また、配列の和はループで求めても構いませんが、Rubyでは「inject」がよく使われています。（Ruby2.4以降ではArray#sumを使うこともできます）

今回の問題を解くには、駅間の距離が最小のものを探し、その最大値を求めると良さそうです。これを実装すると、以下のように書けます。

組み合わせを使う問題点

Rubyを使うと簡単に組み合わせを実装できて便利ですが、今回の解き方では問題があります。それは、nの数が増えると組み合わせの数が膨大になることです。29個からn個の駅を選ぶとき、n=3であれば29個から3個を選ぶ組み合わせなので、(29×28×27)/(3×2×1)=3654通りです。ただ、nが大きくなるとこの数はどんどん大きくなります。

n	組み合わせの数
1	29
2	406
3	3,654
4	23,751
5	118,755
6	475,020
7	1,560,780
…	…

つまり、組み合わせが膨大になるとそれだけ処理に時間がかかります。今回の問題であれば、n=8くらいになると非常に時間がかかります。今回のように、n=14まで調べようとすると、もう少し工夫が必要です。

間隔が短い方から順に調べてみる

処理に時間がかかるのは、組み合わせをすべて調べているからです。しかし、実際にはすでに配置できた間隔よりも短い間隔を調べる必要はありません。

そこで、人を配置する間隔を小さい方から順に増やしながら、配置できなくなるまで調べていきます。このとき、間隔を足したときの合計が1周の距離を超えていないか、ちょうど1周の距離であれば配置できたといえます。配置できなくなる間隔まで調べられると探索は終了です。

例えば、Rubyの場合は以下のように実装できます。

このように変更すると、今回の問題であればnを増やしても一瞬で処理できます。この前から順に調べていく方法は「線形探索」と呼ばれます。

二分探索するように工夫する

今回の問題であれば処理速度を考えるほどではありませんが、もう少し駅の数が増えた場合などを考えると、線形探索よりも二分探索を使う方法もあります。二分探索は辞典から探したいキーワードを探すときに、適当に開いたページより前か後か考えながら目的のキーワードにたどり着くことに似た探索方法です。

つまり、人を配置する間隔として調べる範囲を少しずつ絞り込みながら、境界となる間隔が求められるまで調べていきます。境界が見つけられると探索は終了で、線形探索よりも圧倒的に高速に検索できます。

チェックする処理は上記と同じ内容を使えますので、二分探索する部分のみ変更すると、Rubyでは以下のように実装できます。

このように変更すると、駅の数が増えても一瞬で処理できます。

今回のポイント

組み合わせを求める処理はRubyなどの言語では簡単に実装できますが、他のプログラミング言語で実装してみるのも勉強になると思います。ぜひ試してみてください。

ただ、今回の問題を解く場合は線形探索や二分探索を考えるほうが良いでしょう。ここで、どちらを選ぶのか、という問題があります。企業のシステムでも、開発した当初はデータ件数が少なく、線形探索で十分な場面は少なくありません。線形探索のほうが簡単に実装できるため、とりあえず線形探索を使う場合もあるでしょう。

しかし、使っているうちにデータの件数が増え、線形探索だと処理に時間がかかる場合があります。このような場合、二分探索への変更を検討することになり、最初から二分探索で実装しておけばよかったと後悔することもあるでしょう。

たしかに線形探索の方が実装やテストは簡単ですが、ソースコードを見比べると二分探索でもそれほど難しくありません。もちろん単調に増加・減少しないなど、二分探索が使えない場合もありますが、二分探索を自力で実装できるように練習しておきましょう。

今月の問題

この連載では、毎月1回問題を出題し、次回にその解答や解説、アルゴリズムの紹介を行います。問題を解く速さを競うわけではありませんが、解いた方は自由にオリジナルの解答を公開していただいて構いません。

【今月の問題】
駅などに設置されているコインロッカー。
スーツケースなどの荷物も預けられる大きなサイズと、手荷物だけを預ける小さなサイズがあります。
コインロッカーを設置できる場所には制限があるため、これらのサイズを組み合わせて配置することにします。

ここで、大きなサイズは横1×縦2、小さなサイズは横1×縦1とします。
これらを横m×縦nのサイズに積み重ねて隙間なく配置するとき、その配置が何通りあるか求めるプログラムを作成してください。
なお、m, nともに10以下の整数とします。

例えば、m=3, n=3のとき、次の27通りがあります。

（著者プロフィール）

WRITING：増井敏克（マスイトシカツ）

増井技術士事務所　代表。技術士（情報工学部門）、テクニカルエンジニア（ネットワーク、情報セキュリティ）、その他情報処理技術者試験に多数合格。また、ビジネス数学検定1級に合格し、公益財団法人日本数学検定協会認定トレーナーとしても活動。「ビジネス」×「数学」×「IT」を組み合わせ、コンピュータを「正しく」「効率よく」使うためのスキルアップ支援を行っている。著書に『エンジニアが生き残るためのテクノロジーの授業』『おうちで学べるセキュリティのきほん』『プログラマ脳を鍛える数学パズル』『もっとプログラマ脳を鍛える数学パズル』『図解まるわかりセキュリティのしくみ』（翔泳社）、『プログラミング言語図鑑』『シゴトに役立つデータ分析・統計のトリセツ』（ソシム）がある。