最短路問題

今日は、SDPAの論文について、レフリーから教えてもらった、数値実験の方法に関する論文に目を通した。

Designing and Reporting on Computational Experiments with Heuristic Methods
Journal of Heuristics, 1:9-32, 1995

特に重要なのはP11(論文内では3ページめ)にある Table 1 である。これがこの論文の要点である。
抜粋しておくと、
1. Define the goals of the experiment.
2. Choose measures of performance and factors to explore.
3. Design and execute the experiment.
4. Analyze the data and draw conclusions.
5. Report the experiment's results.
あと、Table 2 も有益である。
1. Reproducibility is essential.
2. Specify all influential factors in details.
3. Be precise about timing.
4. Show how algorithm parameters are set.
5. Use statistical experimental design techniques.
6. Compare the heuristic with other methods.
7. Reduce variability of results.
8. Produce a comprehensie report of the results.

これらは、今後の改訂に活かしていこう。

あと、SNL のプログラムの一部で最短路問題がボトルネックになっているので、それを解消するための改良をスタート。
Matlab のプログラムをいろいろと書き直したところ、だいたい10倍程度の高速化になった。
これを C++ で書けば、さらに2倍から5倍程度は高速化できそうな手応えはあるが、問題はそれでもボトルネックに成りかねないところである。
多点スタート多点ゴールの最短路問題で、しかも他にも条件分岐が入っているので、おそらくダイクストラ法はあまり高速化できなそうな気がする。
最短路問題のアルゴリズムはバラエティに富んでいるので、どのアルゴリズムなら効率的かを考えるところから始めたほうがよさそうである。

今日の作業内容：
6:45-7:15 [ok] SNL 論文復習
13:20-14:00 [ng] 事務処理いろいろ
14:00-14:20 [ok] 事務処理続き
14:20-14:50 [ok] データ整理
17:00-18:00 [ok] Matlab プログラム改良
18:00-18:30 [ok] 改良つづき
今日のランチ：つかさ　生サーモン照り焼き
明日の予測作業時間：4h