Detail publikace

Rychlý heuristický algoritmus pro hledání Hamiltonovské cesty v grafu

BARTONĚK, D. BUREŠ, J. PETRUCHA, J.

Originální název

FAST HEURISTIC ALGORITHM OF SEARCHING HAMILTONIAN PATH IN GRAPH

Český název

Rychlý heuristický algoritmus pro hledání Hamiltonovské cesty v grafu

Anglický název

FAST HEURISTIC ALGORITHM OF SEARCHING HAMILTONIAN PATH IN GRAPH

Typ

článek ve sborníku

Jazyk

en

Originální abstrakt

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

Český abstrakt

Tento článek popisuje optimalizovaný algoritmus pro hledání Hamiltonovské cesty v grafu. Dříve byl vyvinut podobný algoritmus pro nalezení optimalizované cesty v terénu pro zjištění přesného umístění globálních navigačních družicových systémů (GNSS) metodou RTK (Real Time Kinematics). Cílem této metody je dosažení kvalitního pozorování GNSS na všech dotyčných bodech tak, aby celková délka cesty ve všech těchto bodech byla minimalizována. V grafu existují dva typy uzlů: 1) geodetické body, na které bychom měli měřit metodami GNSS a 2) negeedické (pomocné) body. Úloha je obtížnější, protože body GNSS jsou správně měřitelné pouze za dobrých podmínek pozorování (počet a konfigurace družic). Vzhledem k tomu, že se mění podmínky pozorování v bodech GNSS (což je dáno zásadou GNSS); Navrhovaný algoritmus řeší optimální využití podmínek pozorování na geodetických bodech v souvislosti s přenosem měřicích přístrojů tak, aby cesta byla co nejkratší. Jádrem algoritmu je testování vybrané významné kombinace všech uzlů grafu v matici vzdáleností. Výsledná Hamiltonova cesta není minimalizována, ale algoritmus je velmi rychlý - obtížnost času je O (2 * n), kde n je počet uzlů v grafu. Softwarová aplikace je vytvořena v aplikaci Borland Delphi. Jedním z výstupů optimalizovaných řešení je také prezentace návrhu výsledné cesty v terénu prostřednictvím on-line geo-webových aplikací v internetovém prohlížeči. Aplikace má obecné využití v přesných měřeních GNSS pro budování řídící sítě konstrukcí nebo v geodynamice

Anglický abstrakt

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

Klíčová slova

heuristický algoritmus, Hamiltonovká cesta, optimalizace, GNSS

Vydáno

07.07.2017

Nakladatel

STEF92

Místo

Sofia, Bulharsko

ISBN

978-619-7408-01-0

Kniha

Informatics

Číslo edice

1

Strany od

895

Strany do

902

Strany počet

8

BibTex


@inproceedings{BUT137802,
  author="Dalibor {Bartoněk} and Jiří {Bureš} and Jindřich {Petrucha}",
  title="FAST HEURISTIC ALGORITHM OF SEARCHING HAMILTONIAN PATH IN GRAPH",
  annote="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",
  address="STEF92",
  booktitle="Informatics",
  chapter="137802",
  doi="10.5593/SGEM2017/21",
  howpublished="print",
  institution="STEF92",
  number="1",
  year="2017",
  month="july",
  pages="895--902",
  publisher="STEF92",
  type="conference paper"
}