generic image
Processing...
  • Games
  • Catalog
  • Develop
  • Robux
  • Search in Players
  • Search in Games
  • Search in Catalog
  • Search in Groups
  • Search in Library
  • Log In
  • Sign Up
  • Games
  • Catalog
  • Develop
  • Robux
   
ROBLOX Forum » Game Creation and Development » Scripters
Home Search
 

Re: Traveling Salesman Problem -- Good solutions?

Previous Thread :: Next Thread 
DevVince is not online. DevVince
Joined: 08 Nov 2008
Total Posts: 9245
19 Jul 2016 02:18 AM
Ok so the most basic way of doing this would be get the nearest location to the current one then just keep going by checking every distance with all of the locations, any other ways to go about doing this with a shorter total length?


Atm I have 200 random cities spread out on a baseplate and it has to go 75238.456943815 studs to get go to each random city with the so called shortest but it isn't really as I can tell by looking at it theirs things here and there that could be changed for improvements.


Report Abuse
76km is not online. 76km
Joined: 14 Aug 2015
Total Posts: 5455
19 Jul 2016 02:20 AM
You need to measure the distance from the starting node to every other node nearby, and then take the shortest route.

It's the only known solution, and it can be super inefficient.

Brigs, Merchantmen and Galleons.
Report Abuse
DevVince is not online. DevVince
Joined: 08 Nov 2008
Total Posts: 9245
19 Jul 2016 02:25 AM
Just found this 2-opt swap thing that makes it so it'll be shorter if the lines don't intersect. :O


Report Abuse
76km is not online. 76km
Joined: 14 Aug 2015
Total Posts: 5455
19 Jul 2016 02:28 AM
you can calculate the problem, however you can get all the money from the universities if you create the algorithm for it.

Brigs, Merchantmen and Galleons.
Report Abuse
DevVince is not online. DevVince
Joined: 08 Nov 2008
Total Posts: 9245
19 Jul 2016 02:30 AM
What? Money for what? I want some money.


Report Abuse
DevVince is not online. DevVince
Joined: 08 Nov 2008
Total Posts: 9245
19 Jul 2016 02:34 AM
Oh yea.. I see that... wew i'd like some of that. xD
Not sure if i'm that good at math though. :O


Report Abuse
DevVince is not online. DevVince
Joined: 08 Nov 2008
Total Posts: 9245
19 Jul 2016 02:42 AM
Well...
If someone figures it out everything encrypted will be no more...

This is some crazy stuff..

I'll be spending a lot of time messing with this. xD


Report Abuse
DevVince is not online. DevVince
Joined: 08 Nov 2008
Total Posts: 9245
19 Jul 2016 02:50 AM
I feel if I do somehow solve it some guys in black suvs will arrive at my house and i'll never be seen again. >_>


Report Abuse
76km is not online. 76km
Joined: 14 Aug 2015
Total Posts: 5455
19 Jul 2016 05:03 AM
calculate distance between nodes and take the shortest route.

Brigs, Merchantmen and Galleons.
Report Abuse
DevVince is not online. DevVince
Joined: 08 Nov 2008
Total Posts: 9245
19 Jul 2016 03:20 PM
Yea I'm doing that.

local distance = math.sqrt((lc.X - qp.X)^2 + (lc.Y - qp.Y)^2 + (lc.Z - qp.Z)^2)

But i'm now working on getting it so it'll move every line that intersects with the 2-opt algorithm I got to figure out how it works 100% first though then it'll reduce the path by a large distance.


Report Abuse
warspyking is not online. warspyking
Joined: 15 Nov 2011
Total Posts: 13947
19 Jul 2016 03:34 PM
en.wikipedia.org/wiki/Travelling_salesman_problem#Constructive_heuristics
Report Abuse
Previous Thread :: Next Thread 
Page 1 of 1
 
 
ROBLOX Forum » Game Creation and Development » Scripters
   
 
   
  • About Us
  • Jobs
  • Blog
  • Parents
  • Help
  • Terms
  • Privacy

©2017 Roblox Corporation. Roblox, the Roblox logo, Robux, Bloxy, and Powering Imagination are among our registered and unregistered trademarks in the U.S. and other countries.



Progress
Starting Roblox...
Connecting to Players...
R R

Roblox is now loading. Get ready to play!

R R

You're moments away from getting into the game!

Click here for help

Check Remember my choice and click Launch Application in the dialog box above to join games faster in the future!

Gameplay sponsored by:
Loading 0% - Starting game...
Get more with Builders Club! Join Builders Club
Choose Your Avatar
I have an account
generic image