liveBook · Manning

Depth-first search

As explained in Applied Reinforcement Learning

Depth-first search explores a graph or tree by following one branch as far as possible before backtracking, typically using a stack or recursion.

Depth-first search (DFS) follows one branch of a tree as far as it can, then backtracks to explore another. In delivery routing, each branch represents a sequence of customer stops; DFS can compare completed routes by their accumulated cost. section 7.2 section 7.5

A recursive route search follows this pattern:

  • Extend the current route with an unvisited customer and add the travel cost. section 7.2
  • When the route is complete, compare its cost with the best found so far; otherwise, keep exploring and backtrack to try another branch. section 7.2
Listing 7.6. DFS algorithm implementation.
best_route = None
best_cost = float('inf')
 
def dfs(node):
    global best_route, best_cost
 
    if len(node.route) == len(NODES): #A
        if node.cost < best_cost:     #A
            best_cost = node.cost.    #A
            best_route = node.route   #A
        return
 
    for customer in NODES:
        if customer not in node.route:
            next_cost = node.cost +
          ➥distances[(node.route[-1], customer)]  #B
            child = RouteNode(route=node.route
          ➥+ [customer], cost=next_cost) #B
            node.add_child(child) #B
            dfs(child)  #C
 
root = RouteNode(route=["Depot"], cost=0)
dfs(root)

See a recursive DFS implementation that builds customer routes and tracks the lowest-cost complete route. section 7.2

DFS uses less memory than breadth-first search, but does not guarantee the shortest path. Exhaustively exploring routes also becomes impractical as the number of customers grows. section 7.5

How Applied Reinforcement Learning covers it

How deep it goes
Explains recursive traversal, route-cost comparison, and backtracking, then notes the limits of exhaustive search as routing trees grow.
Examples
Uses delivery routes from a depot through unvisited customers, accumulating travel costs and comparing completed tours.
What you can do after
Build it from scratch by recursively enumerating delivery routes and retaining the lowest-cost complete route.
How it connects
Connects DFS with breadth-first search and Monte Carlo tree search as related tree-search methods.

Also explained in

Compare how 9 books explain depth-first search →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Applied Reinforcement Learning. The section links point to the parts of the book it draws on.