Artificial Intelligence – Breadth-First and Depth-First-Search

Summary of week one of the MOOC Artificial intelligence at edx.

The lecture deals with artificial intelligence, which means in this context, that we want to program computers that act logically, we do not want them to act like humans and we also do not want to build an artificial brain to understand how human thinking works.

The first problems are search problems, like finding the shortest path to a point in grid. For this you can use two types of search:

  • Breadth-First-Search: You try out every point around you and if do not reach the goal, you try the points next to these points and so on. The good thing about this is, you find the shortest way, the bad is it takes very long.
  • Depth-First-Search: You go down one way until the end (for instance, you always take a left turn) and if this does not work, you try another path. The good thing about this is that you probably find the solution faster than with Breadth-First, but you may not find the best solution.

In real-world-problems you sometimes also have costs, that you have to add to the problems, for example if you want to find the shortest path between two cities by train, you probably want to use the shortest distance and not the connection with least steps (edges in the graph).

A real improvement can be made if you add heuristics to your model, like you calculate the distance to your goal. Using this you can combine the  this heuristics with Breadth-First-Search in order to find the best solution faster because you know when your search brings you further away from your goal.