304
правки
Изменения
→Решение альтернативной задачи
===Решение альтернативной задачи===
Решение альтернативной задачи очень схоже с исходном алгоритмом. На каждой итерации алгоритм находит подучасток исходной цепи, на котором расстояние до наиболее удаленной точки максимально, делит ее так же как и в исходном алгоритме и запоминает полученные в результате деления подучастки для следующий следующих итераций. Алгоритм стартует, когда для выбора доступна только исходная цепь.
====Реализация====
Практически очевидно, что данный вариант алгоритма легко реализовать на приоритетной очереди. Будем хранить расстояние, на котором находится наиболее удаленная вершина, как ключ, а номера вершин-границ как значение. На каждой итерации мы выбираем обьект с наибольшим ключем, делим и получившиеся части кладем обратно в очередь с новыми ключами.
