こんにちは、D3の星です。

グラフ理論の続きを書こうと思っていて忘れていました。今回は私たちの日々の生活でも活躍しているアルゴリズムを紹介します。

 

有機化学において化合物の合成経路を考える際にグラフ理論の考え方が役に立つかもしれない、というお話をしてきました。

前graphtheory2回は最小の工程数を求めるための手法として「幅優先探索」を紹介しました。これはどの辺の「長さ」も全て 1 だから成功する方法でした。

今回はもう少し複雑な問題として「最もコストが小さい合成経路 (試薬の値段など)」を探すことを考えてみます。

 

この場合辺の「長さ」はそれぞれ違う値が設定されますが、実はこのような問題は日常生活でもよく現れます。

例えば、カーナビで目的地を設定すると経路が表示されますが、あれはどのようにして経路を決定しているのでしょうか？

一見無関係に思えるこれら二つの問題は、グラフ理論の上では本質的には同じ問題と言えるわけです。

ここではこうした問題を解く鍵となる「ダイクストラ法」と呼ばれるアルゴリズムを紹介します。

 

前回の幅優先探索の際に用いたグラフを再び用意しました。前回との違いは、各辺にコストを表す値が割り当てられていることです。

(試薬の値段等ならもっと大きな値となるでしょうが、ここでは簡潔にするため小さな値で計算することにします)

一番左の頂点を出発原料として、それぞれの化合物を合成するのにかかる最小のコストはどれくらいになるでしょうか。まずは前回の方法を試してみます。

 

1. 出発原料はコスト0とします。

2. 出発原料から一工程で到達できる化合物のコストを決定します。

3. 一つ前の操作でコストが決定した化合物から一工程で到達できる化合物のコストを決定します。

という操作を繰り返すはずでしたが、ここであることに気が付きます。中央に「コスト8」の化合物がありますが、本当に最小のコストは 8 で正しいでしょうか。

よく見ると工程数はかかるものの、コスト 7 で到達できる経路が存在しますよね。

このように、工程数と違ってすぐには最小コストが決定できないという点が重要で、幅優先探索を適用できません。

この段階でコストを 7 に更新すれば良いのですが、そうするとその先の化合物も全て計算し直しとなり、効率が悪くなってしまいます。

 

今回は最小コストを確定できていない化合物の先を計算したことで失敗してしまいましたが、逆に最小コストを確定できる化合物はないのか考えてみます。

まず、出発原料の最小コストは 0 で確定です。これは反応のコストが負の値になることはないからです (当たり前のことですが、これが重要です)。

一工程進めてみます。そうするとまだ最小コストが確定していないコスト 2 の化合物とコスト 8 の化合物ができます。

実は白い数字の中で最小の数字は、この値が最小コストとして確定します。これがダイクストラ法の肝です。

つまりコスト 8 の化合物はまだ確定してはいけなかったが、コスト 2 の化合物は確定して良かった、ということです。

そして、最小コストが確定した化合物から一工程進めて白い数字を追加し、最小の白い数字が最小コストとして確定する、この繰り返しです。

そして白い数字はまだ確定していないので、場合によっては上書きされます。コスト 8 はこの段階でコスト 7 に上書きされました。

これを繰り返すことで、先程のような無駄な再計算をなくすことができました。

 

今回は意外にも身近なところで活躍しているアルゴリズムを紹介しました。

グラフ理論に限らず、他分野の考え方を取り入れてみると慣れ親しんだ分野でもまた違った見え方をすることがあるかもしれません。