Algorithms

Nearest Neighbour Heuristic Algorithm

Algorithm Steps

The Nearest Neighbour Heuristic (NNH) is a simple greedy algorithm used in optimization, mainly for solving the Travelling Salesman Problem (TSP). The algorithm follows these steps:

1. Start at any node (city).

2. Find the nearest unvisited node (the one with the smallest distance from the current node).

3. Move to that node and mark it as visited.

4. Repeat steps 2-3 until all nodes are visited.

5. Return to the starting node to complete the cycle (if required).
   

Advantages & Disadvantages

Why NNH is Not Always Optimal?

• It does not look ahead; just picks the closest city at each step.

• A better route might exist, but the algorithm misses it due to its greedy nature.

• Can be improved by backtracking or using 2-opt swaps.
  

NOTE : NNH for a Travelling salesperson problem alone forms a tour and in rest of the cases it forms a path.

Cheapest Edge Heuristic Algorithm

Algorithm Steps

The Cheapest Edge Heuristic (CEH) is another greedy algorithm used for solving the Travelling Salesman Problem (TSP). Instead of starting from a single node like Nearest Neighbour Heuristic, it builds the tour by adding the cheapest (shortest) available edge while ensuring no cycles are formed until all nodes are connected.

Steps:

1. Sort all edges in ascending order of cost.

2. Pick the cheapest available edge that:

   • Does not form a cycle (except at the last step).

   • Does not create a degree greater than 2 at any node.

3. Repeat Step 2 until all nodes are connected.

4. Connect the last two nodes to complete the tour
   

We will pick the cheapest edges one by one while following two rules:

  i)No node should have more than 2 edges (to avoid forming an invalid structure).

 ii)No cycles should be formed until the last step (to ensure all cities get included in the tour).

Explanation

• Unlike NNH, which builds a path one city at a time, CEH builds a tour edge by edge, always selecting the smallest distance available.

• The algorithm ensures that the final tour is valid by avoiding cycles until the last step.

• It's greedy but generally performs better than Nearest Neighbour in finding shorter paths.

Advantages & Disadvantages

Cheapest Insertion Heuristic (CIH)

Understanding the Algorithm

Cheapest Insertion Heuristic (CIH) is another greedy method for solving TSP (Travelling Salesman Problem). Instead of building the tour from scratch like in NNH or CEH, we:

1. Start with a small tour (usually just two cities).

2. Gradually insert the remaining cities at the cheapest possible position in the existing tour.

3. Repeat until all cities are included.
   

Step 2: Example Walkthrough

Let’s say we have 5 cities: A, B, C, D, E with the following distances:

Step 3: Building the Tour Step-by-Step

1⃣ Start with a basic tour (Pick any 2 cities, let’s say A and B).

• Initial Tour: A → B → A

2⃣ Find the city that is cheapest to insert into this tour.

• Cost of inserting C: A → C → B → A = 20 + 15 + 10 = 45

• Cost of inserting D: A → D → B → A = 25 + 35 + 10 = 70

• Cost of inserting E: A → E → B → A = 30 + 25 + 10 = 65

• ✅ C is the cheapest to insert!

• Updated Tour: A → C → B → A

3⃣ Repeat for remaining cities (D and E).

• Find best place to insert D:

  • Inserting D between A → C: A → D → C → B → A = 25 + 30 + 15 + 10 = 80

  • Inserting D between C → B: A → C → D → B → A = 20 + 30 + 35 + 10 = 95

  • ✅ Best choice: A → D → C → B → A

• Updated Tour: A → D → C → B → A

4⃣ Insert the last city (E) in the cheapest position.

• Find best place to insert E:

  • Between A → D: A → E → D → C → B → A = 30 + 15 + 30 + 15 + 10 = 100

  • Between D → C: A → D → E → C → B → A = 25 + 15 + 20 + 15 + 10 = 85

  • ✅ Best choice: A → D → E → C → B → A

Step 4: Final Tour & Cost Calculation

✅ Final Tour: A → D → E → C → B → A
✅ Total Cost: 85

Why Does This Work?

• Unlike NNH, which greedily picks the nearest neighbor, CIH chooses where to insert a city to minimize total cost.

• Unlike CEH, which picks edges, CIH gradually builds a tour while keeping costs low.

• This gives better results than NNH in most cases but is still not optimal.
  

Comparison of Heuristic Methods

2-Opt Heuristic

The 2-Opt algorithm is used to optimize a given tour by improving its structure. Instead of building a tour from scratch like NNH, CEH, or CIH, 2-Opt starts with a tour and refines it by swapping two edges to reduce the total cost.

Key Idea:

1. Start with any valid tour (e.g., from NNH, CEH, or CIH).

2. Look for two edges that, when swapped, will shorten the tour.

3. Keep swapping edges until no more improvements can be made.

This is a local search algorithm that continuously improves the solution until we reach a local optimum.

Step 2: Example Walkthrough

Let’s say we have 5 cities: A, B, C, D, E with an initial tour:

✅ Initial Tour: A → B → C → D → E → A
✅ Initial Cost Calculation:

🔴 Initial Cost:

• A → B (10)

• B → C (15)

• C → D (30)

• D → E (15)

• E → A (30)
  🔴 Total Cost = 100
  

Step 3: Performing the 2-Opt Swap

Now, we check all pairs of edges and swap if it reduces the cost.

🔍 Find two edges that, when swapped, shorten the tour.

🎯 Example Swap:

• Swap B → C and D → E

• Remove B → C (15) and D → E (15)

• Instead, connect B → D (35) and C → E (20)

🔴 New Cost Calculation:

• A → B (10)

• B → D (35) (New Edge) 🚀

• D → C (30)

• C → E (20) (New Edge) 🚀

• E → A (30)

🔴 New Total Cost = 95

🔥 Since 95 < 100, we accept the swap!

Step 4: Keep Swapping Until No More Improvement

• We keep checking all pairs of edges.

• If we find a swap that reduces the cost, we apply it.

• This continues until no more swaps can improve the tour.

✅ Final Optimized Tour: A → B → D → C → E → A
✅ Final Cost: 95 (Reduced from 100!)

Why Does 2-Opt Work?

-> Avoids unnecessary zig-zags in the tour.

-> Improves suboptimal tours (like those from NNH, CEH, CIH).

-> Simple but powerful!

Comparison with Other Heuristics

Step-by-Step Explanation

1) Identify the Current Tour
   ->Start with an initial tour (could be a greedy nearest neighbor solution or any random valid tour).

  ->Represent the tour as an ordered list of cities.

2) Find Crossing Edges in the Tour
    ->For each pair of edges (A-B) and (C-D) in the tour:
       ->Check if they are crossing (edges overlap geometrically).
       ->Mathematically, two edges (A, B) and (C, D) cross if:
            ->A and B are on opposite sides of C-D
            ->C and D are on opposite sides of A-B
    ->This can be checked using the orientation test in computational geometry.

3) Swap Crossing Edges to Reduce Cost
    ->If edges (A-B) and (C-D) cross, swap them to (A-C) and (B-D).
    ->Since A-C and B-D are shorter than A-B and C-D, this reduces the total tour length.

4) Repeat Until No More Swaps Can Improve the Tour
   ->Keep checking for new crossings and swapping edges.
   ->Stop when no crossing edges remain and further swaps don’t reduce cost.