######################
最短経路アルゴリズム
######################

:doc:`XlWingsを使ったアプリ<./other_lib>` での反応経路検索のアルゴリズムについて紹介する.

| ダイクストラ法を少し改良したアルゴリズムを用いている.
| ダイクストラ法では距離の比較しか行わないが, このアルゴリズムでは3つの項目を比較する.

- 律速段階の活性化エネルギー
- 反応のStep数
- 直前の素反応の活性化エネルギー

| この順番(優先順位)で各項目の比較を行なう.

計算量
=======

| EQの数を :math:`V` ,TS・PTの数を :math:`E` とすると計算オーダーは以下の通りである. (ラフな計算なので正しいか分からないが...)

.. csv-table::
   :header: 引数, 計算量

   pseudo_energy = False,  :math:`O(E log V)`
   pseudo_energy = True, :math:`O(EV log V)`

アルゴリズム解説(pseudo_energy=False)
==========================================

- 青矢印はTSまたはPTを表し, 添え字の数字は活性化エネルギーである.
- EQ0,EQ1,EQ3は同じ構造なのでGroup0としてまとめている.

.. figure:: ./algo_gif/step1.gif
   :scale: 40%
   :align: center

   図の説明

- 反応経路が確定したEQを灰色で塗りつぶす.
- 反応経路が確定した経路を赤矢印で表記する.

| 例としてEQ0を出発構造とする. 同じグループ間ではTS.PTがなくても移動できると考えることにする. よって,EQ1,EQ3へ経路を確定させることができる.
| また同じグループ間での移動には活性化障壁はない(**0**)ものとする.
| ただし,移動には軽微なコスト(**0.001**)を与えることにする.

.. figure:: ./algo_gif/step2.gif
   :scale: 40%
   :align: center

| 確定ノード(EQ0,EQ1,EQ3)から移動可能な経路の探索を行なう.
| まずはEQ1を考える.
| EQ1->EQ5の経路があり,Ea=25である.異なるグループ間での移動はstep数を1増加させる.よってコストは[25,1.001,25]である.
| EQ1->EQ10も同様に[40,1.001,40]である.

.. image:: ./algo_gif/step3.gif
   :scale: 40%
   :align: center

| 次にEQ3から移動可能な経路を探索する.
| EQ3->EQ10へのコストは[30,1.001,30]であり,EQ1->EQ10よりEaが小さいのでコストを更新する.
| またEQ3->EQ4のコストは[10,1.001,10]である.
| これ以上探索はできないため,次にノードの確定を行なう

.. image:: ./algo_gif/step4.gif
   :scale: 40%
   :align: center

| 未確定のノード(EQ5,EQ10,EQ4)のなかで最もコストが低いEQ4を確定ノードとする.

.. image:: ./algo_gif/step6.gif
   :scale: 40%
   :align: center

| 確定ノードから移動可能な経路を探索する.
| EQ4->EQ6, EQ->EQ7に移動可能である.この時のコストは,それぞれ[10,1.002,10],[10,1.002,10]である.
| またEQ6,EQ7は直ちに確定ノードとなる.

.. image:: ./algo_gif/step7.gif
   :scale: 40%
   :align: center

| 確定ノード(EQ6,EQ7)から移動可能な経路を探索する.
| EQ6->EQ10が可能であり,これはEQ3->EQ10よりも低いコスト([25,2.002,25])で移動可能なので,EQ10のコストを更新する.
| またEQ7->EQ11は[50,2.002,50]である.
| これ以上探索はできないため,次にノードの確定を行なう

.. image:: ./algo_gif/step8.gif
   :scale: 40%
   :align: center

| 未確定ノード(EQ5,EQ10,EQ11)の中でもっともコストが低いEQ5を確定ノードとする.(EQ10とEaが同じなのでstep数で判断した)
| EQ5->EQ2へ移動可能であり,EQ2は直ちに確定ノードとする.

.. image:: ./algo_gif/step9.gif
   :scale: 40%
   :align: center

| 確定ノードから移動可能な経路を探索する.
| EQ2->EQ9へ移動可能である.
| 直前のEaは20であり,EQ0->EQ1->EQ5->EQ2->EQ9の律速のEaは25なので[25,2.002,20]
| これ以上探索はできないため,次にノードの確定を行なう

.. image:: ./algo_gif/step10.gif
   :scale: 40%
   :align: center

| 未確定ノード(EQ9,EQ10,EQ11)の中で最もコストの低いEQ9を確定ノードとする

.. image:: ./algo_gif/step11.gif
   :scale: 40%
   :align: center

| 確定ノードから移動可能な経路を探索する.
| EQ9->EQ8が[25,3.002,10]のコストで移動可能である.
| これ以上探索はできないため,次にノードの確定を行なう

.. image:: ./algo_gif/step12.gif
   :scale: 40%
   :align: center

| 未確定ノード(EQ8,EQ10,EQ11)の中で最もコストの低いEQ10を確定ノードとする.

.. image:: ./algo_gif/step13.gif
   :scale: 40%
   :align: center

| EQ10->EQ8へ移動可能であり,これは直ちに確定ノードとなる.

.. image:: ./algo_gif/step14.gif
   :scale: 40%
   :align: center

| 確定ノードから移動可能な経路を探索する.
| EQ10->EQ11

.. image:: ./algo_gif/step15.gif
   :scale: 40%
   :align: center