Робота присвячена побудові найкоротшого шляху між двома точками на поверхні політопу. Зокрема, розглядаються 2 способи покращення відомого алгоритму Чена [1]. Експерименти на багатьох практичних прикладах показали, що 99% вікон, які створює алгоритм Чена не використовуються при побудові мінімального шляху. В роботі запропоновано фільтрацію непридатних вікон та підтримку пріоритетної черги для покращення продуктивності алгоритму.
The paper is devoted to constructing the shortest path between two pointson the on a polyhedral surface of the polytope. In particular, we propose two techniques to improve the known Chen"s algorithm [1]. Experiments on many practical examples showed that 99 % of the windows, which creates Chen"s algorithm are no use to define a shortest path. In the paper we propose filtering of useless windows and support priority queues to improve performance of the algorithm.
