tsp_medium_article_optimal_dp_part2.cs

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{

    public static double[,] distMatrix =
      {
      {0, 13, 17, 23},
      {6, 0, 15, 11},
      {5, 12, 0, 13},
      {9, 10, 14, 0},
    };



    /// <summary>
    /// Function that flips the ith bit of a subset.
    /// Flip the 2 bit of {10011} will return {10111}.
    /// </summary>
    /// <param name="subset">Subset in decimal form, example {1110} is 14.</param>
    /// <param name="i">Index to flip.</param>
    /// <returns>Subset with ith flipped in decimal form.</returns>
    public static int FlipBit(int subset, int i)
    {
        int k = 1 << i;
        return subset ^ k;
    }


    /// <summary>
    /// Struct that represents a subset generate from previous subset, removing its kth index.
    /// Example: Subset {1110} will generate 3 "NextSubsets": {1100} k=1, {1010} k=2, {110} k=3.
    /// </summary>
    public struct NextSubset
    {
        public int k;
        public int subset;
    }


    /// <summary>
    /// Function that generate next subsets for the recurrent function.
    /// Example {1110} -> {1100}, {1010}, {110}.
    /// </summary>
    /// <param name="subset">Subset in decimal form, example {1110} is 14.</param>
    /// <returns>List of subsets.</returns>
    public static List<NextSubset> GenerateNextSubsets(int subset)
    {
        List<NextSubset> nextSubsets = new List<NextSubset>();
        string subsetBitmask = Convert.ToString(subset, 2);
        int n = subsetBitmask.Length - 1;
        for (int i = n; i >= 0; i--)
        {
            if (subsetBitmask[i] == '1')
            {
                NextSubset s = new NextSubset();
                s.k = n - i;
                s.subset = FlipBit(subset, n - i);
                nextSubsets.Add(s);
            }
        }
        return nextSubsets;
    }


    /// <summary>
    /// Recurrent function that computes the minimum cost path from the start_node
    /// to some end_node, for a given subset. Includes memo table for memoization.
    /// Example: GetMinCost(0, "1110", memo) will return the optimal tsp tour, starting
    /// and ending , touching every node once.
    /// </summary>
    /// <param name="endNode">Ending node index.</param>
    /// <param name="subset">Subset in decimal form, example {1110} is 14.</param>
    /// <param name="memo">Memoization table (n * 2^n).</param>
    /// <returns>Minimum cost from start_node to end_node, given a subset.</returns>
    public static Double GetMinCost(int endNode, int startNode, int subset, Double[,] memo)
    {
        if (memo[endNode, subset | 1 << endNode] != Double.PositiveInfinity)
        {
            return memo[endNode, subset | 1 << endNode];
        }

        if (subset == 0)
        {
            memo[endNode, subset | 1 << endNode] = distMatrix[endNode, startNode];
            return distMatrix[endNode, startNode];
        }  

        List<NextSubset> nextSubsets = GenerateNextSubsets(subset);
        Double currentMin = Double.PositiveInfinity;

        for (int i = 0; i < nextSubsets.Count; i++)
        {
            NextSubset s = nextSubsets[i];
            Double d = distMatrix[endNode, s.k] + GetMinCost(s.k, startNode, s.subset, memo);

            if (d < currentMin)
            {
                currentMin = d;
            }
        }

        memo[endNode, subset | 1 << endNode] = currentMin;

        return currentMin;
    }

    /// <summary>
    /// Function that returns the optimal TSP tour.
    /// </summary>
    /// <param name="memo">Memoization table obtained by GetMinCost function.</param>
    /// <returns>
    /// Array of node indexes that represent the optimal TSP tour. Example: 0->1->3->2->0.  
    /// </returns>
    public static int[] GetOptimalTourFromMemo(Double[,] memo, int startNode)
    {
        int n = distMatrix.GetLength(0);
        int[] tour = new int[n + 1];

        int lastIndex = startNode;
        int currentIndex =  startNode;
        int currentSubset = ((1 << n) - 1) & ~(1 << startNode);
        double currentMin = double.PositiveInfinity;

        int step= n - 1;

        while (currentSubset > 0)
        {
            for (int i = 0; i < n; i++)
            {
                double d = memo[i, currentSubset] + distMatrix[i, lastIndex];
                if (d < currentMin)
                {
                    currentMin = d;
                    currentIndex = i;
                }
            }

            tour[step] = currentIndex;
            step--;
            lastIndex = currentIndex;
            currentSubset = currentSubset  & ~(1 << lastIndex);

        }

        tour[n] = tour[0] = startNode;
        return tour;
    }



        /// <summary>
    /// Function that converts an array of integers to a string format.
    /// </summary>
    /// <param name="array">Input integers array.</param>
    /// <returns>Array in string format.</returns>
    public static string ArrayToString(int[] array)
    {
        string result = "{";
        for (int i = 0; i < array.Length; i++)
        {
            if (i < array.Length - 1)
            {
                result += array[i] + ", ";
            }
            else
            {
                result += array[i] + "}";
            }
        }
        return result;
    }


    public static void Main(string[] args)
    {
        int n = distMatrix.GetLength(0);
        Double[,] memo = new Double[n, Convert.ToInt32(Math.Pow(2, n))];

        for (int i = 0; i < memo.GetLength(0); i++)
        {
            for (int j = 0; j < memo.GetLength(1); j++)
            {
                memo[i, j] = double.PositiveInfinity;
            }
        }

        int startNode = 1;
        Double min = GetMinCost(startNode, startNode, ((1 << distMatrix.GetLength(0)) - 1) & ~(1 << startNode), memo);
        int[] tour = GetOptimalTourFromMemo(memo, startNode);
        Console.WriteLine($"The optimal TSP tour is {ArrayToString(tour)} and has a total cost of {min}.");

    }
}