マンドラゴラ収穫順序問題

04

　今回の、マンドラゴラ収穫順序問題解決プログラムの作成にあたって、僕は僕の知るアルゴリズムの中で最も有用と思われるものを選択した。

　すなわち、ダイクストラ法だ。

　ダイクストラ法とは、グラフ上の二点間の最短経路を調べるアルゴリズムである。身近な例を挙げれば、ゲームなどで活用されている。

　たとえば、ここにA、B、C、D、Fの五つの街があるとする。

　AからはBとCに行ける。AB間の距離は10。AC間の距離は17。

　BからはAとDとFに行ける。BA間の距離はABと同じ。BD間の距離は7。BF間の距離は21。

　CからはAとDとFに行ける。CA間の距離はACと同じ。CD間の距離は5。CF間の距離は13。

　DからはBとCとFに行ける。DB間の距離はBDと同じ。DC間の距離はCDと同じ。DF間の距離は3。

　このような条件で、AからDへの最短経路を調べることができるのが、ダイクストラ法である。

　以上の条件をグラフに落とし込み、それを行列にしてプログラムに与える。するとダイクストラ法のアルゴリズムが動いて結果を出す。

　詳しい説明は省くが、この場合の最短経路はA→B→D→Fとなり、辿った距離の和は20になる。

　今回は、この距離を汚染度で置き換えて考える。

　たとえば、ここにマンドラゴラ農地A、Bがあるとする。

　Aで育てられている品種の収穫時に得る汚染度を2[/s]、AからBへの移動時間を300[s]とすると、Aを収穫したあと、Bへ行く時の汚染度は600。

　Bで育てられている品種の収穫時に得る汚染度を4[/s]、AからBへの移動時間を300[s]とすると、Bを収穫したあと、Aへ行く時の汚染度は1200。

　話を簡単にするため、意図的にいくつかの変数を無視しているが、このようにして有向グラフの弧の重みを決定すればダイクストラ法によって適切な収穫順序を求めることが可能となる。

　ちなみに、重みは扱いやすさと汚染計測器とのかねあいを考えて、0〜100の間で正規化した値を使用する。具体的な計算式は以下の通りである。

重み = 正規化関数（P_h + P_d）　

P_h = 汚染度×一本あたりの収穫時間×（農地面積×単位面積あたりの収穫可能本数）

P_d = 減衰された叫びの平均音量×汚染係数×（Aの農地面積×単位面積あたりの収穫可能本数）×min（真空になるまでの時間, 次の農地までの移動時間）

P_hはマンドラゴラの収穫作業中に受ける精神汚染の量。

P_dは真空になる前のカプセル内のマンドラゴラから受ける精神汚染の量。

　こうすれば、ダイクストラ法はちゃんと効率の良い収穫順序を導いてくれるはずだ。（日本の安全に対する意識は他国に比べて余りにも高いので、こちらでマージンを取るまでもなく、法律で規定された基準値をそのまま使用して良いと判断した。新山さんの家も元々そういうことで作業していたらしい）

　……とはいえ、そもそもダイクストラ法は最短経路を求めるアルゴリズムである。最短経路に含まれないものについては捨て置くもの。

　しかしマンドラゴラの収穫において同じことをするわけにはいかない。

　育てたマンドラゴラはすべて収穫しなくてはいけないのだから。

　そこで、実際に使用する際はすべての農地で収穫を済ませるまでスタート地点を変えて最小汚染順序を求め続ける。

　具体的には以下のようにする。

1. 汚染度が最小（あるいは、何らかの理由により最優先で収穫しなくてはならない）品種の農地をスタート地点に設定する。

2. ダイクストラ法を使って求めた通りに収穫（既定値をオーバーしそうになったら後日再開する）

3. 収穫が済んだ農地を除く（このとき、グラフの表現行列の適切なものに書き換える）

4. 1に戻る

　これをすべての収穫が終わるまで繰り返す。

　……正直、大学二年生の僕には骨が折れるプログラムだった。データ構造についての知識すら十分とは言えないのだ。わけが分からなくて、マンドラゴラの叫びを聞くまでもなく気が狂いそうになった。

　だけど、新山さんのためと思うと、諦めるわけにはいかなかった。

　そうして、僕は期日までにプログラムの構築を終え――いよいよ、マンドラゴラ収穫の日がやってきた。