Traveler Salesman Problem

Discution and possible solutions of the Traveler Salesman Problem.

Find the shortest path that connects a set of cities, visiting each of them exactly once, ending in the same city it started from.

The problem is solved in two different ways:

• Brute Force: chek every possible path and find the shortest one $\left(O\left(\frac{(n_{cities}-1)!}{2}\right)\right)$.
• Minimum Spanning Trees: find an approximate solution using the MST and Prim's algorithm $\left(O\left(n_{nodes}\log\left(\frac{m_{edges}}{n_{nodes}}\right)\right)\right)$.

Repository Structure

• BIN
  • Main
• DAT
  • Cities
  • Edges
  • Paths
• SRC
  • Main
  • Brute Force
  • MST
• graph.py
• License
• MakeFile
• README

Setting Parameters

It's possible to sets the parameters using the Makefile.

# PARAMETERS
NCITIES = 8

# MAKEFILE CODE Continues