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

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

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

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

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

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

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

Алгоритм

Greedy-Iterative-Activity-Selector(A, s, f): 

    Sort A by finish times stored in f
    S = {A[1]} 
    k = 1
    
    n = A.length
    
    for i = 2 to n:
        if s[i] ≥ f[k]: 
            S = S U {A[i]}
            k = i
    
    return S

Объяснение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Weighted-Activity-Selection(S):  // S = list of activities

    sort S by finish time
    opt[0] = 0  // opt[j] represents optimal solution (sum of weights of selected activities) for S[1,2..,j]
   
    for i = 1 to n:
        t = binary search to find activity with finish time <= start time for i
            // if there are more than one such activities, choose the one with last finish time
        opt[i] = MAX(opt[i-1], opt[t] + w(i))
        
    return opt[n]

Ссылки

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

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

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

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

[1]