Algorithms For Dummies

 

   

  PART 5 

 Challenging Difficult Problems

In the maze generated by a seed value of 2, every vertex connects with the others. 

Because the generation process is random, some maps may contain disconnected 

vertexes, which precludes going between the disconnected vertexes. To see how 

this works, try a seed value of 13. This actually happens in reality; for example, 

sometimes a robot can’t reach a particular destination.

Looking for a quick best-first route

The depth-first search algorithm explores the graph by moving from vertex to 

vertex and adding directions to a stack data structure. When it’s time to move, the 

algorithm moves to the first direction found on the stack. It’s like moving through 

a maze of rooms by taking the first exit you see. Most probably, you arrive at a 

dead end, which isn’t your destination. You then retrace your steps to the previ-

ously visited rooms to see whether you encounter another exit, but it takes a long 

time when you’re far from your target.

Heuristics  can  greatly  help  with  the  repetition  created  by  a  depth-first  search 

strategy. Using heuristics can tell you whether you’re getting nearer or farther 

from your target. This combination is called the best-first search algorithm (BFS). 

In this case, the best in the name hints at the fact that, as you explore the graph, 

you don’t take the first edge in sight, but rather evaluate which edge to take and 

choose the one that, based on the heuristic, should take you closer to your desired 

outcome. This behavior resembles greedy optimization (the best first), and some 

people also call this algorithm greedy best-first search. BFS will probably miss the 

target at first, but because of heuristics, it won’t end up far from target and will 

retrace less than it would if using depth-first search alone.

FIGURE 20-2: 

A maze 

 representing a 

topological map 

with obstacles.

---

CHAPTER 20