まずはそれぞれの説明から。
● A*
探索の方向に傾斜を付けて、探索範囲を狭める。
● Landmark
16 点ほどの Landmark を用意し、探索方向を狭める
● Triangle inequality(三角不等式)
三角不等式により、探索方向を狭める
これらの特徴をうまく合わせたのが ALT となる。結局は探索の方向に傾斜を付ける A* algorithm なのだが、Landmark & Triangle inequality との組合せることで良い bound を得る事ができるようだ。
● A*
探索の方向に傾斜を付けて、探索範囲を狭める。
● Landmark
16 点ほどの Landmark を用意し、探索方向を狭める
● Triangle inequality(三角不等式)
三角不等式により、探索方向を狭める
これらの特徴をうまく合わせたのが ALT となる。結局は探索の方向に傾斜を付ける A* algorithm なのだが、Landmark & Triangle inequality との組合せることで良い bound を得る事ができるようだ。