论文标题
一种用于将哈密顿周期直线嵌入到给定点的点组中的启发式算法
A heuristic algorithm for straight-line embedding of a hamiltonian cycle onto a given set of points inside simple polygons
论文作者
论文摘要
本文调查了将简单的哈密顿周期嵌入带有n个顶点的问题的问题。这个问题试图嵌入直线周期（无弯曲），该周期不会与多边形的本身或侧面相交，即是平面。这个问题是一个开放问题的特殊情况，可以找到一个简单的哈密顿（S，x，t） - path（一个简单的路径，始于s，始于t，其中s，t和路径中的所有其他顶点是集合x的成员x的成员），在简单的多边形内部，它并未相交本身或多边形的侧面。本文中问题的复杂性尚未得到验证，这是一个空旷的问题。但是，解决了NP完整的类似问题。提出了一种具有O（R（N2M + N3））时间复杂性的启发式算法和O（N2 + M）的空间复杂性来解决问题。
This paper investigated the problem of embedding a simple Hamiltonian Cycle with n vertices on n points inside a simple polygon. This problem seeks to embed a straight-line cycle (without bends), which does not intersect either itself or the sides of the polygon, i.e., it is planar. This problem is a special case of an open problem to find a simple Hamiltonian (s, X, t)-path (a simple path that starts at s and ends at t, where s, t, and all other vertices within the path are a member of set X) inside a simple polygon, which does not intersect itself or the sides of the polygon. The complexity of the problem in this paper is not verified yet, and it is an open problem. However, similar problems are resolved that are NP-Complete. A heuristic algorithm with time complexity of O(r(n2m + n3)) and space complexity of O(n2 + m) is proposed to solve the problem.
