TSP

動的計画法によるTSPのプログラムをC#に移植。（そのまんまだ）
http://blog.livedoor.jp/logopt/archives/2005-06.html#20050604

public static double TSP(double[,] dis)
{
	int	n = dis.GetLength(0);
	System.Diagnostics.Debug.Assert(n ＜ 32);
	int	smax = 1＜＜n;
	double[,] f = new double[n, smax];
	for (int s=1;s＜smax;++s) for (int i=0;i＜n;++i) f[i,s] = double.PositiveInfinity;
	for (int i=0;i＜n-1;++i) f[i, 1＜＜i] = dis[n-1, i];
	for (int s=1;s＜smax;++s)
	{
		for (int i=0;i＜n;++i)
		{
			if (((1＜＜i)&s) == 0) continue;
			for (int j=0;j＜n;++j)
			{
				int	k = s | (1＜＜j);
				if (k == s) continue;
				double tmp = f[i,s] + dis[i,j];
				if (tmp ＜ f[j,k]) f[j,k] = tmp;
			}
		}
	}
	return f[n-1,smax-1];
}
static void Main(string[] args)
{
	double[,] dis = {{0,2,4,5}, {2,0,4,2}, {4,4,0,3}, {5,2,3,0}};
	Console.WriteLine(TSP(dis));
}

有向グラフに対応しているが、無向ならばもっと早くなるかもしれない。ルートも出せる方がいいだろう。実用的ではないが、考え方を学ぶのにいいだろう。（いまいち理解していないが）