■

経路探索を一般化するとグラフ上の問題として表現される。グラフ理論の一分野？
読んでて面白くないのであんまり調べてないけど。
昨日の続き。今のまで調べてたことの分類と整理。

• 単一始点最短路問題(single-source shortest-paths problem)
  ある特定の1ノードから他の全てのノードへの最短経路を求める問題。ダイクストラ法が有名。
• 単一目的地最短路問題(single-destination shortest-paths ploblem)
  上の逆。 探索方法もほぼ同じ。
• 単一点対最短路問題(single-pair shortest-path problem)
  任意の２点間の最短路を求める問題。探索アルゴリズムの代表例としてはSSSPと同様ダイクストラ法など。これにヒューリスティック(目的地までの予想距離)を用いて探索空間を減らしたものの代表例がA*。
• 全点対間最短路問題(all-pairs shortest-paths problem)
  興味ないんで知らない。全点対間の最短経路を求める問題。

まだ途中。明日にでも、３番目の「２点間経路探索」について細かい分類を。頭の中でごちゃごちゃになってるのでこの機会に整理しとこう。