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