Алгоритм поиска пути для увеличения прибыли - PullRequest
Новая
       131

Алгоритм поиска пути для увеличения прибыли

3 голосов
/ 06 августа 2020

Допустим, у нас есть ориентированный граф, в котором каждое ребро содержит кортеж (d, p) , где d - это расстояние, которое необходимо пройти, а p - прибыль, которую вы получите, пройдя это ребро, а после прохождения ребра его прибыль будет установлена ​​на 0 . Мой вопрос: учитывая начальный узел и максимальное расстояние D (такое, что Σd по всем пройденным ребрам), решить для максимальной прибыли, где прибыль определяется как Σp по всем пройденным ребрам.

Вы можете повторно посещать узлы и перебирать ребра.

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

1 Ответ

1 голос
/ 07 августа 2020

Учитывая масштаб проблемы, мы могли бы успешно атаковать ее с помощью целочисленной программы. Для каждого направленного ребра e пусть x(e) будет неотрицательной целочисленной переменной, представляющей количество раз, когда мы используем ребро, а y(e) будет переменной 0-1, представляющей количество раз, когда мы получаем прибыль от ребра. Для каждой вершины v пусть w(v) будет переменной 0-1, указывающей, посещается ли v, а z(v) будет переменной 0-1, указывающей, является ли v конечной вершиной. Простая часть целочисленной программы - это 

maximize sum_e p(e) y(e)
subject to
y(e) <= x(e)            # can't profit from an edge if we don't use it
for all e, y(e) <= w(head(e))    # can't profit unless we visit
for all e, y(e) <= w(tail(e))    # can't profit unless we visit
sum_e d(e) x(e) <= D    # bounded distance
sum_v z(v) = 1          # exactly one ending vertex
# path constraints
for all vertices v, sum_{e with head v} x(e) - sum_{e with tail v} x(e) =
    z(v) - 1 if v is the starting vertex,
    z(v)     otherwise.

Жесткая часть - предотвращение циклов в никуда (аналог ограничения исключения субтура для TSP). Если нам это удастся, то мы сможем найти след Эйлера в подграфе, чьи ребра имеют кратность, обозначенную y(e).

Мы используем ту же стратегию, что и TSP - пишем экспоненциальное количество ограничений, применяем их после c. 

for all sets of vertices S containing the starting vertex,
    for all vertices v not in S,
        sum_{directed edges e entering S} y(e) >= w(v)
...