最短経路アルゴリズム
XlWingsを使ったアプリ での反応経路検索のアルゴリズムについて紹介する.
ダイクストラ法を少し改良したアルゴリズムを用いている.
ダイクストラ法では距離の比較しか行わないが, このアルゴリズムでは3つの項目を比較する.
律速段階の活性化エネルギー
反応のStep数
直前の素反応の活性化エネルギー
この順番(優先順位)で各項目の比較を行なう.
計算量
EQの数を \(V\) ,TS・PTの数を \(E\) とすると計算オーダーは以下の通りである. (ラフな計算なので正しいか分からないが...)
引数 |
計算量 |
|---|---|
pseudo_energy = False |
\(O(E log V)\) |
pseudo_energy = True |
\(O(EV log V)\) |
アルゴリズム解説(pseudo_energy=False)
青矢印はTSまたはPTを表し, 添え字の数字は活性化エネルギーである.
EQ0,EQ1,EQ3は同じ構造なのでGroup0としてまとめている.
図の説明
反応経路が確定したEQを灰色で塗りつぶす.
反応経路が確定した経路を赤矢印で表記する.
例としてEQ0を出発構造とする. 同じグループ間ではTS.PTがなくても移動できると考えることにする. よって,EQ1,EQ3へ経路を確定させることができる.
また同じグループ間での移動には活性化障壁はない(0)ものとする.
ただし,移動には軽微なコスト(0.001)を与えることにする.
確定ノード(EQ0,EQ1,EQ3)から移動可能な経路の探索を行なう.
まずはEQ1を考える.
EQ1->EQ5の経路があり,Ea=25である.異なるグループ間での移動はstep数を1増加させる.よってコストは[25,1.001,25]である.
EQ1->EQ10も同様に[40,1.001,40]である.
次にEQ3から移動可能な経路を探索する.
EQ3->EQ10へのコストは[30,1.001,30]であり,EQ1->EQ10よりEaが小さいのでコストを更新する.
またEQ3->EQ4のコストは[10,1.001,10]である.
これ以上探索はできないため,次にノードの確定を行なう
未確定のノード(EQ5,EQ10,EQ4)のなかで最もコストが低いEQ4を確定ノードとする.
確定ノードから移動可能な経路を探索する.
EQ4->EQ6, EQ->EQ7に移動可能である.この時のコストは,それぞれ[10,1.002,10],[10,1.002,10]である.
またEQ6,EQ7は直ちに確定ノードとなる.
確定ノード(EQ6,EQ7)から移動可能な経路を探索する.
EQ6->EQ10が可能であり,これはEQ3->EQ10よりも低いコスト([25,2.002,25])で移動可能なので,EQ10のコストを更新する.
またEQ7->EQ11は[50,2.002,50]である.
これ以上探索はできないため,次にノードの確定を行なう
未確定ノード(EQ5,EQ10,EQ11)の中でもっともコストが低いEQ5を確定ノードとする.(EQ10とEaが同じなのでstep数で判断した)
EQ5->EQ2へ移動可能であり,EQ2は直ちに確定ノードとする.
確定ノードから移動可能な経路を探索する.
EQ2->EQ9へ移動可能である.
直前のEaは20であり,EQ0->EQ1->EQ5->EQ2->EQ9の律速のEaは25なので[25,2.002,20]
これ以上探索はできないため,次にノードの確定を行なう
未確定ノード(EQ9,EQ10,EQ11)の中で最もコストの低いEQ9を確定ノードとする
確定ノードから移動可能な経路を探索する.
EQ9->EQ8が[25,3.002,10]のコストで移動可能である.
これ以上探索はできないため,次にノードの確定を行なう
未確定ノード(EQ8,EQ10,EQ11)の中で最もコストの低いEQ10を確定ノードとする.
EQ10->EQ8へ移動可能であり,これは直ちに確定ノードとなる.
確定ノードから移動可能な経路を探索する.
EQ10->EQ11
