Skip to content

Instantly share code, notes, and snippets.

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