Sha*_*and 2 algorithm graph hamiltonian-cycle
代码堵塞问题如下:
您将获得一个包含N个节点和K"禁止"边缘的完整无向图.N <= 300,K <= 15.在图中找出不使用任何K"禁止"边的哈密顿循环数.
不幸的是,这里对堆栈和整个网络的解释是非常不充分的.我可以找出HamCycles的某个'n':( n-1)!/ 2.
我可以通过动态编程做短集.
但我没有得到博洛尼亚的所有子集,如何使它成为O ^ K？我是Python的,还没有破译可用的C++.最后我确定我会花时间学习C++,然后我会解读它.但与此同时,为什么有人不能在网络上的某个地方更好地解释这一点？它们总是一半的解释.
如果你指出缺乏的解释可能会有所帮助,但无论如何我都会尝试......
基于O(2 k)的解决方案使用包含 - 排除原则.假设存在k个禁止边,则这些边有2 k个子集,包括集合本身和空集.例如,如果有3个禁带:{A,B,C},则会有2 3 = 8个子集:{},{A},{B},{C},{A,B},{A ,C},{B,C},{A,B,C}.
对于每个子集,您计算至少包含该子集中所有边的周期数.如果包含边s的循环数是f(s)而S是所有禁边的集合,那么通过包含 - 排除原则,没有任何禁边的循环数是:
sum, for each subset s of S: f(s) * (-1)^|s|
哪里| s | 是s中元素的数量.换句话说,周期与任何边的数目的总和减去周期与至少1禁止边缘的数量加上与至少2禁止边缘的数目,...
计算f(s)并非易事 - 至少我没有找到一种简单的方法.你可以在阅读之前停下来思考它.
要计算f(s),请从未与任何s节点相关的节点的排列数开始.如果有米这样的节点,有米!如你所知,排列.调用排列数c.
现在检查s中的链的边缘.如果存在任何不可能的组合,例如涉及3个边的节点或s中的子循环,则f(s)为0.
否则,对于每个链增量米 1和繁殖Ç由2米.(有米地方把链条在现有排列和2的因子是因为链可以是向前或向后).最后,F(S)是Ç /(2米).最后一个除法将置换转换为周期.