Menu
I'm teaching myself how to program algorithms involving TSPs (Djikstra, Kruskal) and I'm looking for some start up advice. I am working with C# and SQL. Ideally I'd like to be able to do this strictly in SQL however I'm not sure if that is possible (I assume the runtime would be awful after 50 vertices).
So I guess the question is, can I do this is only SQL and if so what is the best approach? If not, and I have to get C# involved what would be the best approach there?
913
The traveling salesman problem is easy to state, and — in theory at least — it can be easily solved by checking every round-trip route to find the shortest one.
The traveling nalesman problem (TSP) is to find a tour of minimal cost. The TSP can be modeled as a graph problem by considering a complete graph G = /V, E), and assigning each edge uu E E the cost o., A tour is then a circuit in G that meets every node. In this context, tours are sometimes called Eamiltonian c~rcuits.
In fact, TSP belongs to the class of combinatorial optimization problems known as NP-complete. This means that TSP is classified as NP-hard because it has no “quick” solution and the complexity of calculating the best route will increase when you add more destinations to the problem.
It is only advisable to do simple calculations in SQL, like calculating sums. Sums are faster in SQL, because only sums are returned instead of all the records. Complicated algorithms like the ones you have in mind must be done in your c# code! First, the SQL language is not suited for such problems, second it is optimized for db accesses, making it very slow for other types of uses.
Read your data from your db with SQL into an appropriate data structure into your c# program. Do all the TSP related logic there and, if you want, store the result in the db, when finished.
160
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
