У меня есть проблема, которая как мне кажется могла бы быть решена с помощью графов, а опыта работы с ними – нет. Задача заключается в следующем: Дан связанный неориентированный граф. Причем веса ребер представляют собой квадраты разницы весов вершин. Каждое ребро можно „разрезать”, но при этом веса концевых вершин меняются на сумму веса обеих вершин. Задача – декомпозировать граф на отдельные элементы, причем суммарная цена всех срезов должна быть минимальной. Крайний общий вес вершин не имеет значения. Есть ли какие-нибудь стандартные подходы для решения подобных задач (кроме полного перебора, конечно)? Или может возникнет идея алгоритма для поиска оптимального пути декомпозирования постоянно меняющихся графов?? Предварительно благодарю за любой совет!
Декомпозировать граф на отдельные элементы- что значит? Разбить чтобы была одна вершина, если так то это все ребра резать вариант один. Цена среза это что? Сумаа конечных вершин?
Под "декомпозировать" я имею ввиду разрезать граф на отдельные вершины. А цена каждого среза равна весу разрезаемого ребра. И суммарная цена - соответственно сумме цен всех срезов. Цель - срезать все ребра, но надо сделать это с минимальной ценой. Так, как каждый срез сразу меняет вес двух вершин и как следствие - вес связанных с ними ребер. Поэтому общая цена сильно зависит от последовательности разрезания ребер. Надо найти оптимальную (или близкую к ней) последовательность разрезов.
vgoltsev Вроде есть похожие задачи, связанные с разбиением графов, у меня есть книжки, после НГ посмотрю...
"Меняются" - это уменьшаются или как? То есть, если до разрезания по ребру (x,y) веса вершин были w(x)=a и w(y)=b, то после разреза веса будут w(x)=-b и w(y)=-a. Так? Если так, то веса вершин конечного графа будут образовывать некоторую перестановку весов вершин исходного графа с точностью до знаков.
Eсли до разрезания по ребру (x,y) веса вершин были w(x)=a и w(y)=a, то после разреза веса будут w(x)=a+b и w(y)=a+b. Посылаю прикрепленным файлом пример в виде doc-файла. В предыдущем сообщении послал тот же файл, но он почему то не появился в форуме.
Не могу понять почему прикрепленный файл не появляется в форуме. Уже 2 раза посылаю. Сейчас посылаю еще раз.
Почему то посланный файл с расширением doc не проходит, а архивированный - проходит но у него исчезает расширение и его невозможно прочесть ((. попропбую послать файл в Word формате но без расширения.
Буду предполагать, что веса всех вершин неотрицательны. По индукции несложно показать, что для "звезды" (несколько вершин, каждая из которых соединена единственным ребром с одной и той же центральной вершиной) оптимальной является стратегия разрезов, при которой каждый раз разрезается ребро, ведущее в концевую вершину с минимальным весом. Пусть теперь нам дан произвольный граф. Его можно рассматривать как объединение звезд, образованных каждой из вершин и всеми ее соседями так, что каждое ребро (x,y) входит ровно в две звезды: с центром в x и с центром в y. При этом процесс разрезания графа можно рассматривать как разрезание каждой из звезд его составляющих. Понятно, что если каждая из звезд будет разрезана оптимальным образом (см. выше), то и соответствующее разрезание графа будет оптимальным (со стоимостью равной половине суммы стоимости разрезов всех звезд). Отсюда немедленно получается такой алгоритм: 1) Выкидываем из графа изолированные вершины. Если получился пустой граф, КОНЕЦ. 2) Найдем в графе вершину x с минимальным весом. 3) Среди соседей x найдем вершину y с минимальным весом. 4) Разрезаем ребро (x,y). 5) GOTO 1. Нетрудно понять, что для вершин x,y найденных указанным образом, разрезание ребра (x,y) является оптимальным как для звезды с центром в x, так и для звезды с центром в y. Поэтому данный алгоритм дает оптимальную последовательность разрезов ребер графа.
Кстати, в примере (Primer.zip) разрезание графа по ребрам (1,3), (3,4), (1,2), (2,3) как раз и следует оптимальной стратегии. Так как после первого разреза получилось две вершины с минимальным весом (а именно, вершины 1 и 3), то в качестве x можно выбрать любую из них. В примере выбрана x=3. Если же выбрать x=1, то получится другая последовательность разрезов (которая также является оптимальной): (1,3),(1,2),(3,4),(2,3)
RElf То есть если таких вершин несколько, то неважно, какую брать? Например если взять граф 1(1)-2(1)-3(1)-4(10) - в скобках вес вершин, перед скобками номер то у нас будет выбор между 1,2 и 3. Если взять 2, то в 3) опять же будет выбор между 1 и 3. В результате возможны две неравноценные последовательности разрезов: (1-2),(2-3),(3-4) - стоимость 50 (2-3),(1-2),(3-4) - стоимость 65 Если не обсчитался, то получается, что нельзя брать произвольную минимальную вершину. Значит нужен какой-то дополнительный критерий?
Да, я не учел, что удаление ребра (x,y) изменяет также звезды, где x и/или y являются концевыми вершинами. Это влияние надо осмыслить... Но в любом случае, приведенный алгоритм можно причислить к жадным, так как на каждом ходу он делает локально-оптимальный выбор.
RElf У меня была немного другая идея: если x-y ребро, xw и yw - вес вершин x и y (всегда положительный), a - количество ребер содержащих x (кроме x-y) и b - количество ребер содержащих y (кроме x-y), то можно попытаться всегда разрезать ребро с минимальным "потенциалом" xw*b+yw*a. В случае звезды получается та же самая стратегия, что и у тебя, и для графа в примере тоже выходит оптимальная последовательность. Но все равно алгоритм как-то не сильно нравится, буду придумывать контрпример.
Спасибо за предложения алгоритмов! Я попробовал реализовать и сравнить оба предложенных варианта. Оба алгоритма работают очень быстро, но к сожалению дают не очень хорошие решения, часто одинаковые. Они не находят лучшее решение даже для маленьких графов (с числом вершин <= 5) и не дают хорошего приближения для больших графов (например, 32 вершины). Тупой случаен перебор вариантов при случайном обмене ребер в последовательности разрезания, который работает очень медленно и не дает достаточно хороших результатов, но за 10 секунд находит результат для суммы срезов, который на 1-5 порядков ниже, чем при выборе пути по определенным критериям.
