杭州交通信息网梦幻西游小年卡多少钱:什么是哈密顿路径问题？
来源：百度文库 编辑：杭州交通信息网 时间：2024/04/28 05:24:25
也叫哈密顿回路:在图中找出一条包含所有结点的闭路，并且，出来起点和重点重合外，这条闭路所含结点是互不相同的 可以在多项式时间类判断一个回路是否是哈密顿回路 但目前没有算法直接解出哈密顿回路
天文学家哈密顿(William Rowan Hamilton) 提出，在一个有多个城市的地图网络中，
寻找一条从给定的起点到给定的终点沿 途恰好经过所有其他城市一次的路径。
这个问题和著名的过桥问题的不同之处在于，某些城市之间的旅行不 一定是双向的。比如A→B,但B→A是不允许的。
换一种说法，对于一个给定的网络，确定起点和终点后，如果存在一条路径，穿过这个网络，我们就说这个网络存在哈密顿路径。哈密顿路径问题在上世纪七十年代初，终于被证明是“NP完备”的。据说具有这样性质的问题，难于找到一个有效的算法。实际上对于某些顶点数不到100的网络，利用现有最好的算法和计算机也需要比较荒唐的时间（比如几百年）才能确定其是否存在一条这样的路径。