Анализ алгоритма

Хотя этот жадный метод базируется на вполне естественном принципе, оптимальность возвращаемого множества интервалов не столь очевидна.

В самом деле, торопиться с вердиктом вообще не стоит: идеи, приведшие к описанным выше неоптимальным версиям жадного алгоритма, также на первый взгляд выглядели перспективно.

Для начала можно сразу утверждать, что интервалы множества A, возвращаемого алгоритмом, совместимы.

(4.1) Множество A состоит из совместимых заявок.

Нужно продемонстрировать, что это решение оптимально. Итак, пусть O — оптимальное множество интервалов. В идеале хотелось бы показать, что A = O, но это уже слишком: оптимальных решений может быть несколько, и в лучшем случае A совпадает с одним из них.

Итак, вместо этого мы просто покажем, что |A| = |O|, то есть A содержит столько же интервалов, сколько и O, а следовательно, является оптимальным решением.

Как упоминалось в начале главы, идея, заложенная в основу этого доказательства, заключается в том, чтобы найти критерий, по которому наш жадный алгоритм опережает решение O.

Мы будем сравнивать частичные решения, создаваемые жадным алгоритмом, с начальными сегментами решения O и шаг за шагом покажем, что жадный алгоритм работает не хуже.

Для упрощения доказательства будут введены дополнительные обозначения. Пусть i1, …, ik — множество заявок A в порядке их добавления в A. Заметьте, что | A | = k. Аналогичным образом множество заявок O будет обозначаться j1, …, jm.

Мы намерены доказать, что k = m. Допустим, заявки в O также упорядочены слева направо по соответствующим интервалам, то есть по начальным и конечным точкам. Не забывайте, что заявки в O совместимы, то есть начальные точки следуют в том же порядке, что и конечные.