C++ Code: Travelling Salesman Problem (TSP) using Dynamic Programming and Bit

[PrasanBora]

@Kavya-24
I would like to contribute a solution for the Travelling Salesman Problem (TSP) using dynamic programming with bitmasking. This algorithm finds the minimum Hamiltonian Cycle by determining the shortest route that visits all cities exactly once and returns to the origin city. The solution is implemented in both C++ and Java, using recursion with memoization to optimize performance.

Could you please assign this task to me under Hacktoberfest 2024? I'm looking forward to contributing!

C++ Code: Travelling Salesman Problem (TSP) using Dynamic Programming and Bitmasking

#include <iostream>
#include <vector>
#include <limits.h>

using namespace std;

int n;
vector<vector<int>> dist;
vector<vector<int>> dp;

int tsp(int mask, int pos) {
    if (mask == (1 << n) - 1) {
        return dist[pos][0]; // Return to the start city
    }

    if (dp[mask][pos] != -1) {
        return dp[mask][pos];
    }

    int ans = INT_MAX;

    // Visit every city that hasn't been visited
    for (int city = 0; city < n; city++) {
        if ((mask & (1 << city)) == 0) {
            int newAns = dist[pos][city] + tsp(mask | (1 << city), city);
            ans = min(ans, newAns);
        }
    }

    return dp[mask][pos] = ans;
}

int main() {
    cout << "Enter the number of cities: ";
    cin >> n;

    dist = vector<vector<int>>(n, vector<int>(n));
    dp = vector<vector<int>>(1 << n, vector<int>(n, -1));

    cout << "Enter the distance matrix:\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dist[i][j];
        }
    }

    cout << "The minimum cost of the Hamiltonian Cycle is: " << tsp(1, 0) << endl;
    return 0;
}

Java Code: Travelling Salesman Problem (TSP) using Dynamic Programming and Bitmasking

import java.util.Scanner;
public class TSP {
    static int n;
    static int[][] dist;
    static int[][] dp;

    static int tsp(int mask, int pos) {
        if (mask == (1 << n) - 1) {
            return dist[pos][0]; // Return to the start city
        }

        if (dp[mask][pos] != -1) {
            return dp[mask][pos];
        }

        int ans = Integer.MAX_VALUE;

        // Visit every city that hasn't been visited
        for (int city = 0; city < n; city++) {
            if ((mask & (1 << city)) == 0) {
                int newAns = dist[pos][city] + tsp(mask | (1 << city), city);
                ans = Math.min(ans, newAns);
            }
        }

        return dp[mask][pos] = ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Enter the number of cities: ");
        n = sc.nextInt();

        dist = new int[n][n];
        dp = new int[1 << n][n];

        System.out.println("Enter the distance matrix:");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                dist[i][j] = sc.nextInt();
            }
        }

        for (int i = 0; i < (1 << n); i++) {
            for (int j = 0; j < n; j++) {
                dp[i][j] = -1;
            }
        }

        System.out.println("The minimum cost of the Hamiltonian Cycle is: " + tsp(1, 0));
    }
}

Summary of the change: This implementation adds a solution to the Travelling Salesman Problem (TSP) using a dynamic programming approach with bitmasking. The algorithm efficiently solves the problem by minimizing the cost of visiting every city exactly once and returning to the origin city, also known as finding the minimum Hamiltonian Cycle.

Dependencies:
No external dependencies are required for this change.

Type of change:
New feature (non-breaking change which adds functionality)

Checklist:

• My code follows the style guidelines of this project.
• I have performed a self-review of my own code.
• I have commented my code, particularly in hard-to-understand areas.
• I have made corresponding changes to the documentation.
• My changes generate no new warnings.
• I have added tests that prove my fix is effective or that my feature works.
• New and existing unit tests pass locally with my changes.
• Necessary documentation changes done.
• I have added the file in the correct directory.