最短路の基本的な勉強

この前教えてもらったところでは、最短路問題の基本的な勉強としては、

[教科書1] Network Flows: Theory, Algorithms, and Applications
               Ravindra K. Ahuja, Thomas L. Magnanti, James B. Orlin
[教科書2] Network Optimization
              Dimitri P. Bertsekas
のあたりであり、とくに[教科書１]は2章割いてあるだけあって、基本的なことについてかなり詳しい。
また、実装としては、Andrew Goldberg の Network Optimization にある
http://www.avglab.com/andrew/soft.html
の SPLIB が基本的な実装を網羅している。
この実装は、このページにもあるように Math Prog で比較実験の論文が出ているので、これも参考になる。


とりあえず、上記の情報をベースに進めているが、いろいろと問題もある。
SPLIB は実装が古いので、かなり読みにくくなっている。
特にデータ構造のあたりを無理なマクロを使用して書いているので、このあたりがきつい。
まずは、これを C++ で書き直して、どの程度の性能が出るのかを見てみたい。

あと、これもクリティカルな状況だが、今回の最短路についてはあくまで SDP 処理の前処理であるため、正確な最短路ではなく、SDPにとって都合のいい最短路がベターである。
つまり、目的関数が厳密でないため、厳密解法がいいとも限らず、頭が痛いところである。

今日の作業内容：
10:00-10:30 [ng] parser_db.c 解読
10:30-10:50 [ok] 解読続き
14:00-14:30 [ok] 枝の重さ 確認
14:30-15:30 [ng] dikbd.c 確認
15:30-16:00 [ok] STLのヒープの確認
16:00-16:30 [ng] dikbd.c 続き
16:30-17:00 [ok] dikbd.c 続き
17:00-18:00 [ok] dikbd.c を C++ に書き直し その１
今日のランチ：四川　豚の角煮弁当
明日の予測作業時間：4h