Анализ алгоритмов
Хотя этот жадный метод базируется на вполне естественном принципе, оптимальность возвращаемого множества интервалов не столь очевидна.
В самом деле, торопиться с вердиктом вообще не стоит: идеи, приведшие к описанным выше неоптимальным версиям жадного алгоритма, также на первый взгляд выглядели перспективно.
Для начала можно сразу утверждать, что интервалы множества A, возвращаемого алгоритмом, совместимы.
Множество A состоит из совместимых заявок.
Как упоминалось в начале главы, идея, заложенная в основу этого доказательства, заключается в том, чтобы найти критерий, по которому наш жадный алгоритм опережает решение O. Мы будем сравнивать частичные решения, создаваемые жадным алгоритмом, с начальными сегментами решения O и шаг за шагом покажем, что жадный алгоритм работает не хуже.
Для упрощения доказательства будут введены дополнительные обозначения. Пусть i1, …, ik — множество заявок A в порядке их добавления в A. Заметьте, что
| A | = k. Аналогичным образом множество заявок O будет обозначаться j1, …, jm. Мы намерены доказать, что k = m. Допустим, заявки в O также упорядочены слева направо по соответствующим интервалам, то есть по начальным и конечным точкам. Не забывайте, что заявки в O совместимы, то есть начальные точки следуют в том же порядке, что и конечные.
- Алгоритмы, которые работают бесконечно
- Бесконечные пространства выборки
- Независимые события
- Конечные вероятностные пространства
- Простой рандомизированный план
- Планы и их продолжительность
- Анализ алгоритмов маркировки
- Достижение линейного ожидаемого времени выполнения
- Структура данных для хранения подквадратов
- Оформление отчета по практике по ГОСТу 2021/2022
- Оформление ВКР по ГОСТу
- Как составить бизнес-план своими силами
- Оформление эссе по ГОСТу
- Оформление презентации по ГОСТу
- Оформление статьи по ГОСТу
- Оформление дипломной работы по ГОСТ 2021/2022
- Оформление курсовой работы по ГОСТу
- Оформление контрольной работы по ГОСТу