tsp_medium_article_optimal_dp_part1.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 in 0, 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 subset)
    {
        if (subset == 0)
        {
            return distMatrix[endNode, 0];
        }

        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, s.subset);

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



    public static void Main(string[] args)
    {
        Double min = GetMinCost(0, (1 << distMatrix.GetLength(0)) - 2);
        Console.WriteLine($"The optimal TSP has a cost of {min}.");
    }
}