gsampaio/Steiner-Cycle — Issue #5: Implement Local Search for the GRASP Heuristic
Author: gsampaio
Created: 2011-11-09 02:57:26+00:00
State: open

# Implement Local Search for the GRASP Heuristic

After you create an random solution we need to make an local search in order to retrive better results. To accomplish this follow thouse next steps.

1. Find the maximum weighted edge (u,v) of the solution
2. Clone the original graph
3. Remove all the node of the graph except by the ones that are in the maximum edge
4. Find the shortest path from u to v
5. Remove the maximum weighted edge from the solution
6. Add the shortest path in the place where the maximum edge was

Repeat thouse steps util the time is over or the solution value doesnt change

**BEWARE OF THE TSP GRAPH**
In case all the nodes are terminal nodes (TSP Graph) we need to remove 2 or more edge per iteration in order to make better solutions. For this we can try to use 2-OPT or 3-OPT algorithm.