Попытка выяснить, какой алгоритм использовать

Question

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

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

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

Есть идеи?

Answer 1

У вас есть максимальное количество игр, в которые вы можете играть? Тогда это звучит как вариант задачи о рюкзаке http://en.wikipedia.org/wiki/Knapsack_problem (некоторые подходы к этой проблеме можно найти в статьеk, хотя проблема является NP-полной и как таковая не может быть эффективно решена в принципе).

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

Answer 2

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

Edit:

Поскольку граф ацикличен, кратчайший путь будет работать и для отрицательных ребер. См. Самый короткий / самый длинный путь в DAG в http://algs4.cs.princeton.edu/44sp/

Answer 3

Может быть, вам поможет A * алгоритм , то есть вы сделаете обоснованное предположение (минимальная известность для этого маршрута) для каждого маршрута в своем графике, следуйте наиболее многообещающему и, если увидитеон становится ниже, чем предположение для еще не пройденного маршрута, следуйте по этому новому маршруту и ​​остановитесь здесь.