алгоритм планирования - только первое посещение

Question

Мне нужно знать, была ли изучена следующая проблема:

Давайте нарисуем ациклический ориентированный граф G. Граф связен, у него ровно одна исходная вершина (без входящих узлов) и ровно один стоквершина (без исходящих узлов).

Каждой вершине была назначена неотрицательная цена в долларах, а также цвет.

Цель состоит в том, чтобы найти путь от начала до впадины, который максимизирует сумму цен посещенных ребер.

Подвох в том, что цена получается только тогда, когда вершина конкретногоцвет посещается впервые.Например, когда мы видим красную вершину с ценой 1 доллар, затем синюю с 2 долларами, а затем красную с 30 долларами, общая стоимость составляет 3 доллара.

Приблизительный размер моей конкретной задачи: 50000 вершин, 3000 цветов, типичная длина прогулки.от начала тонуть около 200 ребер.

             ------>[B red $1]---                   ---->[E red $1]----
            /                    \                 /                   \
[A black $0]                      ==>[D black $0]==                     ==>[G black $0]
            \                    /                 \                   /
             ---->[C green $2]---                   ->[F green $1000]--

Answer 1

Это хороший вариант проблемы кратчайшего пути, который рассматривает динамические графы, то есть графы, которые меняются со временем (по мере удаления от источника вес ребер изменяется). Алгоритм Дейкстры решит его, поскольку веса ребер вычисляются по ходу, поэтому тот факт, что веса ребер различаются в зависимости от того, где вы были, не имеет значения. Вот описание Википедии с соображениями по проблеме изменения цвета, выделенными жирным шрифтом :

Пусть узел, с которого мы начинаем, будет называться начальным узлом. Позволять расстояние от узла Y будет расстоянием от начального узла до Y. Алгоритм Дейкстры назначит некоторые начальные значения расстояния и попробуйте улучшить их шаг за шагом.

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

2. Пометить все узлы как непосещенные. Установите начальный узел как текущий. Создайте набор из непосещенных узлов, который называется непосещенным множеством. состоящий из всех узлов, кроме начального узла.

3. Для текущего узла рассмотрите все его не посещенные соседи и вычислите их предварительные расстояния. Теперь это зависит от выбранного пути до этой точки. Например, если текущий узел А обозначен расстоянием 6, а край, соединяющий его с сосед B имеет длину 2 в зависимости от цветного веса , тогда расстояние до B по пути до будет 6 + 2 = 8. Если это расстояние меньше ранее записанного расстояния, затем переписать это расстояние. Хотя сосед был осмотрен, он не помечен как посещенный в настоящее время, и он остается в непосещенный набор.

4. Когда мы закончим с учетом всех соседей текущего узла, отметьте текущий узел как посещенный и удалите его из непосещенный набор. Посещенный узел никогда не будет проверен снова; его записанное расстояние является окончательным и минимальным.

5. Если узел назначения был отмечен как посещенный, остановитесь. Алгоритм завершен.

6. Установите не посещаемый узел, помеченный наименьшим предварительным расстоянием, в качестве следующего "текущего узла" и вернитесь к шагу 3.

Наннинини и Либерти провели хороший обзор Кратчайших путей на динамических графиках .

Answer 2

Если я правильно понимаю проблему, ее можно решить за O ( E ) следующим образом.Давайте начнем с формального определения его решения.

Учитывая DAG G = ( V , E ), пусть FS ( i) будет передней звездой вершины i :

FS ( i ) = {( x , y ) в E : x = i }

let C theбыть набором цветов посещенных вершин и пусть p [ i ] и c [ i ] будут соответственно ценой и цветом вершины i ;Теперь определим вознаграждение r за переход от вершины i к вершине j , принадлежащей FS ( i ) как

r [ i , j ] = p [ j ], если c [ j ] не принадлежит C

в противном случае r [ i , j ] = 0 (если c [ j ] принадлежит C )

Теперь мы готовы определить наши подзадачи следующим образом:

D ( i , j , C ) = max на k , принадлежащих FS ( i ) {r [ i , k ] + D ( k , j , C union {c [ k ]})}

с D ( i , i , C ) = 0 в качестве условия завершения (требуется при достижении узла приемника)

Исходная задача, которая должна быть решена, поэтому D ( s , t , {c [ s ]}), где s и t - соответственно вершина источника и стокаes:

D ( s , t , {c [ s ]}) = max on k принадлежащий FS ( s ) {r [ s , k ] + D ( k , t , {c [ s ]} union {c [ k ]})}

Чтобы решить эту проблему, высохранить DAG, используя списки смежности, соответствующие прямым звездам вершин.Затем, начиная с исходной вершины, вы определяете стоимость, связанную со всеми путями, с учетом цветового ограничения.Поскольку вы в основном исследуете прямые звезды вершин и никогда не возвращаетесь назад, общая сложность составляет O ( E ) с использованием хеш-таблицы для представления набора, так что для вставки теста цвета и членства требуется O (1) время в среднем.То, что я назвал union , на самом деле является операцией insert (результаты одинаковы, так как каждый раз, когда вы выполняете объединение одиночного набора).

Answer 3

Интересная проблема. Это NP-сложный, но не похожий ни на один из классик литературы по алгоритмам аппроксимации.

Подтверждение на примере сокращения из набора экземпляров обложки {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}}. Все края направлены вниз.

 s:$0
 | \
 |   \
 |     \
 |     1:$100
 |      |
!A:$1  2:$100
 |      |
 |     3:$100
 |     /
 |   /
 | /
 *:$0
 | \
 |   \
 |     \
 |     2:$100
!B:$1   |
 |     4:$100
 |     /
 |   /
 | /
 *:$0
 | \
 |   \
 |     \
 |     3:$100
!C:$1   |
 |     4:$100
 |     /
 |   /
 | /
 *:$0
 | \
 |   \
 |     \
 |     4:$100
!D:$1   |
 |     5:$100
 |     /
 |   /
 | /
 t:$0

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