Сколько подзадач есть в этом рекурсивном разборе выбора действий? - PullRequest
Новая
       44

Сколько подзадач есть в этом рекурсивном разборе выбора действий?

1 голос
/ 22 апреля 2019

Выбор активности : При заданном наборе действий A с временем начала и окончания найдите максимальное подмножество взаимно совместимых действий.

Моя проблема

Два подхода кажутся одинаковыми, но проблема numSubblems в firstApproach является экспоненциальной, а во secondApproach - O(n^2). Если бы я запомнил результат, то как я могу запоминать первый подход?

Наивный первый подход 

let max = 0
for (a: Activities):
    let B = {Activities - allIncompatbleWith(a)}
    let maxOfSubproblem = ActivitySelection(B)
    max = max (max, maxOfSubproblem+1)
return max


1. Assume a particular activity `a` is part of the optimal solution
2. Find the set of activities incompatible with `a: allIncompatibleWith(a)`.
2. Solve Activity for the set of activities: ` {Activities - allImcompatibleWith(a)}`
3. Loop over all activities  `a in Activities` and choose maximum.

Второй подход, основанный на разделе 16.1 CLRS 

Solve for S(0, n+1)

let S(i,j) = 0
for (k: 0 to n):
    let a = Activities(k)
    let S(i,k) = solution for the set of activities that start after activity-i finishes and end before activity-k starts
   let S(k,j) = solution for the set of activities that start after activity-k finishes and end before activyty-j starts.
    S(i,j) = max (S(i,k) + S(k,j) + 1)
return S(i,j)


1. Assume a particular activity `a` is part of optimal solution
2. Solve the subproblems for: 
(1) activities that finish before `a` starts 
(2) activities that start after `a` finishes.

Let S(i, j) refer to the activities that lie between activities i and j (start after i and end before j). 
Then S(i,j) characterises the subproblems needed to be solved above. ),
S(i,j) = max S(i,k) + S(k,j) + 1, with the variable k looped over j-i indices.

Мой анализ

firstApproach:

#numSubproblems = #numSubset of the set of all activities = 2^n.

secondApproach:

#numSubproblems = #number of ways to chooose two indicises from n indices, with repetition. = n*n = O(n^2)

Два подхода кажутся одинаковыми, но проблема numSubblems в firstApproach является экспоненциальной, а во secondApproach - O(n^2). В чем подвох? Почему они разные, даже если эти два подхода кажутся одинаковыми?

Ответы [ 2 ]

1 голос
/ 24 апреля 2019

Два подхода кажутся одинаковыми

Два решения не одинаковы. Разница заключается в количестве состояний, возможных в пространстве поиска. Оба решения имеют перекрывающиеся подзадачи и оптимальную подструктуру. Без напоминания оба решения просматривают все пространство поиска.

Раствор 1

Это решение обратного отслеживания , в котором пробуются все подмножества, совместимые с действием, и каждый раз, когда выбирается действие, ваше решение-кандидат увеличивается на 1 и сравнивается с текущим сохраненным максимумом. Он не использует понимание времени начала и окончания деятельности. Основное различие заключается в том, что состояние вашего повторения является полным подмножеством действий (совместимых действий), для которых необходимо определить решение (независимо от времени их начала и окончания). Если бы вы запомнили решение, вам пришлось бы использовать битовые маски (или (std::bitset в C ++) для хранения решения для подмножества действий. Вы также можете использовать std::set или другие Set структуры данных.

Решение 2

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

0 голосов
/ 22 апреля 2019

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

Что такое памятование?

Проще говоря, памятование - это не что иное, как рекурсивное решение(сверху вниз), в котором хранится результат вычисленного решения подзадачи.И если эту же подзадачу нужно вычислить снова, вы возвращаете исходное сохраненное решение вместо его повторного вычисления.

Запоминание в вашем первом рекурсивном решении

В вашем случае каждая подзадача имеет видпоиск оптимального выбора видов деятельности для подмножества.Так что памятка (в вашем случае) приведет к сохранению оптимального решения для всех подмножеств.

Без сомнения, памятка даст вам повышение производительности, избегая повторного вычисления решения на подмножестве действий.это было «замечено» ранее, но оно не может (в этом случае) уменьшить сложность времени до полиномиального времени, потому что вы в конечном итоге сохраняете подрешения для каждого подмножества (в худшем случае).

ГдеПамятка дает нам реальную выгоду?

С другой стороны, если вы видите this , где памятка применяется для рядов Фибоначчи, общее количество подрешения, которое вы должны сохранить, является линейнымс размером ввода.И, таким образом, это уменьшает экспоненциальную сложность до линейной.

Как вы можете запомнить первое решение

Для применения запоминания в первом подходе вам необходимо поддерживать подрешения.Вы можете использовать структуру данных Map<Set<Activity>, Integer>, в которой будет храниться максимальное количество совместимых действий для данного Set<Activity>.В java equals() на java.util.Set работает правильно во всех реализациях, поэтому вы можете использовать его.

Ваш первый подход будет изменен следующим образом: 

// this structure memoizes the sub-solutions
Map<Set<Activity>, Integer> map; 
ActivitySelection(Set<Activity> activities) {
    if(map contains activities)
        return map.getValueFor(activities);
    let max = 0
    for (a: activities):
        let B = {Activities - allIncompatbleWith(a)}
        let maxOfSubproblem = ActivitySelection(B)
        max = max (max, maxOfSubproblem+1)
    map.put(activities, max)
    return max
}

На более легкой ноте:

Временная сложность второго решения (CLRS 16.1) будет O(n^3) вместо O(n^2).Вам нужно будет 3 петли для i, j и k.Пространственная сложность для этого решения O(n^2).

...