FAST HEURISTIC ALGORITHM OF SEARCHING HAMILTONIAN PATH IN GRAPH

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F00216305%3A26110%2F17%3APU124083" target="_blank" >RIV/00216305:26110/17:PU124083 - isvavai.cz</a>

Výsledek na webu

<a href="http://dx.doi.org/10.5593/sgem2017/21/S08.113" target="_blank" >http://dx.doi.org/10.5593/sgem2017/21/S08.113</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.5593/sgem2017/21/S08.113" target="_blank" >10.5593/sgem2017/21/S08.113</a>

Jazyk výsledku

angličtina

Název v původním jazyce

FAST HEURISTIC ALGORITHM OF SEARCHING HAMILTONIAN PATH IN GRAPH

Popis výsledku v původním jazyce

TThis 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

Název v anglickém jazyce

FAST HEURISTIC ALGORITHM OF SEARCHING HAMILTONIAN PATH IN GRAPH

Popis výsledku anglicky

TThis 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

Druh

D - Stať ve sborníku

CEP obor

—

OECD FORD obor

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Projekt

—

Návaznosti

S - Specificky vyzkum na vysokych skolach

Rok uplatnění

2017

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

Informatics

ISBN

978-619-7408-01-0

ISSN

1314-2704

e-ISSN

—

Počet stran výsledku

8

Strana od-do

895-902

Název nakladatele

STEF92

Místo vydání

Sofia, Bulharsko

Místo konání akce

Albena

Datum konání akce

27. 6. 2017

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—