Description of the Lab

Overview of the Lab

In this Lab, we increase the difficulty once more by introducing multiple pieces of cheese in the maze.

The goal of the Lab is to program an exhaustive search of possible paths that go through all pieces of cheese, in order to find the solution to the traveling salesman problem. Then, we improve this exhaustive search using an optimization called backtracking.

Set up the environment

As always, you should start by duplicating the PyRat template file on Google Colab. For recall, you should go on the Google Colab template program, click on « File », then « Save copy in drive ». Rename it as exhaustive.ipynb, and make it accessible by link. We will refer to this link as <shared_link_to_exhaustive.ipynb>.

In this Lab, we will use the following command:

python pyrat.py --rat "<shared_link_to_exhaustive.ipynb>" -p 5 -x 15 -y 15 -d 0.5 --random_seed 1

It is now time to increase the number of pieces of cheese in the maze (-p option). Keep this number low in a first time, as the program we are going to write is quite complex.

The traveling salesman problem

Generating the meta-graph

As studied in the Episode, the traveling salesman problem requires a complete graph to work. We are going to build such a graph, that abstracts some locations in the maze (we call it the meta-graph).

You should write a function that returns a complete graph, in which vertices represent the locations of the pieces of cheese and the starting position, and of which edges are weighted by the lengths of the shortest paths connecting these vertices.

Note: You should also store these shortest paths somewhere in order to move in the maze from a vertex of the meta-graph to another one.

def build_meta_graph (maze_map, locations) :
    # Return the meta-graph and all necessary routing tables

The goal of this Lab is to write an exhaustive solution to the TSP, by filling the following code:

def tsp (graph, initial_vertex) :

    def _tsp (...) :
        # Recursive implementation of the tree exploration

    # Initial call
    return _tsp(...)

An easy way to perform an exhaustive search is to see it as an adaptation of a depth-first search algorithm. While a DFS explores the graph until each vertex is visited once and for all (which corresponds to a single branch of a complete graph), an exhaustive search wants each vertex to be visited once within each possible branch. Here is a possible implementation of a recursive depth-first search algorithm to use as a basis for your exhaustive search.

def dfs (graph, initial_vertex) :
    
    # Nonlocal list of visited vertices (nonlocal variables are basically global variables for nested functions)
    visited_vertices = []
    
    # Recursive implementation of a depth-first search
    def _dfs (current_vertex, current_length) :
        
        # Visiting a vertex
        print("Visiting", current_vertex, "at distance", current_length, "from start")
        nonlocal visited_vertices
        visited_vertices.append(current_vertex)
        
        # We stop when all vertices are visited
        if len(visited_vertices) == len(graph) :
            print("Spanning tree done, all vertices have been explored once using DFS")
            return
        
        # If there are still vertices to visit, we explore unexplored neighbors
        for neighbor in graph[current_vertex] :
            if neighbor not in visited_vertices :
                _dfs(neighbor, current_length + graph[current_vertex][neighbor])
                
        # If there are no unvisited neighbors left, the inner function will return,
        # which corresponds to coming back to the previously visited vertex
        print("Cannot progress, going back")
        
    # Initial call
    _dfs(initial_vertex, 0)

Once the result of the traveling salesman problem is obtained, write a function to transform the solution path (into the meta-graph) into a sequence of locations within the maze.

def meta_graph_route_to_route (meta_graph_route, routing_tables) :
    # Return the sequence of locations in the maze to perform a route in the meta-graph

Then, use the code you designed in previous labs to transform this list into a list of moves to apply, and get all pieces of cheese in a minimum number of moves.

Implement a backtracking strategy

At this point, you should have a program which checks all possible permutations of vertices in the meta-graph, finds the one leading to the shortest path, and then converts this permutation into moves.

Now, you should improve this by implementing a backtracking strategy, that will abort exploration of a branch if it is already longer than the current best.

It would be interesting to work on a different file now, and create a program called exhaustive_backtracking.ipynb. This would allow you to compare performance of the exhaustive search with or without this optimization.