Imagine for a moment that you’ve taken the root of the problem, the highest node in the tree that is in white, and expanded it’s best child, and the best child of that, and so on, four times. Here, we’ve highlighted some nodes yellow, and some nodes white. As before, the left child of the root is the most promising, then the second most left, and so on. It’s a caricature of depth first search exploring a search space for a problem. The image below should be familiar to us by now. Part of the reason that this series has been focusing on depth first search, a tree search algorithm, is because it parallelizes well. Depending on the type of heuristic search algorithm you have, you may find it trivial to paralellize, or you might find that task nearly impossible. As the name suggests, it’s where the search for solutions to the problem is performed in parallel. Parallel Depth First Searchįirst, a word on what parallel heuristic search is. This will set the stage for talking about distributed heuristic search, where we will use multiple computers to perform search quickly. That is, we will look at how to use multiple processes in the same memory space to perform search quickly. In particular, we’re going to look at how to perform heuristic search in parallel using multiple cores. If you’ve not heard the term before, wall-clock time is exactly what it sounds like: how much time goes by according to the clock on the wall. This time, we’re going to look at reducing the wall-clock time needed to solve a search problem by using parallel computing.

Even if we move heaven and earth to reduce memory consumption, heuristic search is still prohibitively expensive in terms of time. We talked about why it was important to reduce the memory consumed by a search. Previously, we looked at a technique for reducing the memory footprint of a heuristic search.

Parallels update problems