Improving A * Algorithm

Question

Let's say I find a way in the house using the A * algorithm. Now the run time can be O (n ^ 2).

I was wondering if the performance would improve if I found out which doors to follow, and accordingly I would use A * on it, i.e. if I have a starting position S and an ending position like F , and instead of applying A * on these two endpoints, it would be better if I applied A * on

 `S` and `A1` `A1` and `A2` `A2` and F. 

Where are A1 and A2 - my intermediate (doors) to be followed for the shortest path? Would it be useful to improve the search for intermediate elements, and then follow the path, and not just apply A * directly at startup and completion.

Given that searching for intermediate elements requires linear time.

Answer 1

Yes, this will help a lot if the algorithm accepts O(n^2) behavior at runtime. Instead of one big problem, you get two smaller problems, each of which will be 1/4 more expensive to calculate.

I am sure that there are pathological cases when this does not help or even hurts, but in your scenario (home) it will probably help a lot.

I assume that you are using the fact that you need to climb the elevator or stairs to change floors. This would help A * a lot, because now the cost function should only work on one floor. It will be very representative for real value. In contrast, the cost function will greatly underestimate the distance if you want to move to one room, but one floor higher. In this case, the Euclidean distance will fail completely (and the algorithm will degrade into an exhaustive search). The first transition to the stairs, and then the transition from the stairs to the desired room will work much better.