bidirectional Search.

Bidirectional search is great in a sense that it can save a lot of memory.

b^d/2 + b^d/2 is way smaller than b^d

Stopping Condition os Bidirectional Search

However, the problem is that it’s hard to decide when to stop.

A lot of people would say “Isn’t it obvious? why can’t we stop when there’s a common element in the explored set?”

Actually, that’s not true. If you terminate there, there’s chance that your path might not be the lowest cost. You can see the counter example below.

graph TD; Start–>B: 2; B–>Goal: 2; Start–>Goal : 3;

Two Questions.

There can be two questions at this point.

1. Can I at leaast stop ‘expanding’ nodes when there’s a common element in the explored set?
2. Where should I look more if 1 is true and I can stop expanding?

The answer to the 1 is : yes, you can stop exploring.

1. only frontier.

Bidirectional A* Search

Now the stopping condition that we discussed is not the best. We need a better stopping condition

---