网站建设网站徒手整形培训,贵州网站建设培训,怎么搭建自己的网站挣钱,搜索引擎的网址有哪些什么是哈密顿回路#xff1f;
哈密顿回路#xff08;Hamiltonian Cycle#xff09;是图论中的一个概念#xff0c;指的是在一个图中通过图的每个顶点恰好一次且仅一次#xff0c;并最终回到起始顶点的闭合回路。在一个哈密顿回路中#xff0c;除了起始和结束的顶点必须是…什么是哈密顿回路
哈密顿回路Hamiltonian Cycle是图论中的一个概念指的是在一个图中通过图的每个顶点恰好一次且仅一次并最终回到起始顶点的闭合回路。在一个哈密顿回路中除了起始和结束的顶点必须是同一个顶点并且这个顶点恰好出现两次之外其他每个顶点都恰好出现一次。哈密顿回路的命名来自于爱尔兰数学家威廉·罗伊兰·哈密顿。
判断是否存在哈密顿环问题是一个经典的NP完全问题这意味着目前没有已知的多项式时间算法能解决所有情况。对于一个含有 V V V个顶点和 E E E条边的图来说常见的算法时间复杂度如下 暴力搜索法尝试图中所有可能的顺序来查找哈密顿环。其时间复杂度为 O ( V ! ) O(V!) O(V!)因为需要检查每个顶点的所有排列。 回溯法在搜索过程中如果路径不满足条件则回退一步。这是一种改进的暴力法但最坏情况的时间复杂度仍然为 O ( V ! ) O(V!) O(V!)。 动态规划例如 Held-Karp 算法用于求解旅行商问题TSP该问题与哈密顿环问题紧密相关。Held-Karp算法使用动态规划其时间复杂度为 O ( V 2 2 V ) O(V^2 2^V) O(V22V)。 启发式算法如遗传算法、蒙特卡洛方法等并不保证总是能找到解决方案但在一些情况下它们可以在多项式时间内给出近似解。时间复杂度因算法和实现而异但通常比 O ( V 2 2 V ) O(V^2 2^V) O(V22V)要低。
判断给路径是否是哈密顿回路
只需要满足条件每个点经过一次并且是一个环路就行。像判断是否是给定图的拓扑排序一样按照流程走一遍就行。 优化代码
尽量不适用全局变量使用引用传参。将条件合并。
#include iostream
#include vector
#include unordered_setusing namespace std;bool isHamiltonianCycle(const vectorunordered_setint graph, const vectorint path) {if(path.front() ! path.back() || path.size() ! graph.size()) {return false;}unordered_setint visited;int lenpath.size();for(int i 0; i len - 1; i) {if(graph[path[i]].count(path[i1]) 0 || visited.count(path[i]) ! 0) {return false;}visited.insert(path[i]);}if(graph[path[len-2]].count(path.back()) ! 0)return true;else return false;
}int main() {ios_base::sync_with_stdio(false);cin.tie(nullptr);int N, M;cin N;vectorunordered_setint graph(N 1);cin M;while(M--) {int u, v;cin u v;graph[u].insert(v);graph[v].insert(u);}int K;cin K;while(K--) {int n, v;cin n;vectorint path;path.reserve(n);//无所谓这改变的是capacity与resize不一样。while(n--) {cin v;path.emplace_back(v);}if(isHamiltonianCycle(graph, path)) {cout YES\n;} else {cout NO\n;}}return 0;
}
动态规划最短哈密顿路径
最短哈密顿路径 该问题将在以后解释。
