Karen Shay West's Home Page

Python Project: Brute Force Variation of Depth First Search on a map of the MIT campus minimizing time outdoors

• We found the solution to an optimization problem on how to find the shortest route from one building to another on the MIT campus given you wish to constrain the amount of time you spend walking outdoors.


• Our search projects followed these rules.


• A graph consists of a set of nodes and edges where an edge connects 2 nodes.


• Each node has children if there is an edge connecting it to a node below it.


• There are directed and undirected nodes.


• Directed graphs are digraphs.


• Undirected graphs are bidirectional.


• An edge can have a weight.


• The objective function for graph theory is either minimized or maximized.


• So for this problem, we read in a map of the MIT campus and built a graph from it: start building, destination building, distance between them in meters, and distance between spent outdoors.


• Not every route was bi-directional.


• So we first created a data structure for a weighted digraph, node and edge.


• We then modeled the MIT campus as a graph.


• We then found the shortest route using Brute Force, a variation of Depth First Search algorithm, spending minimal time outside.