RUS  ENG
Full version
JOURNALS // Intelligent systems. Theory and applications // Archive

Intelligent systems. Theory and applications, 2017 Volume 21, Issue 3, Pages 41–64 (Mi ista10)

This article is cited in 1 paper

Algorithms of moving of the end of chain to the given point

I. O. Berger

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: The problem of chains is investigated. Results on the existence of chains obtained from given chain by moving of the end of the chain to a given point; Bounds of the minimum of the Euclidean distance between chains obtained from each other by moving of the end to a given point; possible number of chains obtained by moving the end to a given point and differing by the minimum number of elements from a given chain; the possible number of chains that are at the minimum distance from the given and obtained by moving the end of the chain to a given point, for $ n = 2 $ and $ n = 3 $. Algorithms for moving the end of a chain to a given point are described: an exponential algorithm that sorts out all possible chains with step $\varepsilon$, a linear algorithm giving an approximate solution for Euclidean distance, and a linear algorithm giving an exact answer for the Hamming distance and approximate for the Euclidean distance.

Keywords: chain, algorithm, upper bounds, lower bounds, Euclidean distance, Hamming distance.



© Steklov Math. Inst. of RAS, 2024