Алгоритм поиска пути на графе с учетом как узлов, так и ребер - PullRequest
Новая
       52

Алгоритм поиска пути на графе с учетом как узлов, так и ребер

4 голосов
/ 19 марта 2012

У меня есть неориентированный граф.Пока предположим, что график завершен.С каждым узлом связано определенное значение.Все ребра имеют положительный вес.Я хочу найти путь между любыми двумя заданными узлами так, чтобы сумма значений, связанных с узлами пути, была максимальной, и в то же время длина пути была в пределах заданного порогового значения.Решение должно быть «глобальным», что означает, что полученный путь должен быть оптимальным среди всех возможных путей.Я попробовал подход линейного программирования, но не могу сформулировать его правильно.Любые предложения или другой метод решения будут очень полезны.

Спасибо!

Ответы [ 4 ]

1 голос
/ 19 марта 2012

Если вы ищете алгоритм в общем графе, ваша задача является NP-Complete, предположим, что порог длины пути равен n-1, и каждая вершина имеет значение 1. Если вы найдете решение для вашей проблемы, вы можете сказать, данный граф имеет гамильтонов путь или нет. Фактически, если ваш путь максимизированного размера вершины имеет значение n, то у вас есть гамильтонов путь. Я думаю, что вы можете использовать что-то вроде релаксации Хельда-Карпа, чтобы найти хорошее решение.

1 голос
/ 19 марта 2012

Это может быть не идеально, но если пороговое значение (T) достаточно мало, есть простой алгоритм, который работает в O (n ^ 3 T ^ 2).Это небольшая модификация Флойд-Варшалла. 

d = int array with size n x n x (T + 1)
initialize all d[i][j][k] to -infty
for i in nodes:
    d[i][i][0] = value[i]
for e:(u, v) in edges:
    d[u][v][w(e)] = value[u] + value[v]

for t in 1 .. T
    for k in nodes:
       for t' in 1..t-1:
           for i in nodes:
               for j in nodes:           
                  d[i][j][t] = max(d[i][j][t],
                                   d[i][k][t'] + d[k][j][t-t'] - value[k])

The result is the pair (i, j) with the maximum d[i][j][t] for all t in 0..T

РЕДАКТИРОВАТЬ: это предполагает, что пути могут быть непростыми, они могут содержать циклы.

EDIT2: Предполагается также, что если узел появляется в пути более одного раза, он будет учитываться более одного раза.Это явно не то, что хотел ОП!

0 голосов
/ 22 марта 2012

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

0 голосов
/ 19 марта 2012

Целочисленная программа (это может быть хорошей идеей или нет):

Для каждой вершины v пусть x v будет 1, если вершина v посещена, и 0 в противном случае.Для каждой дуги a пусть y a будет количеством раз, которое используется дуга a.Пусть s будет источником, а t будет пунктом назначения.Цель:

увеличить ∑ v значение (v) x v .

Ограничения:

∑ a значение (a) y a ≤ порога ∀v, ∑ a имеет голову v y a - ∑ a имеет хвост v y a = {-1, если v = s;1, если v = t;0 в противном случае (сохранение потока)
∀v ≠ x, x v ≤ ∑ a имеет голову v y a (необходимо ввести вершину для посещения)
∀v, x v ≤ 1 (посещать каждую вершину не более одного раза)
∀v ∉ {s, t}, ∀ вырезывает S, отделяющие вершину v от {s, t},x v ≤ ∑ a такой, что хвост (a) ∧ S ∧ head (a) ∈ S y a (выгода только от вершин, а не на изолированных петлях).

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

...