Решение

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

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

Может ли существовать альтернативное решение, которое намеренно отстает от жадного решения, а потом резко «набирает скорость» и обгоняет его? И как оно может обогнать, если жадное решение каждый день пере- мещается на максимально возможное расстояние?

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

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

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

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

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

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

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


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

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

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

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Решение:

  1. § 3. Исправление недостатков решения арбитражного суда. Дополнительное решение
  2. РЕШЕНИЕ
  3. РЕШЕНИЕ АЛЬТЕРНАТИВНОЕ
  4. ПРИНЯТИЕ РЕШЕНИЙ
  5. РЕШЕНИЯ КСУ
  6. Не избегайте принятия решений
  7. ПРИНЯТИЕ РЕШЕНИЙ ГРУППОВОЕ
  8. ЗАДАЧА: РЕШЕНИЕ
  9. Принять решение
  10. Управленческие решения
  11. Решение проблем
  12. КЛЮЧ К РЕШЕНИЮ ПРОБЛЕМ.
  13. Убеждения и решения
  14. Убеждения и решения
  15. НАЙДИТЕ РЕШЕНИЕ
  16. НАЧНИТЕ С ПРИНЯТИЯ РЕШЕНИЯ