Heuristic for the Hamiltonian Path Problem in Euclidian Two Space
作者:
NorbackJ. P.,
LoveR. F.,
期刊:
Journal of the Operational Research Society
(Taylor Available online 1979)
卷期:
Volume 30,
issue 4
页码: 363-368
ISSN:0160-5682
年代: 1979
DOI:10.1057/jors.1979.77
出版商: Taylor&Francis
数据来源: Taylor
摘要:
AbstractThe Hamiltonian Path problem is a variant of the travelling salesman problem, in which the tour is not a closed curve. It has been demonstrated that the optimal path through all the points in some finite subset of Euclidian two space must take the vertices of each "half" of the convex hull in the order prescribed by the convex hull. This fact is used to develop two heuristics. These are tested against problems for which the optimal solution is determined by other methods. These comparisons as well as measures of computational efficiency are presented.
点击下载:
PDF (2702KB)
返 回