Recap

My first two projects implemented for searching via Best first and Breadth first algorithms.

New environment

Even though, depth first search CAN be easily implemented on the same grid environment, I will get much more practice by creating a new one.

Here, I make a really simple tree structure to navigate through. Here is a Node class with a recursive constructor so that you can create a tree by simply creating a root node.

import random
import names

class Node:
    node_count = 0

    def __init__(self, parent, height, depth, branching):
        Node.node_count += 1
        self.name = names.get_first_name()
        self.parent = parent
        self.height = height
        self.routes = []
        self.cost = random.randint(0, 100)
        self.is_goal = random.choices([True, False], weights=[5, 95], k=1)[0]

        # print(f'Created Node:\n{self}')
        if depth > 0:
            for i in range(0, branching):
                new_node = Node(self, height + 1, depth - 1, random.randint(0, branching))
                route = Route(new_node, random.randint(0, 100))
                self.routes.append(route)

When the note is created, we give the constructor:

• A parent so that we can navigate back to the root node
• The height, so that we can keep track of how deep we are from the root of the tree
• Depth so that we can stop creating children
• A branching factor for each note that randomlg tapers off the deeper we get

Other points to consider in this:

• So we can attribute meaning to the node and track it, we give each note a randomly generated first name
• Each node has a 5% chance of being a goal.
  • Because each goal assignment events is independent From each other, the tree may have zero goals, one goal or multiple goals.
  • When we have multiple goals, discovering the first goal should result in an early exit.

Each child mode is added to the parent’s routes. This is a list of objects that hold the node and a nominal cost. For this exercise, the cost It’s not being used, but I would like it here so that I could extend the algorithm if I have extra time.

Edit: I’ve mixed up the concepts of node height and node depth here. Depth is supposed to mean how far a node is from the root. Height is supposed to mean how far a node is from the deepest leaf node.

class Route:
    def __init__(self, node, cost):
        self.node = node
        self.cost = cost

The Algorithm

Here is the implementation of the depth first search algorithm:

def depth_first_search(starting_node):
    count = 0
    frontier = [starting_node]
    while frontier.__len__() > 0:
        count += 1
        node = frontier.pop()
        # print(f"Node {count}:")
        print(node.display_string(count))
        time.sleep(0.5)

        if node.is_goal:
            print(f'Searched through {count} of {Node.node_count} nodes.')
            return node

        for child in node.routes:
            frontier.append(child.node)
    print(f'Searched through all nodes.')
    return None

I initialise the frontier as a list containing the starting node. I treat this list as a stack. This is where items on the list are processed in a first, in last out manner.

For each iteration, I pop off the Node at the top of the stack. I then expand out all the Nodes found in the roots and add them to the top of the stack.

If we reach a goal, then we have an early return. Otherwise, just keep adding on more nodes to the frontier as we see them.

Showcase

Here is the algorithm in action:

Here’s an explanation of the output. When the nodes are created, I keep a count of how many nodes have been created and output that to the console.

Nodes created: 22

As we run the search algorithm, the nodes that are expanded are printed out. The first number is how far from the root node. To visually accentuate this, I’ve also prepended tabs according to the node depth.

 0 - Node 1 (Jerry) 
	 1 - Node 2 (Edward) 
		 2 - Node 3 (Edna) 
			 3 - Node 4 (John) 
				 4 - Node 5 (Ronald) 
		 2 - Node 6 (Rocco) 
			 3 - Node 7 (Dale) 
			 3 - Node 8 (Roy) 
				 4 - Node 9 (Kim) 
				 4 - Node 10 (Edward) 
	 1 - Node 11 (Michael) 
		 2 - Node 12 (William) 
			 3 - Node 13 (William) (Goal)

I then summarise how many nodes have been expanded compared to the total. This gives an indication of how many nodes we avoided (time/computation savings)

Searched through 13 of 22 nodes.

Finally, I print out the path to the goal from the root node.

The path to the goal is this:
Name:Jerry
Height: 0
Cost: 32
Is Goal: False

Name:Michael
Height: 1
Cost: 84
Is Goal: False

Name:William
Height: 2
Cost: 69
Is Goal: False

Name:William
Height: 3
Cost: 45
Is Goal: True

You can view the code here: Github