Graph-Clustering Method for Construction of the Optimal Movement Trajectory under the Terrain Patrolling

Boris V. Rumiantsev, Rasul A. Kochkarov and Azret A. Kochkarov ()
Additional contact information
Boris V. Rumiantsev: Federal Research Centre “Fundamentals of Biotechnology” of the Russian Academy of Sciences, Leninsky Prospect, 33, Build. 2, 119071 Moscow, Russian Federation
Rasul A. Kochkarov: Department of Data Analysis and Machine Learning, Faculty of Information Technology and Big Data Analysis, Financial University under the Government of the Russian Federation, Leningradsky Prospekt, 49/2, 125167 Moscow, Russian Federation
Azret A. Kochkarov: Federal Research Centre “Fundamentals of Biotechnology” of the Russian Academy of Sciences, Leninsky Prospect, 33, Build. 2, 119071 Moscow, Russian Federation

Mathematics, 2023, vol. 11, issue 1, 1-13

Abstract: The method of the optimal movement trajectory construction in the terrain patrolling tasks is proposed. The method is based on the search of the Hamiltonian circuit on the graph of the terrain map and allows automatic construction of the optimal closed path for arbitrary terrain map. The distinguishing feature of the method is the use of the modified algorithm for the Hamiltonian circuit search. The algorithm can be scaled for the maps corresponding to the graphs with a large (more than 100) number of the vertices, for which the standard brute-force algorithm of the Hamiltonian circuit search requires significantly higher execution time than the proposed algorithm. It is demonstrated that the utilized algorithm possesses 17 times less constant of the time complexity growth than the standard brute-force algorithm. It allows more than one order of magnitude (from 30 to 500 vertices, i.e., approximately to the 17 times) increase of the graph vertices that is used for the Hamiltonian circuit search in the real time (0.1–100 s) regime.

Keywords: graph theory; Hamiltonian circuit; time complexity; monitoring; patrolling (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/11/1/223/pdf (application/pdf)
https://www.mdpi.com/2227-7390/11/1/223/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:11:y:2023:i:1:p:223-:d:1022582

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().