Algorithms For Dummies

  Considering Heuristics 

     381

You use the BFS algorithm principally in web crawlers that look for certain infor-

mation  on  the  web.  In  fact,  BFS  allows  a  software  agent  to  move  in  a  mostly 

unknown  graph,  using  heuristics  to  detect  how  closely  the  content  of  the  next 

page resembles the initial one (to explore for better content). The algorithm is also 

widely used in video games, helping characters controlled by the computer move 

in search of enemies and bounties, thereby resembling a greedy, target-oriented 

behavior.

Demonstrating BFS in Python using the previously built maze illustrates how a 

robot can move in a space by seeing it as a graph. The following code shows some 

general functions, which are also used for the next algorithm in this section. These 

two functions provide the directions to take from a vertex (

node_neighbors

) and 

determines the cost of going from one vertex to another (

graph_weight

). Weight 

represents distance or time.

def graph_weight(graph, a, b):

    return graph.edge[a][b]['weight']

def node_neighbors(graph, node):

    return graph.edge[node]

The  path-planning  algorithm  simulates  robot  movement  in  a  graph.  When  it 

found a solution, the plan translates into movement. Therefore, path-planning 

algorithms  provide  an output  telling  you how to best  move from  one vertex to 

another, you still need a function to translate the information and determine the 

route  to  take  and  calculate  trip  length.  The  functions 

reconstruct_path

 and  

compute_path

 provide the plan in terms of steps and expected cost when provided 

with the result from the path-planning algorithm.

def reconstruct_path(connections, start, goal):

    if goal in connections:

        current = goal

        path = [current]

        while current != start:

            current = connections[current]

            path.append(current)

        return path[::-1]

def compute_path_dist(path, graph):

    if path:

        run = 0

        for step in range(len(path)-1):

            A = path[step]

            B = path[step

+1]

---

382