パズルで鍛えるアルゴリズム力
概要
この記事は著書パズルで鍛えるアルゴリズム力の一部分を端的にまとめたものになります。
解説するアルゴリズムは以下の３種類になります。
- 力まかせ探索（しらみつぶし探索）
- 深さ優先探索
- 幅優先探索
また、記事内で出されるクイズも書籍内に記載のあるものを使用しています。
クイズ（10パズル）
Q1
解答
解答は一例のため、他にも解答が存在します
Q2
こちらは2004年の開成中学校の入試問題で出題された有名な問題です。
解答
解答は一例のため、他にも解答が存在します
アルゴリズム
- 力まかせ探索（brute-force search）
- 逆ポーランド記法(reverse Polish notation)
力まかせ探索（brute-force search）
単純だが非常に汎用的な計算機科学の問題解決法であり、全ての可能性のある解の候補を体系的に数えあげ、それぞれの解候補が問題の解となるかをチェックする方法である。
逆ポーランド記法(reverse Polish notation)
加算を表す演算子+を、被演算子である 3 と 4 の後（右）に置いて、以下のよう記述する。
3 + 4 => 3 4 +
また、逆ポーランド記法を用いることで、()が不要になります
(3 + 4) * (1 - 2) => 3 4 + 1 2 - *
この逆ポーランド記法とスタック（last-in first-out）を用いることで、計算手順が簡単になります。
例えば、6 * ( 1 + 2 ) - 8ような計算式があったときに、
逆ポーランド記法を用いると6 1 2 + * 8 -のように表すことができます。
逆ポーランド記法で表された数式を一文字ずつ取り出して、配列に格納していきます。
配列に格納された値が数字の場合は、そのまま格納。演算子の場合は、配列の末尾から２つの数字を取り出して計算し、結果を再度配列の末尾に格納します。
計算の手順を以下のテーブルにまとめました。
| 逆ポーランド記法 | 計算の過程 |
|---|---|
| [] | |
| 6 | [6] |
| 6 1 | [6, 1] |
| 6 1 2 | [6, 1, 2] |
| 6 1 2 + | [6, 3] |
| 6 1 2 + * | [18] |
| 6 1 2 + * 8 | [18, 8] |
| 6 1 2 + * 8 - | [10] |
組み合わせの総和を考える
使用するアルゴリズムの基礎情報がわかったところで改めて、クイズに落とし込んで考えてみます
前途でも述べたように、力まかせ探索では、解候補数に比例してコストが増大するため、実装前にコストを見積もる必要があります。
４つの数字それぞれが一意で１回ずつしか使えない場合の組み合わせは24通りです
（4つの数字が一意でない場合はさらに少ない組み合わせ数になります）
また、演算子+-*/を１回または複数回使用する場合の、３つ並べた組み合わせは64通りです。
()を用いない場合は、この２つの組み合わせの総和が解候補数になります。
さらに、()を用いた場合数字と演算子の羅列パターンは何通りあるでしょうか？
1 + 2 * 3 + 4と(1 + 2) * 3 + 4は数字と演算子の羅列パターンは同じですが、解が異なるため、別の場合としてカウントしなければいけません。
そのため、逆ポーランド記法を用いて、数字と演算子の配置パターンも組み合わせ総数に影響してきます。
ただ、逆ポーランド記法の数字と演算子の配置パターンは以外にも以下の5通りしかありません。
x = 数字、 o = 演算子
1. xxxxooo
2. xxxoxoo
3. xxoxxoo
4. xxoxoxo
5. xxxooxo
よって、今回のクイズの組み合わせ総数は5 x 24 x 64 = 7680通りとなります。人間の手で8000通り近くの計算を行うことは困難ですが、コンピュータの場合は問題なく高速に計算することができます。
力まかせ探索を実装してみた
これらのことを踏まえて、プログラミングで記載してみました。
コード
実行環境
クイズ（数独）
Q1
解答
Q2
解答
アルゴリズム
- グラフ(graph)
- 深さ優先探索（depth-first search）
グラフ(graph)
グラフとは、ノード（頂点）群とノード間の連結関係を表すエッジ（枝）群で構成されるものを言います。
グラフには、エッジに向きがついている有向グラフとエッジに向きがついていない無向グラフの２種類があります。
グラフは数独に限らず、様々なアルゴリズムで多く用いられることがあります。
深さ優先探索（depth-first search）
深さ優先探索(DFS)とは、グラフのより深いところへと可能な限り潜っていき、これ以上深いところへは進めない状態になった場合、一歩も戻って次の分岐を試す、という動きを繰り返す探索法です。
下記のグラフに対して、ノードの番号のような順序で探索を行なっていきます。
深さ優先探索の特徴として、探索候補ノードの記録にスタックを使用し、最後に追加された候補を優先的に探索するLIFO(Last-In First-Out)方式で探索していきます。
深さ優先探索では、上記特性から辞書ごとに並んだデータに対して、最初にヒットした結果だけが欲しいといったような場合に適しています。
数独をグラフに落とし込んでみる
数独をグラフとして表すと、下記のような画像のようになります。
左から数字を当てはめていき、縦・横・同じブロック内に同じ数字が入るまで、数字を入れていきます。
左上から空いている箇所を探索し、その箇所に入れることのできる数字をピックアップします。
一つ数字を入れるごとに再帰関数でグラフの深くを探索していきます。
深さ優先探索を実装してみた
これらのことを踏まえて、プログラミングで記載してみました。
コード
実行環境
クイズ（迷路）
Q1
解答
解答は一例のため、他にも解答が存在します
アルゴリズム
- 幅優先探索（breadth-first search）
幅優先探索（breadth-first search）
幅優先探索（BFS)とは、出発点に近いところから順に探索し、探索可能なパターンを同時に洗い出す探索法です。幅優先探索では、深さ探索とは異なり、一度探索した場所は戻らずに探索を続けます。
幅優先探索の特徴として、探索候補ノードの記録にキューを使用し、探索するごとにキューから取り出し、再度キューに入れなおす作業を行います。
幅優先探索では、複数のパターンを同時に探索することができるため、最短経路を求める問題に適しています。
一方で同時に複数のパターンの探索を行うため、メモリ消費量が多いデメリットがあります。
迷路をグラフに落とし込んでみる
迷路をグラフとして表すと、下記の画像のようになります。
スタートから探索可能な経路の選択を検索し、探索できる方向にそれぞれ進み、
まず、スタートから１手で行けるマス全てに「１」と書き込みます。続いて、「１」のマスから１手で行けるマスに「２」と書き込みます。これをゴールまで続けていくことで、同時に探索を行うことができます。
力まかせ探索を実装してみた
これらのことを踏まえて、プログラミングで記載してみました。
コード
実行環境
まとめ
- 力まかせ探索...アルゴリズムの基礎。強力だが、コストを考慮して実行しないといけない
- 深さ優先探索...グラフの深い方へ探索していく。一つの解を求めるのに適している。
- 幅優先探索...複数同時の探索を行う。最短経路問題などの最適解を求める問題に適している。
力まかせ探索、深さ優先探索、幅優先探索の３つのアルゴリズムを解説しましたが、それぞれのアルゴリズムごとに特徴があり、問題ごとに使い分けることによってより効率の良い解を得られることがわかりました。ただ、どのアルゴリズムにも共通して言えることは、アルゴリズムを適用させる前にはしっかりとコストを計算し、どのアルゴリズムが適しているかを見極める必要があるという点です。また、関係のない問題に対してもアルゴリズムにどう適用させていくのかという技術も必要になってきます。今回紹介はしませんでしたが、一見グラフは関係なさそうな有名な「川渡り問題」もグラフに置き換え、幅優先探索を使うことで最適な解を得られることができます。この著書では、そういったさまざまな問題に対して、どのようにアルゴリズムに落とし込んでいくかという点も学ぶことができました。また、プログラムも書いてあるため、アルゴリズムを学術的というよりもより実践的に学ぶことができる本です。
今回紹介したアルゴリズムは初級編なので、もっと発展的なものを知りたいと思った方はぜひ、著書を手に取って見てください！
Discussion