Решение

Описанный алгоритм создает естественный вопрос: а не получится ли так, что более ранняя остановка позволит лучше синхронизироваться с возможностями выбора будущих дней? Но если над этим задуматься, начинаешь интересоваться, действительно ли это возможно.

Кажется, последний вопрос может стать основой для рассуждений, основанных на принципе «опережения» из раздела 4.1. Возможно, удастся показать, что если жадная стратегия идет впереди в любой конкретный день, никакое другое решение не сможет догнать и обогнать его в будущем.

Чтобы доказать, что этот алгоритм действительно оптимален, следует опре- делить естественный смысл, по которому выбираемые им точки «идут впереди» любого другого действительного множества точек остановки. И хотя доказатель- ство строится по той же схеме, что и доказательство из раздела 4.1, стоит отметить
интересный контраст с задачей интервального планирования: в том случае дока- зывалось, что жадный алгоритм максимизирует нужную характеристику, а сейчас мы стремимся к минимизации некоторой характеристики.

Пусть R= |.v_∩......... JГ_Д I — множество точек остановки, выбранное жадным алго-

ритмом. Действуя от противного, предположим, что существует меньшее действи- тельное множество точек остановки S= ], такое что т < к.

Чтобы прийти к противоречию, сначала покажем, что точка остановки, дости- гаемая жадным алгоритмом в каждый день j, находится дальше точки остановки, достигаемой альтернативным решением, то есть

(4.40) Для всех j = 1, 2,..., т выполняется условие X_f> > x_ч.

Доказательство. Воспользуемся индукцией по j. Случай j = 1 очевиден из определения жадного алгоритма: в первый день туристы приходят максимально возможное расстояние, прежде чем остановиться. Теперь предположим, что j > 1, а предположение истинно для всех i < j. Тогда

Это означает, что у ваших друзей имеется возможность пройти весь путь от _| до x_ч за один день; а значит, точка лr_Л, в которой они в конечном счете остановят- ся, может находиться только дальше (Обратите внимание на сходство с соот- ветствующим доказательством для задачи интервального планирования: здесь жадный алгоритм «идет впереди», потому что на каждом шаге выбор, принимаемый альтернативным решением, является одним из его действительных вариантов.) ■

В частности, из (4.40) следует, что х_⅛ < Jf_⅛. Теперь, если т < к, должно выпол- няться условие < L-il, потому что в противном случае туристам не пришлось бы останавливаться в точке x_{t> t}. Объединяя эти два неравенства, можно сделать вывод, что зг_⅜ < L- d; но это противоречит предположению о том, что S является действительным множеством точек остановки.

Соответственно, предположение m < к было ложным, и мы доказали, что жад- ный алгоритм создает действительное множество точек остановки минимального возможного размера.