
Computer Science Computer Science Forum 
 LinkBack  Thread Tools  Display Modes 
July 19th, 2015, 02: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. Last edited by DarkLink94; July 19th, 2015 at 02:24 PM. 
July 19th, 2015, 05: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 'byhand' solution, but not competitive with computer algorithms, even ones giving pretty basic approximations.

July 20th, 2015, 05:24 PM  #3 
Global Moderator Joined: May 2007 Posts: 6,686 Thanks: 661  
July 21st, 2015, 05:49 AM  #4 
Newbie Joined: Mar 2015 From: uk Posts: 13 Thanks: 0  
July 21st, 2015, 04:54 PM  #5 
Global Moderator Joined: May 2007 Posts: 6,686 Thanks: 661  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, 07:46 AM  #6 
Newbie Joined: Mar 2015 From: uk Posts: 13 Thanks: 0  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, 08:14 AM  #7 
Newbie Joined: Mar 2015 From: uk Posts: 13 Thanks: 0  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


Tags 
algorithm, approximation, approxmation, polynomial, tsp 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Polynomial Approximation  Blitz94  Abstract Algebra  1  April 23rd, 2013 03:00 PM 
Rational approximation algorithm  implicit  Elementary Math  1  October 12th, 2011 07:31 PM 
Division Algorithm and degree of a polynomial  hcir614  Number Theory  4  September 22nd, 2011 12:15 PM 
Divide polynomial without using polynomial identity  condemath  Algebra  3  September 20th, 2011 09:34 PM 
Exhibition of SelfApproximation Algorithm and Program.  omegapoint  Applied Math  2  December 22nd, 2010 05:57 AM 