Implementation of approximate algorithms for solving and approximating the TSP problem.
Categories of algorithms which are implemented:
Christofides (provides a 3/2-approximation of TSP)
Greedy
Simulated Annealing (SA)
Threshold Accepting (TA)
Asadpour Asymmetric Traveling Salesman Algorithm
The Travelling Salesman Problem tries to find, given the weight (distance) between all points where a salesman has to visit, the route so that:
The total distance (cost) which the salesman travels is minimized.
The salesman returns to the starting point.
Note that for a complete graph, the salesman visits each point once.
The function :None:None:`travelling_salesman_problem` allows for incomplete graphs by finding all-pairs shortest paths, effectively converting the problem to a complete graph problem. It calls one of the approximate methods on that problem and then converts the result back to the original graph using the previously found shortest paths.
TSP is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.
http://en.wikipedia.org/wiki/Travelling_salesman_problem
Implementation of approximate algorithms for solving and approximating the TSP problem.
Categories of algorithms which are implemented:
Christofides (provides a 3/2-approximation of TSP)
Greedy
Simulated Annealing (SA)
Threshold Accepting (TA)
Asadpour Asymmetric Traveling Salesman Algorithm
The Travelling Salesman Problem tries to find, given the weight (distance) between all points where a salesman has to visit, the route so that:
The total distance (cost) which the salesman travels is minimized.
The salesman returns to the starting point.
Note that for a complete graph, the salesman visits each point once.
The function :None:None:`travelling_salesman_problem` allows for incomplete graphs by finding all-pairs shortest paths, effectively converting the problem to a complete graph problem. It calls one of the approximate methods on that problem and then converts the result back to the original graph using the previously found shortest paths.
TSP is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.
http://en.wikipedia.org/wiki/Travelling_salesman_problem
Hover to see nodes names; edges to Self not shown, Caped at 50 nodes.
Using a canvas is more power efficient and can get hundred of nodes ; but does not allow hyperlinks; , arrows or text (beyond on hover)
SVG is more flexible but power hungry; and does not scale well to 50 + nodes.
All aboves nodes referred to, (or are referred from) current nodes; Edges from Self to other have been omitted (or all nodes would be connected to the central node "self" which is not useful). Nodes are colored by the library they belong to, and scaled with the number of references pointing them
