最短経路の本 二周目

24 あたりから最後まで。結局あんまり細かいところまで読み込んでないんですが、とりあえず。

• 計算量クラスの話。問題を他の問題に帰着するということ。
• ハミルトン閉路と巡回セールスマン問題。TSP は NP なので最適解を見つけるのは非常に難しい。
• そこで、ヒューリスティックを用いた近似解の構成が考えられる。一般には最適解は得られないが、現実的な時間で近似解を求める。
• 得られる経路が最適とは限らないので、最短経路と比べてどれくらい長いかの評価が望まれる。得られた経路が最適解に近いということが立証できるならば、それもまたよい成果である。
• 最短経路の下限を求める方法がいくつか紹介されている。全域木とかマッチングとかを使う。