Проблема выбора активности

Комбинаторная задача оптимизации

Задача выбора активности — это комбинаторная задача оптимизации, касающаяся выбора неконфликтующих действий для выполнения в заданном временном интервале , учитывая набор действий, каждое из которых отмечено временем начала (s _i ) и временем окончания (f _i ). Задача состоит в том, чтобы выбрать максимальное количество действий, которые может выполнить один человек или машина , предполагая, что человек может работать только над одним действием одновременно. Задача выбора активности также известна как задача максимизации интервального планирования (ISMP) , которая является особым типом более общей задачи интервального планирования .

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

Формальное определение

Предположим, что существует n действий, каждое из которых представлено временем начала s _i и временем окончания f _i . Два действия i и j называются неконфликтующими, если s _i ≥ f _j или s _j ≥ f _i . Задача выбора действия состоит в нахождении максимального набора решений (S) неконфликтующих действий, или, точнее, не должно существовать набора решений S' такого, что |S'| > |S| в случае, если несколько максимальных решений имеют одинаковые размеры.

Оптимальное решение

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

Алгоритм

Жадный - Итеративный - Активность - Селектор ( A , s , f ) :    Сортировать A по времени финиша, сохраненному в f        С = { А [ 1 ]}    к = 1    n = A . длина    для i = 2 до n :      если s [ i ] ≥ f [ k ] :     С = С У { А [ я ]}     к = я    возврат S 

Объяснение

Строка 1: Этот алгоритм называется Greedy-Iterative-Activity-Selector , потому что это в первую очередь жадный алгоритм, а затем он итеративный. Существует также рекурсивная версия этого жадного алгоритма.

• ${\displaystyle A}$представляет собой массив, содержащий действия .
• ${\displaystyle s}$представляет собой массив, содержащий время начала действий в . ${\displaystyle A}$
• ${\displaystyle f}$ представляет собой массив, содержащий время окончания действий в . ${\displaystyle A}$

Обратите внимание, что эти массивы индексируются, начиная с 1 и до длины соответствующего массива.

Строка 3: Сортирует в порядке возрастания времени окончания массива действий , используя время окончания, сохраненное в массиве . Эту операцию можно выполнить во времени, используя, например, алгоритмы сортировки слиянием, сортировки кучей или быстрой сортировки. ${\displaystyle A}$ ${\displaystyle f}$ ${\displaystyle O(n\cdot \log n)}$

Строка 4: создает набор для хранения выбранных действий и инициализирует его действием с самым ранним временем окончания. ${\displaystyle S}$ ${\displaystyle A[1]}$

Строка 5: создает переменную , которая отслеживает индекс последнего выбранного действия. ${\displaystyle k}$

Строка 9: Начинает итерацию со второго элемента массива до его последнего элемента. ${\displaystyle A}$

Строки 10,11: Если время начала действия ( ) больше или равно времени окончания последнего выбранного действия ( ), то оно совместимо с выбранными действиями в наборе и, таким образом, может быть добавлено к . ${\displaystyle s[i]}$ ${\displaystyle ith}$ ${\displaystyle A[i]}$ ${\displaystyle f[k]}$ ${\displaystyle A[k]}$ ${\displaystyle A[i]}$ ${\displaystyle S}$ ${\displaystyle S}$

Строка 12: Индекс последнего выбранного действия обновляется до только что добавленного действия . ${\displaystyle A[i]}$

Доказательство оптимальности

Пусть будет набором действий, упорядоченных по времени окончания. Предположим, что — оптимальное решение, также упорядоченное по времени окончания; и что индекс первого действия в A равен , т. е. это оптимальное решение не начинается с жадного выбора. Мы покажем, что , которое начинается с жадного выбора (действие 1), является другим оптимальным решением. Поскольку , и действия в A не пересекаются по определению, действия в B также не пересекаются. Поскольку B имеет то же количество действий, что и A , то есть , B также является оптимальным. ${\displaystyle S=\{1,2,\ldots ,n\}}$ ${\displaystyle A\subseteq S}$ ${\displaystyle k\neq 1}$ ${\displaystyle B=(A\setminus \{k\})\cup \{1\}}$ ${\displaystyle f_{1}\leq f_{k}}$ ${\displaystyle |A|=|B|}$

После того, как жадный выбор сделан, проблема сводится к поиску оптимального решения для подзадачи. Если A является оптимальным решением исходной задачи S , содержащей жадный выбор, то является оптимальным решением задачи выбора активности . ${\displaystyle A^{\prime }=A\setminus \{1\}}$ ${\displaystyle S'=\{i\in S:s_{i}\geq f_{1}\}}$

Почему? Если бы это было не так, выберите решение B ′ для S ′ с большим количеством действий, чем A ′, содержащее жадный выбор для S ′. Тогда добавление 1 к B ′ дало бы допустимое решение B для S с большим количеством действий, чем A , что противоречит оптимальности.

Задача выбора взвешенной активности

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

Рассмотрим оптимальное решение, содержащее действие k . Теперь у нас есть неперекрывающиеся действия слева и справа от k . Мы можем рекурсивно найти решения для этих двух наборов из-за оптимальной подструктуры. Поскольку мы не знаем k , мы можем попробовать каждое из действий. Этот подход приводит к решению. Его можно оптимизировать еще больше, учитывая, что для каждого набора действий в , мы можем найти оптимальное решение, если бы мы знали решение для , где t — последний неперекрывающийся интервал с j в . Это дает решение. Его можно оптимизировать еще больше, учитывая, что нам не нужно рассматривать все диапазоны , а только . Таким образом, следующий алгоритм дает решение: ${\displaystyle O(n^{3})}$ ${\displaystyle (i,j)}$ ${\displaystyle (i,t)}$ ${\displaystyle (i,j)}$ ${\displaystyle O(n^{2})}$ ${\displaystyle (i,j)}$ ${\displaystyle (1,j)}$ ${\displaystyle O(n\log n)}$

Взвешенный - Активность - Выборка ( S ) : // S = список активностей  сортировать S по времени окончания     opt [ 0 ] = 0 // opt[j] представляет оптимальное решение (сумму весов выбранных действий) для S[1,2..,j]     для i = 1 до n :      t = бинарный поиск для поиска активности с временем окончания <= времени начала для i               // если таких занятий несколько, выбираем то, у которого последнее время окончания опт [ i ] = МАКС ( опт [ i -1 ], опт [ t ] + w ( i ))       возврат опц [ н ] 

Ссылки

1. Динамическое программирование с введением в выбор взвешенной активности

Внешние ссылки

• Проблема выбора вида деятельности