Eliminating System- An idea for reducing the complexity of an NP-complete problem.
By well-wisher
- 261 reads
Below is an idea for a system for reducing the number of hamilton circuits that a computer would have to weigh when searching for the circuit with optimal total weight:
Step 1: On a weighted graph find all the hamilton circuits.
Each time you find a hamilton circuit calculate the weight of only one of its edges.
Step 2: When you have found all the hamilton circuits and calculated the weight of one edge out of each circuit stop.
Step 3: Now, calculate the total weight of only those hamilton circuits whose single edge weight could not exclude them from being a circuit of optimal total weight.
When you have found the hamilton circuit out of that set with the lowest total weight stop and display your result.
In other words, this system does what a detective does, narrowing down its list of possible suspects by eliminating all options that can't be the right answer.
- Log in to post comments