Scholarly record
FAST HEURISTIC ALGORITHM OF SEARCHING HAMILTONIAN PATH IN GRAPH
Abstract
This paper describes the optimized algorithm for searching Hamiltonian path in graph. Formerly a similar algorithm was developed for the finding of the optimized path in terrain for finding of the precise positioning of Global Navigation Satellite Systems (GNSS) via Real Time Kinematics (RTK) method. The aim of this method is to achieve quality GNSS observation on all the points in question, so that the total length of the path within all these points can be minimized. There are nodes of two types in the graph: 1) geodetic points on which we are supposed to measure by GNSS methods and 2) non-geodetic (subsidiary) points. The task is made more difficult because the GNSS points are properly measurable merely under good observation conditions (number and configuration of satellites). Considering the fact, that observation conditions on GNSS points change (which is given by GNSS principle); the proposed algorithm solves optimal utilization of observation conditions on geodetic points in the context of transferring measuring devices to make the path as short as possible. The core of the algorithm is testing the selected significant combination of all nodes of graph in the matrix of distances. The resulting Hamiltonian path is not minimized but the algorithm is very fast пїЅ the time difficulty is O(2*n), where n is number of nodes in the graph. The software application is created in Borland Delphi. One of the outputs of optimized solutions is also the presentation of the proposal of the resulting path in the terrain by on-line geo-web application in internet browser. The application has a general utilization in the accurate GNSS measurements for building of control network of constructions or in geodynamics.
Publication Impact Profile
Publication details
References14
Garey, M. R. and Johnson, D. S. (1983). Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman, p. 199
Bartoněk, D.; Bureš, J.; Švábenský, O. (2017) "Optimized GNSS RTK measurement planning for effective point occupation via heuristic analysis", Engineering Computations, Vol. 34, Issue: 1,pp. 90-104, DOI: 10.1108/EC-11-2015-0352
Liu D., Hou M., Qu H., Xiong P. (2012). A New High-Efficiency Global Optimization Algorithm for Solving Traveling Salesman Problem in Recent Advances in Computer Science and Information.
Kubiak N., Stachowiak A. (2013). Framework of Optimization Methodology with Use of an Intelligent Hybrid Transport Management System Based on Hopfield Network and Travelling Salesman Problem in Distributed Computing and Artificial Intelligence.
Kizilateş G., Nuriyeva F. (2013). On the Nearest Neighbor Algorithms for the Traveling Salesman Problem in Advances in Computational Science, Engineering.
Budinich M. (1994). A Self-organising Neural Network for the Travelling Salesman Problem that is Competitive with Simulated Annealing in ICANN.
Chieng H. H., Wahid N. (2014). A Performance Comparison of Genetic Algorithm’s Mutation Operators in n-Cities Open Loop Travelling Salesman Problem in Recent Advances on Soft Computing and Data Mining.
Ming F. H.; Lung K. (2014). Hybrid evolutionary fuzzy learning scheme in the applications of traveling salesman problem. INFORMATION SCIENCES Volume: 270, Pages: 204-225.
Akandwanaho S. M.; Adewumi A. O.; Adebiyi A. A. (2014). Solving Dynamic Traveling Salesman Problem Using Dynamic Gaussian Process Regression. JOURNAL OF APPLIED MATHEMATICS. Article Number: 818529.
Hussain A. Z. (2014). The Ordered Clustered Travelling Salesman Problem: A Hybrid Genetic Algorithm. SCIENTIFIC WORLD JOURNAL. Article Number: 258207.
Rada, V. (2011) Theory of Decision Making. Lectures, Faculty of Civil Engineering, Brno University of Technology, Czech Republic.
Bartoněk D., Bureš J., Opatřilová I. (2014). Optimization of Pre-processing of Extensive Projects in Geographic Information Systems. Advanced Science Letters, 1 October 2014, vol. 20, no. 10-11, pp. 2026-2029(4), research article, DOI: 10.1166/asl.2014.5664.
Bartoněk, D.; Opatřilová, I. (2015). The Management of Global Navigation Satellite Systems Measurement via Geographic Information Systems. ADVANCED SCIENCE LETTERS, Volume: 21, Issue: 1, Pages: 57 - 61, Published: JAN 2015, DOI: 10.1166/asl.2015.5745
Bartoněk, D.; Dermeková, S. (2015) The Use of Decision Theory in the Business Geography. ADVANCED SCIENCE LETTERS Volume: 21, Issue: 1, Pages: 88-92, Published: JAN 2015, DOI: 10.1166/asl.2015.5746
View or Download full articleAccess options
SWS access login
Login as SWS Scientific CommitteeLogin as SWS Scientific PartnerLogin as SWS AuthorAuthors and approved SWS contributors will read and export their own linked papers after identity matching by SWS profile, email and SGEM GlobalID.
For librarian assistance: [email protected]
Purchase Instant Access
- Article can be downloaded after successful payment.
- Article may be used according to SWS library access terms.
- Article cannot be redistributed.
