New Idea for solving Travelling Salesman problem:
By well-wisher
Sun, 11 Mar 2018
- 389 reads
New Idea for solving The Travelling Salesman problem:
(Note: I do not really know how to write an algorithm even in pseudocode but I hope the idea here is clear)
(Note: I do not really know how to write an algorithm even in pseudocode but I hope the idea here is clear)
On the weighted graph find a hamilton circuit
Calculate total weight of hamilton circuit found
Next find a hamilton circuit of less total weight.
If no hamilton circuit of less total weight is found then stop and display "Optimal route found".
If a hamilton circuit of less total weight is found then search for another hamilton circuit of less total weight than that.
If no hamilton circuit of less total weight is found then stop and display "Optimal route found".
If a hamilton circuit of less total weight is found then search for another hamilton circuit of less total weight than that.
etcetera
Next find a hamilton circuit of less total weight.
If no hamilton circuit of less total weight is found then stop and display "Optimal route found".
If a hamilton circuit of less total weight is found then search for another hamilton circuit of less total weight than that.
If no hamilton circuit of less total weight is found then stop and display "Optimal route found".
If a hamilton circuit of less total weight is found then search for another hamilton circuit of less total weight than that.
etcetera
You see, rather than beginning by finding all the hamilton circuits and then verifying them (as in a brute force search); I begin by just finding one hamilton circuit and then looking for one of less weight then looking for one of even less weight etcetera; the process continuing like that until a hamilton circuit of most minimal and thus optimal total weight is found.
Greedy Algorithm comparison
Also this may not work as quickly as a greedy algorithm but, because greedy algorithms always make locally optimal choices which don't always lead to the globally optimal solution, I think my idea is more effective than a greedy algorithm because it will always reach the optimal solution.
- Log in to post comments