My Math Forum  

Go Back   My Math Forum > Science Forums > Computer Science

Computer Science Computer Science Forum


Reply
 
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.
Attached Images
File Type: jpg yeah.jpg (20.6 KB, 10 views)

Last edited by DarkLink94; July 19th, 2015 at 02:24 PM.
DarkLink94 is offline  
 
July 19th, 2015, 05:59 PM   #2
Global Moderator
 
CRGreathouse's Avatar
 
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.
CRGreathouse is offline  
July 20th, 2015, 05:24 PM   #3
Global Moderator
 
Joined: May 2007

Posts: 6,686
Thanks: 661

Quote:
Originally Posted by DarkLink94 View Post
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!!!!
mathman is offline  
July 21st, 2015, 05:49 AM   #4
Newbie
 
Joined: Mar 2015
From: uk

Posts: 13
Thanks: 0

Quote:
Originally Posted by mathman View Post
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!
DarkLink94 is offline  
July 21st, 2015, 04:54 PM   #5
Global Moderator
 
Joined: May 2007

Posts: 6,686
Thanks: 661

Quote:
Originally Posted by DarkLink94 View Post
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.
mathman is offline  
July 24th, 2015, 07:46 AM   #6
Newbie
 
Joined: Mar 2015
From: uk

Posts: 13
Thanks: 0

Quote:
Originally Posted by mathman View Post
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
DarkLink94 is offline  
July 24th, 2015, 08:14 AM   #7
Newbie
 
Joined: Mar 2015
From: uk

Posts: 13
Thanks: 0

Quote:
Originally Posted by mathman View Post
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
DarkLink94 is offline  
Reply

  My Math Forum > Science Forums > Computer Science

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 Self-Approximation Algorithm and Program. omegapoint Applied Math 2 December 22nd, 2010 05:57 AM





Copyright © 2019 My Math Forum. All rights reserved.