The travellingsalesman from ronitrex

Problem with circles

Hello, very nice and optimal multithreaded solution for TSP problem, but there seems to be an issue regarding circles on the bigger scale of the problem. Please have a look at this.
Example snippet:

TravellingSalesman/src/Tour.cpp

Lines 107 to 121 in 6ca44a7

 bool isNotCircle = true; 

 int i = 0; 

 while (isNotCircle || (i <= matrixOrder)) { 

 i++; 

 next = getNextNode(prev, 0, tourEdgeMatrix); 

 prev = next; 

 // There is a circle! 

 if (vertVisitList[next] == true) { 

 isNotCircle = false; 

 } else { 

 vertVisitList[next] = true; 

 } 

 } 

 return true; 

 }

This code acknowledges the fact that there is a circle in the Tour but still flags it as correct route ignoring the circle whatsoever. This problem can backfire when calculating optimal path after finding lowest cost route. I've tried to scribble a small work around to ignore all the solutions that ends up in cycles and it seems like it fixed a problem. When ignoring cycles, solution regarding route and cost differs from the one that is being printed now.

I've tested your solution on the following matrix of order 17:

{{0, 14, 7, 5, 12, 7, 11, 4, 9, 8, 11, 11, 15, 2, 11, 12, 3, }
{14, 0, 11, 13, 20, 10, 11, 6, 16, 20, 17, 13, 10, 15, 6, 14, 15, }
{7, 11, 0, 5, 14, 20, 15, 8, 10, 11, 19, 10, 2, 9, 6, 20, 4, }
{5, 13, 5, 0, 19, 6, 19, 11, 3, 5, 15, 4, 19, 3, 2, 12, 11, }
{12, 20, 14, 19, 0, 2, 12, 6, 7, 6, 11, 7, 11, 8, 2, 10, 19, }
{7, 10, 20, 6, 2, 0, 4, 14, 12, 10, 2, 2, 15, 3, 18, 9, 12, }
{11, 11, 15, 19, 12, 4, 0, 13, 8, 15, 18, 6, 17, 16, 11, 8, 13, }
{4, 6, 8, 11, 6, 14, 13, 0, 11, 13, 6, 16, 20, 14, 12, 7, 18, }
{9, 16, 10, 3, 7, 12, 8, 11, 0, 14, 15, 17, 8, 12, 2, 14, 2, }
{8, 20, 11, 5, 6, 10, 15, 13, 14, 0, 17, 4, 10, 19, 11, 2, 2, }
{11, 17, 19, 15, 11, 2, 18, 6, 15, 17, 0, 15, 9, 14, 5, 12, 15, }
{11, 13, 10, 4, 7, 2, 6, 16, 17, 4, 15, 0, 13, 18, 8, 20, 11, }
{15, 10, 2, 19, 11, 15, 17, 20, 8, 10, 9, 13, 0, 2, 4, 10, 5, }
{2, 15, 9, 3, 8, 3, 16, 14, 12, 19, 14, 18, 2, 0, 5, 3, 17, }
{11, 6, 6, 2, 2, 18, 11, 12, 2, 11, 5, 8, 4, 5, 0, 5, 19, }
{12, 14, 20, 12, 10, 9, 8, 7, 14, 2, 12, 20, 10, 3, 5, 0, 17, }
{3, 15, 4, 11, 19, 12, 13, 18, 2, 2, 15, 11, 5, 17, 19, 17, 0, }}

Current code return optimal route as 63, but it looks like optimal solution is 65.

Best wishes, Ilya.

ronitrex / travellingsalesman Goto Github PK

travellingsalesman's People

Contributors

Watchers

travellingsalesman's Issues

Problem with circles

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent

	bool isNotCircle = true;
	int i = 0;
	while (isNotCircle \|\| (i <= matrixOrder)) {
	i++;
	next = getNextNode(prev, 0, tourEdgeMatrix);
	prev = next;
	// There is a circle!
	if (vertVisitList[next] == true) {
	isNotCircle = false;
	} else {
	vertVisitList[next] = true;
	}
	}
	return true;
	}