Theory

Heuristics Search

Heuristics are used in situations in which there is the requirement of a short-term solution. On facing complex situations with limited resources and time, Heuristics can help to make a quick decisions by shortcuts and approximated calculations.

Traveling Salesman Problem (TSP) using Heuristics Search

1. Initialization:
• Start at any city as the initial node.
2. Node Exploration:
• From the current city, explore neighboring cities (other cities that haven't been visited yet). These neighboring cities represent the immediate options or choices available from the current location.
3. Heuristic Evaluation:
• Evaluate each neighboring city based on a heuristic function. This function estimates the distance to travel from the current city to each neighboring city and back to the starting city. Cities with lower heuristic values (indicating shorter distances) are considered more promising options.
4. Selection of Next Node:
• Choose the neighboring city with the lowest heuristic value, indicating that it's likely to lead to a shorter overall tour.
5. Move to Next Node:
• Move to the selected neighboring city and repeat the process, exploring its neighbors, evaluating them based on the heuristic function, and selecting the next city to move to.
6. Termination:
• Continue this process until all cities have been visited once, forming a complete tour, or until no more promising paths are available.

Example :Nearest Neighbor Heuristic for TSP

• step1 , initialization is being performed


• step1 -step2 , loop