『ACM

admin管理员组

文章数量:1794759

『ACM

写在前面：我们主要还是分享算法的模板，而不是去刨析算法的原理！

什么是哈密尔顿路径

哈密顿图（哈密尔顿图）（英语：Hamiltonian graph，或Traceable graph）是一个无向图，由天文学家哈密顿提出，由指定的起点前往指定的终点，途中经过所有其他节点且只经过一次。在图论中是指含有哈密顿回路的图，闭合的哈密顿路径称作哈密顿回路（Hamiltonian cycle），含有图中所有顶点的路径称作哈密顿路径（Hamiltonian path）。

天文学家哈密顿(William Rowan Hamilton) 提出，在一个有多个城市的地图网络中，寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。 这个问题和著名的七桥问题的不同之处在于，过桥只需要确定起点，而不用确定终点。哈密顿问题寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。

实现： // 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]; }

本文标签： ACM