• 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.

Advantage:

• • 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