こちらの記事は次のような方のニーズに応えるために書いています。
- 基本情報技術者試験を受けようと思うけど、アルゴリズムについて知りたい！
- アルゴリズムの基本的な考え方を教えて！
- アルゴリズムってどういう意味？
アルゴリズムは基本情報技術者試験では必須の知識です。今回はこのアルゴリズムについて解説していきます。
基本情報技術者試験のアルゴリズムとは？
基本情報技術者試験では、アルゴリズムを理解する必要があります。というよりも、理解できていない場合、合格は極めて難しいです。
その理由は、以下の基本情報技術者試験の午後試験科目（１５点問題は２問選択）において、擬似言語２５点・ソフトウェア開発、プログラミング２５点の合計５０点が、アルゴリズムを理解できていないとほぼ解答できないため、基本情報技術者試験の合格基準点６０点に到達するのが難しくなります。
私が基本情報技術者試験に合格した際の体験記は以下のリンクに掲載しています。
アルゴリズムとは？
アルゴリズムの意味
アルゴリズムは下記のような意味があります。
問題を解決するための方法や手順のこと。問題解決の手続きを一般化するもので、プログラミングを作成する基礎となる。アルゴリズムは1つの問題に対し、複数ある場合が多い。たとえば、文字をアルファベット順に並べ替えるには、複数のアルゴリズムが考えられる。アルゴリズム次第で、プログラムのサイズや汎用性などが変わってくるため、効率的と思われるものをプログラムに採用する。アルゴリズムは流れ図（フローチャート）を用いて図式化される。
ASCII.jpデジタル用語辞典より
アルゴリズムの具体例
説明を読むと難しく感じますが、要は手順、と考えておけばいいのかなと思います。
たとえば、下の図でA地点からB地点に行くまでにはどういった方法があって、どれが一番早く到達するかといった検討です。
このくらい単純な図式だと、A→２→３→B地点と行くのが最も時間が短い、というのがわかります。これを算出するには、
- A地点→１→B地点： ７分＋１４分＝２１分
- A地点→２→B地点： ８分＋１２分＝２０分
- A地点→２→３→B地点：８分＋３分＋８分＝１９分
- A地点→３→B地点： １５分＋８分＝２３分
というように総当りで確認するのが確実です。
情報技術者試験ではおなじみのクリティカルパス法による所要期間の見積もりも同じように計算しますよね。
こうした手順の算出方法がアルゴリズムであり、これを理解することが基本情報技術者試験の鍵になります。なお、ここでいうアルゴリズム（＝手順）というのは、計算方法そのものではなくて、考え方です。
もう少し具体的に説明しますと、上の図式では、
- A地点からB地点まで行く方法を全て調べる（合計４ルート）
- ４ルートすべての所要時間を計算する
- 最も早い時間がどれかを選ぶ
という３つの手順を用いていることがわかります。
さらに手順を細分化すると、
「A地点からB地点まで行く方法を全て調べる（合計４ルート）」というのは、
- A地点からのルートが何通りあるかを調べる
- A地点から１つ進んだところからのルートが何通りあるかを調べる
- これをB地点に到達するまで繰り返す
という手順に分かれます。
また、「４ルートすべての所要時間を計算する」というのは、
- 各ルートを通過するときの所要時間を、B地点に到達するまで合計していく
ということであり、「最も早い時間がどれかを選ぶ」というのは、
- 最も短い時間のルートのみを残す
ということになります。
つまり、普段ならば頭の中でぱっと計算していることも、手順を判断しているんですね。これを細かく分類して、条件分岐や計算を加えていくのがアルゴリズムの考え方ということになります。
コンピュータになぜアルゴリズムが必要か
なぜ、こういうアルゴリズムの考え方が必要か、というとコンピュータにはこうした手順を教えてあげないと動いてくれないからです。
人間ならば「A地点からB地点まで最も早く到達ルートはどれですか？」と質問するだけで答えを出せますが、コンピュータには先ほど書いたとおり、
- A地点からB地点まで行く方法を全て調べて
- すべてのルートの所要時間を計算して
- 最も早い時間がどれかを選んで
と伝えなければなりません。しかも行く方法の調べ方も、所要時間の計算方法も、最も早い時間の選び方もすべてプログラムという文字で伝えてあげなければなりません。
もし伝えなければ、コンピュータは何もしませんし、自分で考えてはくれません。
このプログラムを考える作業は非常に面倒ですし、頭で色々と考えなければなりません。
この作業ができるかどうかが、基本情報技術者試験に合格できるレベルのアルゴリズムが習得できるかの鍵になります。
もちろん、世間でいうプログラム開発をされている方にとっては簡単すぎる内容なのでしょうが、そうした世界で生きていない場合は、その最初の一歩にたどり着くまでが本当に大変です。
ですので、最初は難しくて当然です。少しずつ慣れていけばいいと思います。
まずは今回ご紹介したような簡単な形で、プログラムの記述は別として、どういうことをコンピュータに教えてあげれば答えを計算してくれるか、ということを考えてみるのがアルゴリズム理解のきっかけになるかと思います。
Excelマクロでアルゴリズムを表現
前置き
今回ご紹介したアルゴリズムは、最も早く到達できるルートをコンピュータに探す命令を出すための手順ですので、プログラム化が可能です。
そして、ExcelマクロはVBAというプログラムを利用したものですのでこうしたアルゴリズムをプログラムとして表現することが可能です。
なお、今回はどういった手順で判断がおこなわれていくのかを追っていくためにも、再帰処理などは使用せずに、そのままコードを羅列して表現しています。
もっと効率的な方法ももちろんあるのですが、アルゴリズムを理解していくには、プログラムのコードを追いながら、変数や条件分岐の流れを追っていくことが大切ですので、この方式をごｓ
コードのご紹介
まず、Excelに前提条件の準備をします。
プログラム化するにあたり、図で表現されている道順を文字と数値で表現します。
そして、この文字と数値を処理するコードを書きます。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 | Option Explicit Sub FindShortest() ' ↓繰返用 ↓合計時間 ↓分岐前時間↓ルート↓分岐前ルート Dim i, j, k, l, total_time, pass_time, root, org_root, _ end_point, prev_point, root_number, min_time, count '↑到着地点↑分岐前地点 ↑ルート数 ↑最短時間 ↑カウント '結果表示をクリア Range(Cells(2, 5), Cells(100, 6)).Clear 'ルート数確認 root_number = ActiveSheet.Cells(20000, 1).End(xlUp).Row - 1 'カウンター始動 count = 1 '1回目の分岐 Aからの出発ルートを探す For i = 1 To root_number end_point = "A" '出発地がAならばルートや時間を記録、そうでなければパス If Cells(i + 1, 1) = end_point Then root = Cells(i + 1, 1) total_time = Cells(i + 1, 2) end_point = Cells(i + 1, 3) 'B地点に到着していたらExcelにルートと時間を出力 If end_point = "B" Then root = root & "B" Cells(count + 1, 5) = root Cells(count + 1, 6) = total_time count = count + 1 Else End If '2回目の分岐を始めるまえの情報を記憶しておく org_root = root prev_point = end_point pass_time = total_time '2回目の分岐 For j = 1 To root_number '2回目の分岐判定を始める前の状態にリセット root = org_root end_point = prev_point total_time = pass_time '出発地が前回の到着地ならばルートや時間を記録、そうでなければパス If Cells(j + 1, 1) = end_point Then root = root & Cells(j + 1, 1) total_time = total_time + Cells(j + 1, 2) end_point = Cells(j + 1, 3) 'B地点に到着していたらExcelにルートと時間を出力 If end_point = "B" Then root = root & "B" Cells(count + 1, 5) = root Cells(count + 1, 6) = total_time count = count + 1 Else End If '3回目の分岐 For k = 1 To root_number '出発地が前回の到着地ならばルートや時間を記録、そうでなければパス If Cells(k + 1, 1) = end_point Then root = root & Cells(k + 1, 1) total_time = total_time + Cells(k + 1, 2) end_point = Cells(k + 1, 3) 'B地点に到着していたらExcelにルートと時間を出力 If end_point = "B" Then root = root & "B" Cells(count + 1, 5) = root Cells(count + 1, 6) = total_time count = count + 1 Else End If Else End If Next k Else End If Next j Else End If Next i '全ルート中最短時間の判定 min_time = Cells(2, 6) For l = 1 To count - 2 If Cells(l + 2, 6) < min_time Then min_time = Cells(l + 2, 6) Else End If Next l '前ルート中最短時間のルートのセルを黄色・太字にする For l = 1 To count If Cells(l + 2, 6) = min_time And Cells(l + 2, 6) <> "" Then Range(Cells(l + 2, 5), Cells(l + 2, 6)).Interior.Color = 65535 Range(Cells(l + 2, 5), Cells(l + 2, 6)).Font.Bold = True Else End If Next l End Sub |
使い方
下記のZIPファイルをダウンロード、解凍してからExcelを開き、マクロを有効にします。
その後、開発タブ→Visual BasicでVBAの画面を開きます。この操作は、
開発タブがない場合は、こちらのリンクをご参照の上Excelマクロの初期設定をしてください。
VBAの画面では、表示→ローカルウィンドウを選択して、ローカルウィンドウを表示してください。
下記のようにExcelの画面とVBAの画面を並べておくと見やすいです。
ローカルウィンドウが表示されていることを確認したら、再生ボタン（マクロ実行ボタン）を押して開始です。
すぐに結果が出ます。
A→２→３→Bが最短ルート、所要時間は１９分です。
これだけだとよくわかりませんね。
今度は、
すると、先ほど最初から最後まで実行されたプログラムが、１行ずつ実行されます。
これで、変数の動きを確認しながら、どういった処理がされていくかを確認することができます。プログラムが進むたびに数字が書き換わっていって、答えを導き出していく動きがわかると思います。
アルゴリズムの例の説明は以上です。
いきなりこのプログラムの内容を理解するというよりは、アルゴリズムというのは、こうした動きで結果を出すための手順のことを言うんだ、ということをなんとなく理解してもらえればいいと思います。
ここまでお読みいただきましてありがとうございました。
