| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > В орграфе найти "наибольший" замкнутый подграф |
| Автор: getch2 1.9.2014, 15:10 |
| В орграфе заданы веса вершин. Нужно найти замкнутый подграф с наибольшей суммой весов своих вершин. Для пояснения замкнутости нарисовал очень простой (на практике - куда сложнее) граф с пронумерованными вершинами:  Замкнутыми являются, например, эти подграфы: 1 -> 2 -> 3 -> 5 -> 6 -> 4 1 -> 2 -> 3 2 -> 4 и т.д. Наверняка, это давно известная задача. Но правильно составить поисковый запрос, к сожалению, не смог. Помогите с нахождением оптимального (скорость) алгоритма для решения этой задачи. |
| Автор: Akina 1.9.2014, 15:56 | ||||
Мне это напоминает задачу коммивояжёра. С дополнительныими ограничениями, вроде непосещения одного узла дважды и замкнутостью маршрута. Если удастся найти замкнутый маршрут, посещающий все узлы - он и будет решением. Если нет - то ищется максимальный маршрут. А что будет "весом" - вес узла или вес ребра - для решения в общем сиренево. |
| Автор: getch2 1.9.2014, 16:44 | ||||||
Верно, я поторопился и ошибся. Вот такой исходный граф имел в виду:  Соответственно, примеры замкнутых подграфов такие: 2 -> 4 -> 6 -> 5 -> 3 -> 1 1 -> 2 -> 3 2 -> 4
Спасибо, покопаю комивояжера. Жаль, что там только приблизительные методы. |
| Автор: Akina 1.9.2014, 17:42 | ||||
Просто я как-то привык, что, расписывая путь в графе, последним узлом указывают именно последний, а не предпоследний. В случае замкнутого - тот же, что и начальный. Это позволяет избежать таких вот накладок...
Ну почему, есть и точные. Но это полный перебор, что оправдано лишь в случае малых или сильноразреженных графов. |
| Автор: getch2 1.9.2014, 17:59 | ||
Моя формулировка была вызвана особенностью решаемой практической задачи. Там не используется последовательность вершин искомого подграфа, а только сам список вершин (не имеет значения порядок). |
| Автор: getch2 2.9.2014, 10:03 |
| Наверное, правильно сформулировать исходную задачу. Есть функция 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 4.9.2014, 12:23 |
| Похоже, иногда проще делегировать за вознаграждение решение относительно несложной задачи, нежели бороться со своей возрастной деградацией... Подскажите путь, как выйти на сильного олимпиадника по программированию? |
