Let's say there is a salesman and he is trying to go from town to town to sell his products. He has to visit all the towns, but he is in a hurry to get back so he needs to find the route that will get him around the fastest.
If it's a simple problem with few towns, the salesman can find his own solution. In a case however like the one shown above, he would need the help of the computer.
One way a computer could solve this problem is, through Opt-Swap, by taking all the possible paths between these towns (edges connecting the points), and generating a random path. Then, taking two edges at random and if swapping them is an improvement to the total distance traveled, then it would perform the swap. It would repeat that loop until it the route could not be improved by an immediate opt-swap. This however does not mean that that resulting route is the optimal one, and there are various algorithms that attempt to control for that like simulated annealing by which the computer is told to probabilistically accept non-optimal solutions earlier on in the process.
This is a very rough overview of the traveling salesman problem but if you are interested I would highly recommend watching the two referenced videos. They go into more detail and they explain it much better.
Also, I randomly ran into this: https://www.youtube.com/watch?v=8WjUVEamGKA . Very interesting! If you have 4 minutes to spare it's definitely worth watching.
References:
- https://www.youtube.com/watch?v=SC5CX8drAtU
- https://www.youtube.com/watch?v=-cLsEHP0qt0
- http://permutationcity.10gbhost.com/projects/mutants/tspresults.gif?i=2
This reminds me of an algorithm created by a computer scientist used to solve for the shortest distance between nodes in a graph, Dijkstra's algorithm. It has wide uses in the field from basic problems like this to more complicated artificial intelligence uses.
ReplyDelete