#p111737,Шарпер написал(а):А откуда алгоритм знает какие относятся к К, а какие к N?
К N относятся все пункты, которые заданы условием задачи.
Алгоритм состоит из одного этапа предварительных расчетов, и N - k этапов составления маршрута.
Предварительный этап состоит из :
1. разбиения множества пунктов N на два подмножества:
k пунктов, которые образуют выпуклый внешний периметр многоугольника,
и (N - k) свободных пунктов, которые находятся внутри периметра.
2. Составление матрицы детуров каждого пункта с каждым отрезком периметра
( всего нужно найти k*(N - k) значений).
Каждый из этапов составления маршрута заключается во включении одного из свободных пунктов в маршрут,
на каждом таком этапе количество свободных пунктов уменьшается на единицу,
а количество пунктов, составляющих маршрут увеличивается на единицу.
Каждый такой этап состоит из:
1. нахождения минимального элемента в матрице детуров,
2. исключение участка маршрута, соответствующего этому минимальному элементу,
3. добавление двух новых участков, содержащих пункт, соответствующий этому же минимальному элементу,
4. расчет детуров двух новых участков с оставшимися свободными пунктами
( всего нужно найти 2*(N - k) значений, причем на каждом этапе (N - k) становится на единицу меньше).
Вполне себе алгоритмизируемый алгоритмичный алгоритм... 
Отредактировано Лукомор (2019-09-23 10:50:09)
