ALT: A* + Landmark + Triangle inequality その1

まずはそれぞれの説明から。

● A*
探索の方向に傾斜を付けて、探索範囲を狭める。

● Landmark
16 点ほどの Landmark を用意し、探索方向を狭める

● Triangle inequality(三角不等式)
三角不等式により、探索方向を狭める

これらの特徴をうまく合わせたのが ALT となる。結局は探索の方向に傾斜を付ける A* algorithm なのだが、Landmark & Triangle inequality との組合せることで良い bound を得る事ができるようだ。