什么是哈密顿路径问题?

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