Главная | Обратная связь | Поможем написать вашу работу!
МегаЛекции

Оптимальность для подзадач

Next Fit Algorithm (Поиск подходящего из последующих)

1. Берем новый элемент

2. Берем новый контейнер.

3. Кладем элемент в контейнер.

4. Берем следующий элемент.

5. Если элемент помещается в контейнер, идем на шаг 3. Если элемент не помещается в контейнер, идем на шаг 2.

То есть мы просто кладем элементы в контейнер, и если некий элемент уже не помещается, берем новый контейнер. Алгоритм в большинстве случаев даст наихудшие результаты из всех рассматриваемых алгоритмов. Можно придумать и более хитрый алгоритм, но у этого алгоритма есть один плюс - он не требует просмотра прошлых контейнеров. Это может оказаться полезным, если, например, контейнеры к нам подъезжают по конвейеру.

First Fit Algorithm (Поиск первого подходящего)

1. Берем новый элемент

2. Берем новый контейнер.

3. Кладем элемент в контейнер.

4. Берем следующий элемент.

5. Если элемент помещается в контейнер, идем на шаг 3. Если элемент не помещается в контейнер, проверяем остальные контейнеры по порядку. Если находится контейнер с достаточным количеством свободного места, кладем элемент в контейнер и идем на шаг 4, иначе идем на шаг 2.

То есть кладем элементы в контейнер, и если элемент уже не помещается, пытаемся найти подходящий контейнер среди уже частично заполненных. Если места не находим, берем новый контейнер.

Worst Fit Algorithm (Поиск наименее подходящего)

1. Берем новый элемент

2. Берем новый контейнер.

3. Кладем элемент в контейнер.

4. Берем следующий элемент.

5. Если элемент помещается в контейнер, идем на шаг 3. Если элемент не помещается в контейнер, берем частично заполненный контейнер с максимумом свободного места. Если элемент помещается в контейнер, кладем элемент в контейнер и идем на шаг 4, иначе идем на шаг 2.

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

Best Fit Algorithm (Поиск наиболее подходящего)

1. Берем новый элемент

2. Берем новый контейнер.

3. Кладем элемент в контейнер.

4. Берем следующий элемент.

5. Если элемент помещается в контейнер, идем на шаг 3. Если элемент не помещается в контейнер, берем частично заполненный контейнер с минимумом свободного места, но в который еще можно положить данный элемент. Если такой контейнер находится, идем на шаг 3, иначе идем на шаг 2.

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

 

Для каждого из этих алгоритмов есть вариант с предварительной сортировкой элементов по уменьшению - First Fit Decreasing, Best Fit Decreasing и т.п. То есть элементы берутся, начиная с самого крупного, что дает лучшие результаты.

 

Рассмотрим схему работы жадных алгоритмов на конкретных примерах.

Задача о выборе заявок

Даны n заявок на проведение занятий в некоторой аудитории. В каждой заявке указаны начало и конец занятия (si и fi для i-й заявки). Заявки с номерами i и j совместны, если интервалы [si, fi) и [sj, fj) не пересекаются (т. е. fi ≤ sj или fj ≤ si). Задача о выборе заявок состоит в том, чтобы набрать максимальное количество совместных друг с другом заявок.

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

На вход данному алгоритму подаются массивы начала и окончания занятий. Множество A состоит из номеров выбранных заявок, а j — номер последней заявки. Жадный алгоритм ищет заявку, начинающуюся не ранее окончания j-той, затем найденную заявку включает в A, а j присваивает ее номер.

Алгоритм работает за O(nlogn+n), т. е. сортировка плюс выборка. На каждом шаге выбирается наилучшее решение. Покажем, что в итоге получится оптимум.

Доказательство. Заметим, что все заявки отсортированы по неубыванию времени окончания. Заявка номер 1, очевидно, входит в оптимум (если нет, то заменим самую раннюю заявку в оптимуме на нее, от этого хуже не станет). Выкинув все заявки, противоречащие первой, получим исходную задачу с меньшим количеством заявок. Рассуждая по индукции, аналогичным образом приходим к оптимальному решению.

 

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

Принцип жадного выбора

Говорят, что к задаче оптимизации применим принцип жадного выбора, если последовательность локально оптимальных выборов дает глобально оптимальное решение. В этом состоит главное отличие жадных алгоритмов от динамического программирования: во втором просчитываются сразу последствия всех вариантов.

Чтобы доказать, что жадный алгоритм дает оптимум, нужно попытаться провести доказательство, как в задаче о выборе заявок. Сначала мы показываем, что жадный выбор на первом шаге не закрывает путь к оптимальному решению: для любого решения есть другое, согласованное с жадным выбором и не хуже первого. Потом мы показываем, что подзадача, возникшая после жадного выбора на первом шаге, аналогична исходной. По индукции будет следовать, что такая последовательность жадных выборов дает оптимальное решение.

Оптимальность для подзадач

Это свойство говорит о том, что оптимальное решение всей задачи содержит в себе оптимальные решения подзадач. Например, в задаче о выборе заявок можно заметить, что если A — оптимальный набор заявок, содержащий заявку номер 1, то A′ = A \ {1} — оптимальный набор заявок для меньшего множества заявок S′, состоящего из тех заявок, для которых si ≥ f1.

Поделиться:





Воспользуйтесь поиском по сайту:



©2015 - 2024 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...