哈密顿图NP问题pre
哈密顿回路
与欧拉回路
By 何闽强 李文海 郭煜桁
欧拉回路:图G的一个回路,若它恰通过G中每条 边一次,则称该回路为欧拉(Euler)回路。
哈密顿回路:从图中的任意一点出发,路途中经 过图中每一个结点当且仅当一次,则成为哈密顿 回路
欧拉回路问题是P问题 哈密顿回路问题是NP问题(NPC)
证明1:归约到精确覆盖问题 (exact cover) 在一个全集X中若干子集的集 合为S,精确覆盖(Exact cover) 是指,S的子集S*,满足X中的 每一个元素在S*中恰好出现一 次。[1] 在计算机科学中,精确覆盖问 题指找出这样的一种覆盖,或 证明其不存在。
哈密顿回路的应用 ——格雷码
可以使用下述方法来求得符合上述要求的格雷 码: 1、将不同的位串看做不同的顶点,比如001,010。 2、将位串只相差一位的顶点用边连接。比如000 就要和001,010,100连接。 3、在步骤1和步骤2生成的图G中寻找哈密顿回 路。
这条哈密顿回路所产生的前后恰 好相差一位的位串序列是: 000,001,011,010,110,111,101,10 0。如下图。
的c*m次方。 ——《自动机理论,语言和计算导论》
至今为止所有解答旅行商问题的算法都在本质上尝试了 所有的回路并计算了回路的总权。所以,在确认有没有 哈密顿回路之前,似乎一定要检查指数个回路个数。 ——《自动机理论,语言和计算导论》
欧拉回路的P类算法
• Fleury算法: 任取v0∈V(G),令P0=v0; • 设Pi=v0e1v1e2…ei vi已经行遍,按下面方法 从中选取ei+1: • (a)ei+1与vi相关联;
• 当前状态:起点、终点、经过的点的集 合 • –用位压缩的办法表示经过的点的集合, 则每种状态都可以用三个整数表示,不 妨记为<a, b, st>,其中st表示经过的点的 集合 • f(<a, b, st>) = min{ f(<a, k,st - 2b >) + w(k,b) },k 属于集合st.
• (b)除非无别的边可供行遍,否则ei+1不 应该为Gi=G-{e1,e2, …, ei}中的桥(所谓桥是 一条删除后使连通图不再连通的边); • (c)当(b)不能再进行时,算法停止。 • 可以证明,当算法停止时所得的简单回路 Wm=v0e1v1e2….emvm(vm=v0)为G中的一条 欧拉回路,复杂度为O(e*e)。
二分图表示
旅行商问题
• 假设有一个旅行商人要拜访m个城市,他必须选 择所要走的路径,路经的限制是每个城市只能拜 访一次,而且最后要回到原来出发的城市。路径 的选择目标是要求得的路径路程为所有路径之中 的最小值。
在有m个顶点的图中。不同的回路数以O(m!)的
速度增长,对于任何常数c。 O(m!)最终大于2
• 复杂度: • –状态数O(n^2*2^n),状态转移O(n) • –时间复杂度O(n^3*2^n),空间复杂度 O(n^2*2^n)
哈密顿回路的应用 ——格雷码
• 格雷码简介: • 格雷码是在贝尔实验室中ห้องสมุดไป่ตู้了减少数字信号传递过程中错 误的影响被发明的。
• 哈密顿回路在格雷码上的应用:
• 旋转的指针的位置可以表示成数字的形式。 • 一种方式是把圆周等分成2^n段的弧,并且用程度为n的位 串给每段弧度赋值。如下图。
•
•
哈密顿回路的应用 ——格雷码
• 当指针靠近两段弧度的边界时,在读 出指针位置时可能发生错误。这可能 引起读出的位串里有一个大的错误。 • 比如上图中如果指针,若在确定指针 的位置出错,则读出的位串是100而不 是011。所以3位都是错的。 • 为了把这样的错误的影响降到最低, 应当使相邻弧度所表示的位串只相差1 位。
应用举例:
• A城市的交通系统由若干个路口和街道 组成,每条街道都连接着两个路口。 所有街道都是双向通行的,且每条街 道都有一个长度。一个邮递员在送信, 要从邮局出发经过所有街道再返回邮 局(每条街可以重复走),他怎么样 安排可以使长度最短?
• 哈密顿回路的近似算法和应用
• 人们证明,找一条哈密顿路的近似比 为常数的近似算法也是NPC问题。 • 寻找哈密顿路的确定算法虽然很难有 多项式时间的,但是这并不意味着只 能进行时间复杂度为O(n!*n)暴力搜索。 利用状态压缩动态规划,可以将时间 复杂度降低到O(2^n*n^3)