Write down the algorithm for bidirectional search, in pseudo-code. Assume that each search will be a breadth-first search, and that the forward and backward searches takes turns expanding a node at a time . Be careful to avoid checking each node in the forward search against each node in the backward direction.

Artificial Inteligence, A Modern Approach. Stuart Russel and Peter Norvig, ch 3, p89, ex 3.10

After googling a correction, I wasn't even able to find an "official" algorithm version. I'm not sure if my bidirectional search pseudo-code version respects the very last condition given by Russel. Could you help me improving my pseudo-code ?

For both start and goal nodes

boolean founded = false
While founded = false
    if pulse == distance_n
            pulse ++
            founded = true
        end if
    end if
end while

When one of the algorithm find a node the orhter algorithm has already visited we have found a solution.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.