Solve question 3 using a Bidirectional Search, using Uniform Cost Search for both trees.

The default implementation of such a bidirectional search is not optimal and tweaks need to be applied. Here we will apply a simple tweak to make the resultant algorithm optimal. At any general time, let fringe1 and fringe2 be the priority queues of the search trees rooted at the source and goal respectively. Let C1 and C2 be the cost of the best node in fringe1 and fringe2 respectively. The algorithm first expands fringe1 till a cost of C2. This updates the variables fringe1 and C1. Then the algorithm expands fringe2 till a cost of (updated) C1. This updates fringe2 and C2. The algorithm iterates over these two steps.

At every iteration, tree rooted at source is expanded till the best cost node available in the fringe of tree 2. Then the tree rooted at the goal is expanded till the cost of the best node available in the fringe of tree 1. This process continues by altering the expansion of the two trees.

The point of intersection of the two trees will be just a candidate path, and not the optimal path. Continue expanding the trees further till the minimum depth possible, after which it is guaranteed that no better solution will be obtained. Take the least cost path from all possible candidate paths. In case of a tie, and earlier generated solution is preferred.

For every test case print "a b" where the path cost of the path is given by a+b*sqrt(2)