両側A*探索
両側A*探索のときにどういうヒューリスティクス関数を使えば解が正しいと保証されるのかということで研究室で奮闘中。
vを現在見ているノードとして
s->tで片側探索するのときのヒューリスティクス関数をhf(v) t->sで片側探索するのときのヒューリスティクス関数をhb(v)
としたときに
両側探索でs->tのときに使うべきヒューリスティクス関数pf(v) 両側探索でt->sのときに使うべきヒューリスティクス関数pb(v)
を求める。
そのとき
pf(v) = hf(v) - hb(v) pb(v) = hb(v) - hf(b) [= -pf(v)]
か
pf(v) = {hf(v) - hb(v) + hf(s)}/2
pb(v) = {hb(v) - hf(v) + hb(t)}/2とするのがよさげ。
証明は三角不等式をぶんまわせばできるくさい。
ちなみに両側探索したときにsから探索したノードとtから探索したノードが初めてぶつかったときに、そのノードが最短路だと思うと間違えで、今まで見つかっているs側のノードと、t側のノードをを直接結ぶような経路も調べないといけない。これはA*じゃなくてもいえることだけど。
