Fast, efficient and accurate solutions to the Hamiltonian path problem using neural approaches

Unlike its cousin, the Euclidean Traveling Salesman Problem (TSP), to the best of our knowledge, there has been no documented all-neural solution to the Euclidean Hamiltonian Path Problem (HPP). The reason for this is the fact that the heuristics which map the cities onto the neurons “lose their credibility” because the underlying cyclic property of the order of the neurons used in the TSP is lost in the HPP. In this paper we present three neural solutions to the HPP. The first of these, GSOM_HPP, is a generalization of Kohonenʹs self-organizing map (SOM) as modified by Angéniol et al. (Neural Networks 1988;1:289–93). The second and third methods use the recently-introduced self-organizing neural network, the Kohonen Network Incorporating Explicit Statistics (KNIES) (Oommen et al., Proceedings of WIRN/VIETRI-98, the Tenth Italian Workshop on Neural Nets, Vietri Sul Mare, Italy, May 1998. p. 273–282). The primary difference between KNIES and Kohonenʹs SOM is the fact that unlike SOM, every iteration in the training phase includes two distinct modules – the attracting module and the dispersing module. As a result of SOM and the dispersing module introduced in KNIES the neurons individually find their places both statistically and topologically, and also collectively maintain their mean to be the mean of the data points which they represent. The new philosophy, which has previously (Oommen et al. Proceedings of WIRN/VIETRI-98, the Tenth Italian Workshop on Neural Nets, Vietri Sul Mare, Italy, May 1998. p. 273–282) been used to effectively solve the Euclidean Traveling Salesman Problem (TSP), is now extended to solve the Euclidean Hamiltonian Path (HPP). These algorithms which are the first all-neural solutions to the HPP, have also been rigorously tested. Experimental results for problems obtained by modifying selected instances from the traveling salesman problem library (TSPLIB) (Reinett. ORSA Journal on Computing 1991;3:376–84) for the HPP indicate that they are both accurate and efficient. Apart from the computational results presented, the paper also contains a systematic strategy by which the quality of any HPP algorithm can be quantified.