در رفتار احتمالی الگوریتم اکتشافی برای تورهای حداکثر همیلتون

A heuristic algorithm for computing the longest Hamiltonian tour through a set of points in the plane is given in [S.P. Fekete, H. Meijer, A. Rohe, W. Tietze, Solving a “hard” problem to approximate and “easy” one: Good and fast heuristics for large geometric maximum matching and maximum traveling salesman problems, Journal of Experimental Algorithms 7 (2002), article 11]. Asymptotically the value of the heuristic solution is guaranteed to be within a factor of 3/2 of the optimal solution. It was shown experimentally that the algorithm does often find solutions that are much closer to the optimal answers. In this paper we will show that in practice the heuristic algorithm is better than the 3/2 bound suggests. We will prove that the heuristic algorithm is ε-optimal with a probability that approaches 1 as the input becomes a larger and larger set of points drawn from a balanced distribution.