写在前面：我们主要还是分享算法的模板，而不是去刨析算法的原理！
什么是哈密尔顿路径
哈密顿图（哈密尔顿图）（英语：Hamiltonian graph，或Traceable graph）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径（Hamiltonian path）。
天文学家哈密顿(William Rowan Hamilton) 提出，在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。 这个问题和著名的七桥问题的不同之处在于，过桥只需要确定起点，而不用确定终点。哈密顿问题寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。
实现：
代码语言：javascript复制// hamilton路径
int f[1 << 20][20];
int hamilton(int n, int weight[20][20]) {
memset(f, 0x3f, sizeof(f));
f[1][0] = 0;
for (int i = 1; i < 1 << n; i )
for (int j = 0; j < n; j )
if (i >> j & 1)
for (int k = 0; k < n; k )
if (i >> k & 1)
f[i][j] = min(f[i][j], f[i ^ 1 << j][k] weight[k][j]);
return f[(1 << n) - 1][n - 1];
}
