GitHub - samaroo/TSP: A script that can find a TSP solution to a set of cartesian nodes either by Branch and Bound, or Random Insertion heuristic

samaroo / TSP Public

Notifications You must be signed in to change notification settings
Fork 0
Star 1

A script that can find a TSP solution to a set of cartesian nodes either by Branch and Bound, or Random Insertion heuristic

1 star 0 forks Branches Tags Activity

Star

Notifications

Branches Tags

Name		Name	Last commit message	Last commit date
Latest commit History 1 Commit
.vscode		.vscode
Engine		Engine
Engine.cpp		Engine.cpp
Engine.h		Engine.h
Makefile		Makefile
README.txt		README.txt
input.txt		input.txt
output.txt		output.txt
sample-ab-FASTTSP-out.txt		sample-ab-FASTTSP-out.txt
sample-ab-MST-out.txt		sample-ab-MST-out.txt
sample-ab.txt		sample-ab.txt
sample-c-FASTTSP-out.txt		sample-c-FASTTSP-out.txt
sample-c-MST-out.txt		sample-c-MST-out.txt
sample-c-OPTTSP-out.txt		sample-c-OPTTSP-out.txt
sample-c.txt		sample-c.txt
sample-d-FASTTSP-out.txt		sample-d-FASTTSP-out.txt
sample-d-MST-out.txt		sample-d-MST-out.txt
sample-d-OPTTSP-out.txt		sample-d-OPTTSP-out.txt
sample-d.txt		sample-d.txt
sample-e-FASTTSP-out.txt		sample-e-FASTTSP-out.txt
sample-e-MST-out.txt		sample-e-MST-out.txt
sample-e-OPTTSP-out.txt		sample-e-OPTTSP-out.txt
sample-e.txt		sample-e.txt
test-0-FASTTSP.txt		test-0-FASTTSP.txt
test-1-MST.txt		test-1-MST.txt
test-2-OPTTSP.txt		test-2-OPTTSP.txt
test-3-FASTTSP.txt		test-3-FASTTSP.txt
test-4-MST.txt		test-4-MST.txt
test-5-OPTTSP.txt		test-5-OPTTSP.txt
test-6-FASTTSP.txt		test-6-FASTTSP.txt
test-7-MST.txt		test-7-MST.txt
test-8-OPTTSP.txt		test-8-OPTTSP.txt
test-9-FASTTSP.txt		test-9-FASTTSP.txt

Repository files navigation

There are four input files, sample-ab.txt, sample-c.txt,
sample-d.txt, and sample-e.txt.
  sample-ab.txt has 10000 vertices, sample-c.txt and sample-d.txt
  each have 30, sample-e.txt has 11 vertices.

There are output files for sample-ab.txt run with MST and FASTTSP,
while samples c-e were run with all 3 modes.

The file sample-d.txt is the same as sample-c.txt, EXCEPT
that it has been shifted up and to the right by 50, putting all
vertices in Quadrant 1 of the graph.  If you get the same answers
when running samples c and d in MST mode, and sample c output is
wrong, it's because you forgot to account for transitioning from
one region to another.  When running OPTTSP, if you get sample d
right but sample c wrong, it's because you forgot that in FAST
and OPT, you DO NOT consider the border between regions.

The file sample-e.txt has 11 vertices selected from sample d;
the vertices were selected so that our fast and optimal solutions
give different output.  This test case should help with debugging
OPTTSP mode.