Algorithms For Dummies

 

   

  PART 5 

 Challenging Difficult Problems

            run 

+= graph_weight(graph, A, B)

        return run

    else:

        return 0

Having prepared all the basic functions, the example creates a maze using a seed 

value of 30. This maze presents two main routes going from vertex A to vertex Y 

because  there  are  some  obstacles  in  the  middle  of  the  map  (as  shown  in 

 Figure 20-3). There are also some dead ends on the way (such as vertexes E and O).

graph, coordinates = create_maze(seed=30)

start = 'A'

goal  = 'Y'

scoring=manhattan_dist

The BFS implementation is a bit more complex than the depth-first search code 

found in Chapter 9. It uses two lists: one to hold the never-visited vertexes (called 

open_list

), and another to hold the visited ones (

closed_list

). The 

open_list

 

list acts as a priority queue, one in which a priority determines the first element 

to extract. In this case, the heuristic provides the priority, thus the priority queue 

provides a direction that’s closer to the target. The Manhattan distance heuristic 

works best because of the obstacles obstructing the way to the destination:

# Best-first search

path = {}

open_list = set(graph.nodes())

FIGURE 20-3: 

An intricate maze 

to be solved by 

heuristics.

---

CHAPTER 20