Travelling Salesdrone
The classic AI problem but with a drone, not a salesman. Can you get the drone around our cities in the shortest route? Race your opponent to find the optimal route in the shortest possible time.
At the start of the game you are given a random set of points on our 100 by 100 grid map these represent the cities. Both players are given the same city locations.
A blank game before any solution has been submitted
Your home can be any one of these cities but you must visit every city and return home. The drone always flies in a straight line between the cities but must remain in the confines of the map. The winner is the person who can find the shortest path between the cities.
When the game is in play your route will be plotted onto the map. If your route is coloured yellow you are currently winning the game otherwise it will be shown in red. In the event both you and your opponent calculate the same distance, then the winner will be the person who gets to that solution first.
You cannot submit a route which is the same as your opponents current best solution, however you could make modifications to it and submit the revised solution.
A game that has had solutions submitted
The problem gets exponentially more difficult the more cities you add. Our game styles allow 10, 20 or 50 cities and you have a maximum of 20 seconds to complete the game.
Here are some suggestions of strategies to improve your bot's performance.
Only submit a solution if you know it is better than the current best solution. The goal here is to save processing time. If you submit every solution you calculate, you lose time waiting for your code to be called again. If you only submit solutions that are better than the current best, you will be able to iterate through more possible solutions in the time available.
Do not submit the same route as your opponents best solution, again you will waste time and the route will only be rejected by the server. Please note the starting at different point and going in the same order will count as the same solution eg
[0,1,2,3,4,5,6,7,8,9] is the same as [5,6,7,8,9,0,1,2,3,4] or doing the same route in reverse [9,8,7,6,5,4,3,2,1,0] etc.Pick a city and then travel to the next closest city that you haven't already visited. So for example if you have the following 10 city map:
Starting at city 'A' you can plot a reasonably good route around the cities by just going to the next closest city as shown below:
Make sure you keep track of the distance as you go around the cities to follow the rule of only submitting a route if you know it can win.
Using nearest neighbour try a different starting city as this will quite often lead to a different result which may or may not be better. So starting at city 'J' would yield the result below:
Reducing the number of times you cross over your previous path can lead to a better solution. So if you use the nearest neighbour starting at city 'A' you can see that move 'C' to 'D' crosses move 'I' to 'A'.
.png?alt=media&token=63e35610-4309-4063-9f32-9965898d5145)
If you swap these over ie 'C' to 'I' and 'D' to 'A' you will have a better solution as shown below:
Last modified 4yr ago