Iterative Improvement Algorithm

• IN many optimization problems, path is irrelevant, the goal state itself is solution. for example, (Travelling Shells-man Problem) TSP and N-Queens problem. In such cases, one can use Iterative improvement algorithms. It keeps single current state and try to improve it.

• For the most practical approach in which all the information needed for a solution are contained in the state description itself. The path of reaching a solution is not important.

• Iterative improvement is a technique that approaches a solution by progressive approximation, using the K th approximate solution to find the (k+1) th approximate solution.


  • • memory save by keeping track of only current state.
  • • When path is irrelevant and goal state is the solution.
  • • Then state space = a set of goal states.
  • - find one that states constraints (e.g., no two classes at same time)
    - or, and optimal one (e.g., highest possible value, least possible cost)
    -In such cases, can use iterative improvement algorithms; keep a single \Current" state,
  • try to improve it.
  • -Constant space
    -Suitable for online as well as oine search.

Example: N-Queens Problem

  • • Put n queens on an n|x n chessboard
  • • No two queens on the same row, column, or diagonal
  • • Iterative improvement:
  • • Start with one queen in each column
  • • move a queen to reduce number kof conflicts.
  • • Even for very large n (e.g., n=1 million), this usually finds solution almost instantly.

Example TSP Problem

  • • Given a complete graph (edges between all pairs on nodes)
  • • A tour is a cycle that visits every node exactly once
  • • Find a least-cost tour (simple cycle that visits each city exactly once)
  • • Iterative improvement:
  • • Start with any tour, perform pairwise exchanges.
  • • variants of this approach get within 1% of optimal very quickly with thousands of cities.

Classes of Iterative improvement algorithms

  •  Hill Climbing (gradient decent)
  •  Local Bean search
  •  Simulated Annealing
  •  genetic Algorithm

About the Author

Silan Software is one of the India's leading provider of offline & online training for Java, Python, AI (Machine Learning, Deep Learning), Data Science, Software Development & many more emerging Technologies.

We provide Academic Training || Industrial Training || Corporate Training || Internship || Java || Python || AI using Python || Data Science etc