4. Search: Depth-First, Hill Climbing, Beam

Search trees

Search trees represent all the possibilities to search for the quickest path without coming back to previous paths. They are particularly used for quickest paths on maps with nodes (intersections), but not exclusively. They are primarily about choices, and finding the best sequence of choices.

British Museum Algorithm = complete expansion of all paths

Depth First vs Breadth First Search Algorithms

Depth First Search Algorithm starts by going down one level from the left by convention until the goal is reached. The program goes back up to the previous node if the goal is not reached, a process called “back up” or “backtracking“.

Breadth First Search Algorithm expands the search level by level, exploring all possibilities of one level before going down.

Both Depth First and Breadth First Algorithms use enqueued lists to extend the paths to goals and discard paths that lead to points that have already been extended.

Hill Climbing Search Algorithm

The search tree is always extended towards the node that is closer to the goal.

Hill Climbing is an informed search making use of certain heuristic information.

Beam Search Algorithm

A beam search algorithm is limiting the number of nodes extended at each node. It only extends nodes that go towards the goal, according to certain heuristics.

Commands summary

En-queuing the next nodes if the goal is not reached, the algorithms process as follow:

  • Depth First: new nodes go to front of the queue
  • Breadth First: new nodes go to front of the queue
  • Hill Climbing: sort the node closest to the goal first
  • Beam: keep only a small number of nodes in the queue

Best First Search Algorithm

Chooses of all en-queued nodes to extend the one that is closest to the goal.

Continuous space

Search algorithms can be used in continuous spaces. However, Hill Climbing can encounter certain problems, such as:

  • getting blocked at a local maximum
  • the telephone pole problem: getting confused at a flat level between high rising parts of the space
  • especially in high dimensional spaces, getting fooled by a particular configuration of space borders that prevent extensions as all paths seem to lead away from the goal