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

Для пояснения замкнутости нарисовал очень простой (на практике - куда сложнее) граф с пронумерованными вершинами:

Замкнутыми являются, например, эти подграфы:
1 -> 2 -> 3 -> 5 -> 6 -> 4
1 -> 2 -> 3
2 -> 4
и т.д.

Наверняка, это давно известная задача. Но правильно составить поисковый запрос, к сожалению, не смог.

Помогите с нахождением оптимального (скорость) алгоритма для решения этой задачи.

Замкнутость этого подграфа мне представляется сомнительной.


Мне это напоминает задачу коммивояжёра. С дополнительныими ограничениями, вроде непосещения одного узла дважды и замкнутостью маршрута.
Если удастся найти замкнутый маршрут, посещающий все узлы - он и будет решением. Если нет - то ищется максимальный маршрут. А что будет "весом" - вес узла или вес ребра - для решения в общем сиренево. 

Верно, я поторопился и ошибся. Вот такой исходный граф имел в виду:

Соответственно, примеры замкнутых подграфов такие:
2 -> 4 -> 6 -> 5 -> 3 -> 1
1 -> 2 -> 3
2 -> 4


Спасибо, покопаю комивояжера. Жаль, что там только приблизительные методы.

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


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

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

Наверное, правильно сформулировать исходную задачу.

Есть функция F(X) = b[1](X) + b[2](X) + ... b[N](X) - (a[1](X) + a[2](X) + ... a[N](X)).

где b[i](X) и a[i](X) - функции, значения которых положительные вещественные числа.

При этом между этими функциями во всей области определения заданы следующие соотношения:
b[i] = a[i] + Ɛ[i] для всех i = 1 .. N, где Ɛ[k] - относительно слабые флуктуации.

И для некоторых функций имеются еще следующие соотношения:
либо b[k] = b[n] - a[m] + Ɛ[j[k]], либо b[k] = b[n] + b[m] + Ɛ[j[k]], либо a[k] = a[n] + a[m] + Ɛ[j[k]], либо a[k] = a[n] - b[m] + Ɛ[j[k]].

Задача для заданного X найти подпоследовтельности значений {p} из {1..N} и {q} из {1..N}, чтобы
F2 = b[p[1]] + b[p[2]] + b[p[p_max]] - (a[q[1]] + a[q[2]] + ... + a[q[q_max]]) = ±Ɛ[t[1]] ± Ɛ[t[2]] ± ... ± Ɛ[t[t_max]] было наибольшим.

Подошел к решению следующим образом (в лоб). Сначала выше обозначенные взаимосвязи между b[i] и a[j] решил представить в виде орграфа. Затем найти все его связанные компоненты и по итогу посчитать их сумму. С наибольшей суммой - и есть искомые подпоследовательности {p} и {q}.

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

Это сообщение отредактировал(а) getch2 - 2.9.2014, 10:48

Похоже, иногда проще делегировать за вознаграждение решение относительно несложной задачи, нежели бороться со своей возрастной деградацией...

Подскажите путь, как выйти на сильного олимпиадника по программированию?