日常生活を裏で支えるアルゴリズム

どうも、みーくんです。

最近は気温の寒暖差が激しいだけでなく花粉症の時期でもあるので、喉は痛いわ鼻は詰まるわで地獄絵図になっております。

そのため、この3連休は家で安静にしているのですが、何か生産性のあることをしたいと思い、資格に手を出し始めました。「基本情報技術者試験」というIT業界に携わる者にとって登竜門的な国家資格なのですが、まだ取得していなかった(正確には会社側から資格取得を義務づけられていなかった)ので、持っておくに越したことはない理論で勉強しております。現役システムエンジニア界隈では「基本情報は持っていても意味がない。実務経験がモノを言う。」だとか「資格取得というよりは、学んだ内容を理解するのが大切。」だとか「取得しなかったからといって会社クビになるわけじゃないから、暇潰しに受験しに行くくらいの心持ちで良い。」だとか「アルゴリズムなんて仕組みを理解するだけ。そんなことよりアルゴリズムをプログラム言語で実装しろ。」だとかいう意見が跳梁跋扈しておりますが、私はSIerの営業職なので、まぁ一定のアピールにはなるかなと思ったわけです。

今日は基本情報技術者試験の概要と、その中で身近な場面で生かされているアルゴリズムについて述べていきたいと思います。

基本情報技術者試験とは

主にプログラマ・システムエンジニア等のIT職に従事する人、あるいはこれから従事しようとする人を対象にした経済産業省が認定する国家試験で、受験料は税込5700円です。午前試験と午後試験に分かれ、それぞれの試験時間は150分になります。午前試験と午後試験の双方で6割以上得点すれば合格となります。

午前試験は9:30～12:00の間で行われ、問題数は小問80問です。出題形式は四肢択一になります。出題範囲は以下の通りです。

・テクノロジ基礎理論

・コンピュータシステム

・技術要素

・開発技術

・プロジェクトマネジメント

・サービスマネジメント

・システム戦略

・経営戦略

・企業と法務

午後試験は13:00～15:30の間で行われ、問題数は大問7問です。出題形式は多岐択一になります。出題範囲は以下の通りです。

・情報セキュリティ

・ハードウェア

・ソフトウェア

・データベース

・ネットワーク

・ソフトウェア設計

・プロジェクトマネジメント

・サービスマネジメント

・システム戦略

・経営戦略、企業と法務

・データ構造及びアルゴリズム

・C

・COBOL

・Java

・アセンブラ

・表計算

このうち、「情報セキュリティ」「データ構造及びアルゴリズム」は必須問題で、その他は選択式になります。

ダイクストラ法

今回ご紹介するのは、午後問題の「データ構造及びアルゴリズム」の過去問題として出題された「ダイクストラ法」です。

ダイクストラ法(Dijkstra's Algorithm)とは、始点と終点が存在し、そこに至る経路が複数ある中で、どの経路を辿れば最短で終点まで到達できるかを探索するためのアルゴリズムです。これを人力でやろうとすると、まずすべての経路を洗い出し、それの合計値をそれぞれ出して比較することになり、経路が多ければ多いほど非効率です。そのため、アルゴリズム化してコンピュータに任せてしまえば早く終わるよね、という趣旨になります。歴史を辿ると割と最近で、1959年にオランダの計算機科学者エドガー・ダイクストラ(Edsger Wybe Dijkstra)によって考案されました。現代では、カーナビの経路探索や鉄道の経路案内において活用されています。
ここでの前提となるのが、地点と、地点間を結ぶ距離をグラフ化するということです。例えば、以下のようになります。

ここでの丸は地点を表しており「ノード」、線は地点間を結ぶ距離を表しており「エッジ」と呼びます。エッジの隣に付随している数値は地点間の距離を表しており「コスト」と呼びます。このグラフは隣接行列でも表現することができます。補足として、以下掲載します。

例えば地点Aから地点Bに向かうためには1のコストがかかるので、2行目3列では1という数値が入っています。この隣接行列を見ていただければ気づく方もいらっしゃると思いますが、左斜めに入っている0を境目として線対称になっています。これは、ダイクストラ法において前提となるグラフが無向グラフと呼ばれるものだからです。無向グラフとは簡単に申し上げると、地点Aから地点Bに行くこともできるし、地点Bから地点Aにも行くことができるということです。進行の向きが制限されないということにもなりますね。
さて、例示したグラフの場合、ダイクストラ法を用いたアルゴリズムではどのような動きをするのでしょうか。段階を踏んで説明します。

①

Aの距離を0とし、それ以外の距離は未確定なので∞とする。確定の距離は赤色で表示している。

②

Aと隣接しており、且つ未確定の地点B、C、Dについて、確定した地点を経由した場合の距離を計算する。未確定の距離は緑色で表示している。

③

未確定の地点のうち、Bへ至る経路が最も距離が小さいのでBを確定する。

④

Bと隣接しており、且つ未確定の地点E、Fについて、確定した地点を経由した場合の距離を計算する。

⑤

未確定の地点のうち、Dへ至る経路が最も距離が小さいのでDを確定する。

⑥

Dと隣接しており、且つ未確定の地点Gについて、確定した地点を経由した場合の距離を計算する。

⑦

未確定の地点のうち、Eへ至る経路が最も距離が小さいのでEを確定する。

⑧

Eと隣接しており、且つ未確定の地点Fについて、確定した地点を経由した場合の距離を計算する。

⑨

未確定の地点のうち、Fへ至る経路が最も距離が小さいのでFを確定する。

⑩

Fと隣接しており、且つ未確定の地点C、Hについて、確定した地点を経由した場合の距離を計算する。この場合、以前出ていた7よりも新しく計算した6の方が距離が短いので6の数字で上書きする。

⑪

未確定の地点のうち、Cへ至る経路が最も距離が小さいのでCを確定する。

⑫

Cと隣接しており、且つ未確定の地点Gについて、確定した地点を経由した場合の距離を計算する。この場合、以前出ていた7の方が距離が短いので7の数字で上書きする。

⑬

未確定の地点のうち、Gへ至る経路が最も距離が小さいのでGを確定する。

⑭

Gと隣接しており、且つ未確定の地点Hについて、確定した地点を経由した場合の距離を計算する。この場合、以前出ていた10よりも新しく計算した9の方が距離が短いので9の数字で上書きする。

⑮

すべての地点を網羅した最短距離が「9」であると確定した。

このようにダイクストラ法は、不要な経路が分かった時点で切り捨てるので計算を省略できることが特徴です。このアルゴリズムを疑似言語で表現し、プログラム言語(JavaScript)で実装すると以下のようになります。

-------------------------------------------------(以下疑似言語)-------------------------------------------------

----------------------------------------------(以下JavaScript)--------------------------------------------------

/**
 * ノード
 */
function Node(id) {
    this.edgesTo      = [];
    this.edgesCost    = [];
    this.done         = false;
    this.cost         = -1;
    this.id           = id;
    this.previousNode = null;
}
Node.prototype.addNode = function (node, cost) {
    this.edgesTo.push(node);
    this.edgesCost.push(cost);
};

function createNodes() {
    var node1 = new Node(1); // start
    var node2 = new Node(2); // top
    var node3 = new Node(3); // center
    var node4 = new Node(4); // bottom-left
    var node5 = new Node(5); // bottom-right
    var node6 = new Node(6); // goal

    node1.addNode(node2, 5);
    node1.addNode(node3, 4);
    node1.addNode(node4, 2);

    node2.addNode(node1, 5);
    node2.addNode(node6, 6);
    node2.addNode(node3, 2);

    node3.addNode(node2, 2);
    node3.addNode(node1, 4);
    node3.addNode(node4, 3);
    node3.addNode(node5, 2);

    node4.addNode(node1, 2);
    node4.addNode(node3, 3);
    node4.addNode(node5, 6);

    node5.addNode(node4, 6);
    node5.addNode(node3, 2);
    node5.addNode(node6, 4);

    node6.addNode(node2, 6);
    node6.addNode(node5, 4);

    return [
        node1, node2, node3, node4, node5, node6
    ];
}


function main() {

    var nodes = createNodes();

    // start node is first node
    nodes[0].cost = 0;

    while (true) {
        var processNode = null;

        for (var i = 0; i < nodes.length; i++) {
            var node = nodes[i];

            // 訪問済み or まだコストが未設定
            if (node.done || node.cost < 0) {
                continue;
            }

            if (!processNode) {
                processNode = node;
                continue;
            }

            // 一番小さいコストのノードを探す
            if (node.cost < processNode.cost) {
                processNode = node;
            }
        }

        if (!processNode) {
            break;
        }

        processNode.done = true;

        for (var i = 0; i < processNode.edgesTo.length; i++) {
            var node = processNode.edgesTo[i];
            var cost = processNode.cost + processNode.edgesCost[i];

            // コストが未設定 or コストの少ない経路がある場合はアップデート
            var needsUpdate = (node.cost < 0) || (node.cost > cost);
            if (needsUpdate) {
                node.cost = cost;
                node.previousNode = processNode;
            }
        }
    }

    console.log('Has been done to search path.');
    console.log(nodes);

    var goalNode = nodes[5];
    console.log('Shoten cost is ' + goalNode.cost);

    console.log('Shoten path');

    console.log('=====================');
    var path = 'Goal -> ';
    var currentNode = goalNode;
    while(true) {
        var nextNode = currentNode.previousNode;
        if (!nextNode) {
            path += ' Start';
            break;
        }
        path += nextNode.id + ' -> ';
        currentNode = nextNode;
    }

    console.log(path);
    console.log('=====================');
}

// Start this program.
main();