|
| 17 Sep 2015 08:57 PM |
Your challenge, if you choose to accept it, is to create some code that can solve the Travelling Salesman problem.
The problem goes as such: A salesman must travel to a number of cities. He wants to know the shortest route he can take to hit all the cities at least once and end up back where he started, so he can go on the route again in the future.
Essentially, you generate many random points, and try to figure out what is the order to go through them that will take the least distance.
It must be able to solve it for at least 30 cities and the algorithm must be fast enough to solve it under 30 seconds.
Your algorithm doesn't need to find the perfect solution every time. It needs to be able to at least find the perfect solution sometimes and a very good solution every other time. It shouldn't return a bad solution.
You can do it in any programming language you wish. I have done it in Java using simulated annealing.
It should look something like this: https://www.youtube.com/watch?v=eLZvNv1bMoE |
|
|
| Report Abuse |
|
|
cntkillme
|
  |
| Joined: 07 Apr 2008 |
| Total Posts: 44956 |
|
|
| 17 Sep 2015 08:58 PM |
| This challenge sounds very familiar... like too familiar. |
|
|
| Report Abuse |
|
|
| |
|
|
| 17 Sep 2015 09:14 PM |
i remember doing this with i think the A* algorithm for pathfinding, i hated it
(This is my signature): Im extremely sarcastic, but most of the time I will provide useful info for you! :) |
|
|
| Report Abuse |
|
|
|
| 17 Sep 2015 09:23 PM |
| I am now starting, should be fun! |
|
|
| Report Abuse |
|
|
|
| 22 Sep 2015 05:35 AM |
local function PTheorem(a,b) return (a ^ 2) + (b ^ 2) end
Perhaps... You can use this to find C assuming it is triangular. |
|
|
| Report Abuse |
|
|
morash
|
  |
| Joined: 22 May 2010 |
| Total Posts: 5834 |
|
|
| 22 Sep 2015 06:21 AM |
| Pick the points with the shortest distance between them? |
|
|
| Report Abuse |
|
|
|
| 22 Sep 2015 07:27 AM |
local points = {} local cityNearby
local cityMap = Instance.new("Model", game.Workspace) cityMap.Name = "City"
local tracks = Instance.new("Model", game.Workspace) tracks.Name = "Tracks"
local start = Instance.new("Part", cityMap) start.Name = "StartCity" start.Anchored = true start.BrickColor = BrickColor.Random() start.Size = Vector3.new(2,4,2) start.CFrame = CFrame.new(Vector3.new(math.random(-200,200),-10,math.random(-200,200)))
local lastCity = start local lastMag = math.huge
for i = 1,math.random(30,40) do local city = Instance.new("Part", cityMap) city.Name = "City"..i city.Anchored = true city.BrickColor = BrickColor.Random() city.Size = Vector3.new(2,4,2) city.CFrame = CFrame.new(Vector3.new(math.random(-200,200),-10,math.random(-200,200))) table.insert(points,#points+1, {city, false}) end
for i,v in pairs(points) do local currentCity for t,q in pairs(points) do local mag = (lastCity.Position-q[1].Position).magnitude if mag < lastMag and q[2] == false then lastMag = mag currentCity = q print("Found") end end local track = Instance.new("Part", tracks) track.Name = "Track" track.BrickColor = BrickColor.new("Black") track.Size = Vector3.new(2,4,lastMag) track.CFrame = CFrame.new(lastCity.Position, currentCity[1].Position)*CFrame.new(0,0,-lastMag/2) track.Anchored = true currentCity[2] = true lastCity = currentCity[1] lastMag = math.huge wait() end
lastMag = (lastCity.Position-start.Position).magnitude local track = Instance.new("Part", tracks) track.Name = "Track" track.BrickColor = BrickColor.new("Black") track.Size = Vector3.new(2,4,lastMag) track.CFrame = CFrame.new(lastCity.Position, start.Position)*CFrame.new(0,0,-lastMag/2) track.Anchored = true
Took me roughly 30 mins, good challange so far. |
|
|
| Report Abuse |
|
|
|
| 22 Sep 2015 07:40 AM |
Edited it, made a proper animation for it.
Take it here: http://www.roblox.com/SalesMan-Challange-item?id=299447278 |
|
|
| Report Abuse |
|
|
| |
|
chimmmihc
|
  |
| Joined: 24 Jul 2014 |
| Total Posts: 2420 |
|
|
| 22 Sep 2015 04:53 PM |
You didn't account for gas into the pathfinding, this is part of the real problem
Fun fact, airports have people do this cause so far computers haven't been able too. |
|
|
| Report Abuse |
|
|
notfruit
|
  |
| Joined: 21 Sep 2012 |
| Total Posts: 1386 |
|
|
| 22 Sep 2015 06:15 PM |
bruh get ur NP-complete problems out of here
unless someone has an algorithm for solving this in polynomial time
if u do pls share
that means we can factor large integers in polynomial time
which means we can essentially break at least some kinds of encryption (symmetric-key) |
|
|
| Report Abuse |
|
|