Greedy Hill-Climbing

Simplest heuristic local search



• Start with a given network
  • empty network
  • best tree
  • a random network
• At each iteration
  • Evaluate all possible changes
  • Apply change that leads to best improvement in score
  • Reiterate
• Stop when no modification improves score

• Each step requires evaluating approximately n new changes

Previous slide

Next slide

Back to first slide

View graphic version