Approximation algorithm

Up to now, the best algorithm for solving an NP-complete problem

requires exponential time in the worst case.

It is too time-consuming.

 
 

To reduce the time required for solving a problem,

we can relax the problem,

and obtain a feasible solution “close” to an optimal solution

 
 

欧几里得旅行商问题


 
 


 
 

 
 

第一步,找出最小生成树


第二步,对奇数度的点集使用最小欧几里得加权分配。

{P1,P2,P3,P4,P6,P8}点集 的每一个顶点的度都是奇数

 
 




 
 

第三步,构造欧拉回路,然后由欧拉回路得到哈密顿回路。




 
 


 

 
 

 
 




0 条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注