Есть множество задач вида
interface Тask{
    execute();
}
, связанных набором зависимостей:
@Before(Task[]) -- задача должна быть гарантированно выполнена до выполениня всех задач из массива;
@After(Task[]) -- задача может быть выполнена только после выполнения всех задач из массива;
@If(contextParameter = <someValue>) -- задача может быть выполнена только если некая переменная (из доступного всех задачам контекста) равна <someValue>;
@IfNot(contextParameter = <someValue>) -- задача может быть выполнена только если некая переменная (из доступного всех задачам контекста) не равна <someValue>;
и т.д. и т.п. самые разные условия.

Задачи выполняются последовательно, никакой многопоточности.

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

Есть ли какой-то общий подход к решению таких проблем? готовые алгоритмы? возможно, построение графа или матрицы зависимостей? 
Вообщем нужен совет, как бы вы это делали?  

Это сообщение отредактировал(а) Maksym - 3.7.2009, 12:06

Выглядит как построение графа. Копать туда

Если рассматривать только связи Before и After, то получается просто граф зависимостей, и на нём это - задача топологической сортировки, решается довольно просто обходом в глубину.

А связи If я не очень понял - эти переменные меняются в результате выполнения задач что ли?

Я думаю, что переменные известны перед построением. Таким образом можно просто отбросить те задачи, которые на данный момент не будут использованы.

Формулировка напоминает задачи, связанные с сетевыми графиками.
Там надо повышать скорость выполнения работ.
Там есть разнообразные методы решения.
Я бы шёл от них.

Это сообщение отредактировал(а) nworm - 5.7.2009, 00:09

Считаем, что все дополнительные условия (переменные contextParameter) заранее известны, и задачи эти условия не изменяют.

Нужно слегка изменить данные. Для каждой задачи оставить только список After[]. Если у задачи есть список Before[], то эта задача добавляется в списки After[] каждой зависимой задачи. В результате получается орграф. Для каждой задачи храним статус - не выполнена, ожидает выполнения или выполнена.

В цикле перебираем все задачи со статусом "не выполнена". Для каждой такой задачи выполняем следующую процедуру:

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

2. Помечаем задачу, как ожидающую выполнения.

3. Если у задачи нет зависимостей (список After[] пуст), то переходим к шагу 8.

4. Выбираем очередную задачу из списка After[].

5. Если статус задачи из списка - "не выполнена", то рекурсивно вызываем процедуру для нее. Переходим к шагу 7.

6. Если статус задачи из списка - "ожидает выполнения", значит, в орграфе обнаружился цикл (присутствует циклическая зависимость задач), и выстроить нужную последовательность невозможно. Сигнализируем об ошибке и выходим из процедуры.

7. Если в списке After[] еще есть непроверенные элементы, то переходим к шагу 4.

8. Выполняем задачу (либо добавляем в очередь выполнения), помечаем ее, как выполненную. Выходим из процедуры.

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


Изменяют, см.выше. В любом случае, спасибо за подробный ответ: подумаю, попытаюсь использовать.


Это я и сам понял  но как-то мелко копнул видимо -- ниче не выкопалось.

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

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

Самое простое и верное (точно будет правильно работать) что приходит на ум это перебор с возвратом. 
Этот алгоритм не только скажет есть ли решение или нет но и скажет сколько их и все покажет.
Вопрос только в том как строить дерево полного перебора и как по нему ходить.

Некоторые оптимизации выше уже подсказали. 

P.S.
Хочешь или нет а этот алгоритм придеться реализовывать.
Иначе как ты будешь проверять правильность работы другого алгоритма?
ИМХО: другого алгоритма для решения этой задачи нет , т.к. выполнение task-a ведет к изменению контекста, который может влиять на  условия выполнения других task-ов.