Skip to content

Instantly share code, notes, and snippets.

@tonicanada
Last active January 20, 2023 00:54
Show Gist options
  • Save tonicanada/5ed1b73ca1e86dd7738485e9116dd509 to your computer and use it in GitHub Desktop.
Save tonicanada/5ed1b73ca1e86dd7738485e9116dd509 to your computer and use it in GitHub Desktop.
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}.");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment