Traveling Santa Contest
Does anyone have any experience with using OpenCV's AI capabilities to solve the Traveling Salesman Problem?
There is a Kaggle contest called Traveling Santa 2018 - Prime Paths (https://www.kaggle.com/c/traveling-sa...), and I'm going to enter into it.
I have an algorithm that should work, and once I finish the code, I'll put it into the public domain. That way anyone can use the code to enter into the contest. I'm not in it for the money. But again, does anyone have any experience using OpenCV's AI to solve the Traveling Salesman Problem?
The following image shows the federal capitols as 10-size black points, provincial capitols as 5-size black points, and the municipal capitals as 2-size black points.
The 1-size multicoloured points are the remaining cities, broken down by country.
I am having trouble with my code. I am not certain that line 137 is correct (https://github.com/sjhalayka/hamilton...). Same with line 238 (https://github.com/sjhalayka/hamilton...). Can anyone help? Once I have this final step done, I will be able to make a normalized database that I can use to recursively find a solution to the TSP, with GA perhaps. Oh well, if I can't figure it out, I'll just do with countries and provinces alone, and just completely remove the municipality code.
If you mean DNN (deep learning) module - it supports only inference, so you'll still need to train your networks in other frameworks.
is Travel salesman an image processing problem?
@LBerger maybe it's a good opportunity, to explain the simulatedAnnealingSolver here ?
Simulated annealing is an optimization method. and the question is about AI (deep learning?) capabilities.
Simulated annealing I have got experience but what is the question?
What's the shortest path through all ~200,000 cities, stopping only once in each city (ie. what's the shortest Hamiltonian cycle)?
@sjhalayka what is your question ? I know problem
@sjhalayka -- and yea -- what's your current approach to it ?
(and maybe, "AI" is simply the wrong word here..)
I’ve tried several home-rolled algorithms, all which fail for a large number of cities. The next algorithm that I’ll try consists of breaking up the cities into countries, provinces, and counties. Then it’s a matter of stringing the countries together via the provinces, the provinces together via the counties, and the counties via the cities. If I make the countries 25 large, the provinces 25 large, and the counties 25 large, there’s roughly 13 cities per county, so the string finding will be working on super short bits of string, which makes the problem solvable in a ‘short’ period of time.
I’ve also run into a genetic algorithm (GA) solver for a small number of cities. Does OpenCV have any GA capabilities?
straight "NO".
the "spacial subdivision" idea was already handled here and imho, "simulated annealing" is quite close to the "greedy idea here (random downhill solving)
and alas -- they would not even let me download their data w/o exposing my telephone number (NO WAY!) so i'm out there ...
(kaggle was much more fun, half a decade ago ...)
@berak -- https://motls.blogspot.com/2014/08/ka... :)
@sjhalayka your algorithm is Divide and conquer algorithm ?