Вопрос по algorithm, graph, multiway-tree – Минимальные разрушающие затраты на графике

8

Нам дан граф G (V, E) с N узлами (пронумерованными от 0 до N-1) и точно (N-1)two-way Edges.

Каждое ребро в графе имеетpositive cost C(u,v)(Крайний вес).

The entire graph is such that there is a unique path between any pair of Nodes.

Нам также дают списокL номера узла, на котором размещена бомба.

Нашей целью являетсяdamage/remove the edge из графика так, что после повреждения / удаления ребер из графа, нет никакой связи между бомбами -

то естьafter damaging, there is no path between any two bombs.

cost of damaging the Edge(u,v) = Edge weight(u,v).

Так,we have to damage those edges, such that the total damaging cost is minimum.

Пример:

Total Nodes=N=5 
Total Bomb=Size of List L=3

List L={2,4,0}//Thats is at node number 2,4 and 0 bomb is placed...

Total Edges =N-1=4 edges are::

u v Edge-Weight

2 1 8

1 0 5

2 4 5

1 3 4



In this case the answer is ::
Total Damaging cost =(Edge Weight (2,4) + Edge Weight(0,1))
           =5+5=10.

So when we remove the edge connecting node (2,4),
and the edge connecting node (0,1) ,there is no connection left 
between any pair of machines in List {2,4,0};

Note any other,combinations of edges(that  we damaged ) to achieve the
target goal ,needs more than 10 unit cost.  

enter image description here

Constraints::
N(ie. Number of Nodes) <= 100,000
ListSize |L|(ie. Number of Bombs) <= N
1 <=Edge cost(u,v) <= 1000,000

What i had done?

До сих пор я не нашел эффективного способа :(.

Далее, так как количество узловNколичество ребер точноN-1 и весь граф таков, что существует уникальный путь между любой парой узлов, я пришел к выводу, чтоthe graph is a TREE.

Я пытался изменить алгоритм Крускала, но это мне тоже не помогло.

Спасибо!

@ All :: Добавлены ограничения в качестве правки. ritesh_NITW
Если граф полностью связан, это дерево, но в противном случае это может быть нормальный граф. Saeed Amiri
Я считаю, что у жадного подхода (удаляя самую низкую вершину в каждом пути) есть шанс в дереве, но я пока не уверен в этом: \ Кроме того: Что вы найдете в качестве эффективного подхода? amit
@ amit, до сих пор я не слишком в состоянии найти какой-либо эффективный метод, чтобы решить эту проблему. Ограничение Количество узлов = 100 000, то есть общее число ребер = 100 000-1. Поэтому алгоритм O (n log n) будет удобен и эффективен. ritesh_NITW

Ваш Ответ

6   ответов
2

миальное время простым динамическим программированием. См. Чопра и Рао: " На многогранном многограннике ", Сети 21 (1): 51–89, 1991.

Хороший ответ, ИМО, лучше дать определение многогранного разреза. Saeed Amiri
cs.ust.hk / mjg_lib / Классы / COMP572_Fall06 / Notes / Tree_Multicut.ps имеет описание алгоритма. Google.com / ... VSOverFlow
4

Возьмите график G '= (V', E '), V' = V, E '= {}. Сортируйте ребра в E в порядке возрастания стоимости. Теперь, для каждого ребра в E, добавьте его в E, если он не соединяет два компонента, у которых есть вершины с бомбами в них. Результатом является сумма затрат E-E '.

РЕДАКТИРОВАТЬ

На этом пример

Первоначально, наше множество ребер пусто {}, и мы берем ребра, отсортированные в порядке возрастания [(1, 2), (0, 1), (2, 4), (1, 3)]

Итак, в начале наш график состоит из 5 отключенных компонентов.

(1, 2) имеет стоимость 8, и только один из компонентов, которые он соединяет, имеет бомбу. Итак, мы добавляем его в E '. E '= {(1, 2)} и у нас есть 4 компонента.

Следующим по величине преимуществом является (0, 1) со стоимостью 5. Но у обоих компонентов есть бомбы, поэтому не добавляйте это преимущество.

Следующее - (2, 4). Это также связано с компонентами с бомбами, поэтому мы также пропускаем это.

Наименьшее преимущество по стоимости (1, 3). Поскольку один из его компонентов (содержащий только узел 3) не имеет бомбы, мы добавляем его в E '.

Это дает нам E '= {(1,2) ,, (1, 3)}.

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

MaK, не могли бы вы привести пример. Я не думаю, что этот подход работает, так как всегда есть ОДНО соединенные компоненты, так как «весь граф таков, что существует уникальный путь между любой парой узлов». Пожалуйста, исправьте меня, если я неправильно, я думаю, что если вы сможете проиллюстрировать ваш подход, взяв в качестве примера входные данные, тогда это будет намного легче понять. ritesh_NITW
@ ritesh_nitw: я обновил свой ответ. MAK
2

Корень дерева в некоторой вершине, а затем начните с обхода снизу вверх.

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

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

Я думал так же, но не смог прийти к окончательному алгоритму, думаю, твоя идея с запоминанием поддеревьев, эквивалентных одной бомбе. unkulunkulu
1

ГрафикG это дерево. Следовательно есть только один путь между любыми двумя узлами.

Предположим, естьL Красные (Бомба) узлы и V-L Белый (не бомбовые узлы). Решение требует разбиения G на лес из L поддеревьев. Это требует удаления как минимум L-1 края.

Каждый из удаленных краев должен быть на путь между двумя красными узлами.

A. Урежьте дерево G, чтобы удалить все края, которые не участвуйте в пути между двумя красными узлами.

Удалите узлы белого листа (и край инцидента) из рассмотрения. Повторяйте # 1 до тех пор, пока в модифицированном графе не останется белых листьев.

B. После (A) все ребра, оставленные в графе, являются ребрами, которые образуют путь между двумя красными узлами.

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

С Вернитесь к шагу A для каждого из поддеревьев, созданных в B, если оно содержит более одного красного узла.

Это O (V log V) (| E | is | V | -1).

0

1) Начни с бомбы, в твоем примере я начинаю с:0 2) Создать пути со всеми соседними узлами. Поэтому возьмите все отношения и начните путь с ними. В вашем примере он будет начинаться одним путем:0 -> 1. 3) Если вы ударили другую бомбу на пути, вы удалите край с наименьшей стоимостью. В этом примере мы не попали в бомбу, поэтому мы продолжаем с шага 2. 3A) Никакой бомбы пока нет. Продолжите с шага 2 и расширьте пути новыми соседними узлами. В вашем случае будет создан новый путь:1 -> 3. И существующий будет расширен:0 -> 1 -> 2 3B) На пути обнаружена бомба. Пройдите по пути, где находится бомба, и уберите край с наименьшей стоимостью. В вашем примере путь0 -> 1 -> 2 содержит бомбу (2). Поэтому мы удалим связь со стоимостью 5. Удалите путь из «задачи» и перейдите к шагу 2 на последних достигнутых узлах (2 и 3).

В конце вы должны пройти каждый узел ровно один раз. Если я не ошибаюсь, сложность должна быть около O (n log n)

0

http: //www.cs.ust.hk/mjg_lib/Classes/COMP572_Fall06/Notes/Tree_Multicut.p

имеет описание алгоритма.

Google HTML версия постскриптум файла

=========================================

http: //dspace.mit.edu/bitstream/handle/1721.1/5394/OR-308-95.pdf последовательность = 1

Случай k = 2 не является единственным полиномиально разрешимым случаем проблемы многомерного разреза. Ловдс [12] и Черкасский [3] показывают, что когда ce = 1 Ve E E и G эйлерово, то задача о многомерном разрезе полиномиально разрешима.Erdos и Sz6kely [8] показали, что обобщение задачи многомерного разреза полиномиально разрешимо, когда базовый граф G является деревом. Dalhaus et. и др. В [7] показано, что эта задача является полиномиально разрешимой для фиксированных k на плоских графа

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

Похожие вопросы