My Math Forum my polynomial approximation algorithm for tsp...

 Computer Science Computer Science Forum

July 19th, 2015, 01:18 PM   #1
Newbie

Joined: Mar 2015
From: uk

Posts: 13
Thanks: 0

my polynomial approximation algorithm for tsp...

All done manually on paint atm,

how good is this as an approximation? The image on the right is the optimal solution and on the left the thick black perimeter is the result of my algorithm.
Attached Images
 yeah.jpg (20.6 KB, 10 views)

Last edited by DarkLink94; July 19th, 2015 at 01:24 PM.

 July 19th, 2015, 04:59 PM #2 Global Moderator     Joined: Nov 2006 From: UTC -5 Posts: 16,046 Thanks: 938 Math Focus: Number theory, computational mathematics, combinatorics, FOM, symbolic logic, TCS, algorithms Looks pretty bad. I mean, not bad for a 'by-hand' solution, but not competitive with computer algorithms, even ones giving pretty basic approximations.
July 20th, 2015, 04:24 PM   #3
Global Moderator

Joined: May 2007

Posts: 6,754
Thanks: 695

Quote:
 Originally Posted by DarkLink94 All done manually on paint atm, how good is this as an approximation? The image on the right is the optimal solution and on the left the thick black perimeter is the result of my algorithm.
The set of nodes doesn't look the same in these diagrams!!!!

July 21st, 2015, 04:49 AM   #4
Newbie

Joined: Mar 2015
From: uk

Posts: 13
Thanks: 0

Quote:
 Originally Posted by mathman The set of nodes doesn't look the same in these diagrams!!!!
Theres one mistake in the joining up off the nodes but the nodes are all in the same place!

July 21st, 2015, 03:54 PM   #5
Global Moderator

Joined: May 2007

Posts: 6,754
Thanks: 695

Quote:
 Originally Posted by DarkLink94 Theres one mistake in the joining up off the nodes but the nodes are all in the same place!
What do mean by "nodes are all in the same place"? I presume you are trying to connect nodes by the shortest path, but the nodes in your map are not in the same place as the solution map.

July 24th, 2015, 06:46 AM   #6
Newbie

Joined: Mar 2015
From: uk

Posts: 13
Thanks: 0

Quote:
 Originally Posted by mathman What do mean by "nodes are all in the same place"? I presume you are trying to connect nodes by the shortest path, but the nodes in your map are not in the same place as the solution map.
Both images were the same but I edited one to see how my algorithm would fare, I did not edit the node positions. I repeat the nodes in both images are in the same place

July 24th, 2015, 07:14 AM   #7
Newbie

Joined: Mar 2015
From: uk

Posts: 13
Thanks: 0

Quote:
 Originally Posted by mathman What do mean by "nodes are all in the same place"? I presume you are trying to connect nodes by the shortest path, but the nodes in your map are not in the same place as the solution map.
Both images were the same but I edited one to see how my algorithm would fare, I did not edit the node positions. I repeat the nodes in both images are in the same place

 Thread Tools Display Modes Linear Mode

 Similar Threads Thread Thread Starter Forum Replies Last Post Blitz94 Abstract Algebra 1 April 23rd, 2013 02:00 PM implicit Elementary Math 1 October 12th, 2011 06:31 PM hcir614 Number Theory 4 September 22nd, 2011 11:15 AM condemath Algebra 3 September 20th, 2011 08:34 PM omegapoint Applied Math 2 December 22nd, 2010 04:57 AM

 Contact - Home - Forums - Cryptocurrency Forum - Top