tsp-solver

Travelling Salesman Problem Solver

TSP solver finds optimal route using Backtracking and Branch & Bound design methods.

Specifications

Matrix reduction is used as the bounding function.
Graph is undirected with positive edges only.
Nodes will be expanded in the given input order.

Input format

First line indicates design technique: {1: backtracking, 2: branch & bound}
Second line: {#nodes #edges}
Rest of input define edges of the graph: {node_id node_id edge_weight}
Example input is available in test directory.

Output format

First line indicates minimum cost of the route.
Rest of output define edges in the optimum route.

How to run

Normal usage

make
./tsp-solver < test/input > test/output

Debug mode

make debug
./tsp-solver < test/input > test/output

Memory leak check (needs valgrind)

make leakcheck