Корректен ли этот алгоритм поиска максимального независимого множества в графе?

У нас есть следующие входные данные для алгоритма:

Граф G без циклов (также известный как остовное дерево), где каждый узел имеет соответствующий вес.

Я хочу найти независимый набор S такой, что:

  • Никакие два элемента в S не образуют ребро в G
  • Не существует другого возможного подмножества, удовлетворяющего приведенному выше условию, для которого существует больший вес, чем S[0] + S[1] + ... + S[n-1] (где len(S)==n).

Это псевдокод высокого уровня, который у меня есть до сих пор:

MaxWeightNodes(SpanningTree S):
    output = {0}
    While(length(S)):
        o = max(node in S)
        output = output (union) o
        S = S \ (o + adjacentNodes(o))
    End While
    Return output

Может ли кто-нибудь сказать мне сразу, сделал ли я какие-либо ошибки, или этот алгоритм даст мне результат, который я хочу?


set graph algorithm subset pseudocode
person Govind Parmar    schedule 25.03.2013    source источник
comment
почему бы не попробовать реализовать его, чтобы доказать правильность вашего алгоритма?   -  person TravellingGeek    schedule 25.03.2013
comment
@GeraldSv По мере роста проблем обычно лучшим решением является доказательство работы алгоритма до какой-либо реализации. Потратить недели/месяцы на реализацию чего-то, чтобы выяснить, что можно было выявить простой угловой случай, это очень огорчает - у меня не так много времени, но я уже сталкивался с проблемой такого рода ( :   -  person Rubens    schedule 25.03.2013
comment
@GeraldSv Вы не реализуете алгоритмы, чтобы доказать их правильность, вы делаете это формально. Предложение иного не кажется мне хорошим советом.   -  person G. Bach    schedule 25.03.2013

Ответы (2)


arrow_upward
5
arrow_downward

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

Например, output = []:

        10
      /    \
   100      20
   /  \    /  \
  80  90  10   30

output = [100]:

         x
      /    \
     x      20
   /  \    /  \
  x    x  10   30

output = [100, 30]:

         x
      /    \
     x      x
   /  \    /  \
  x    x  10   x

output = [100, 30, 10]:

         x
      /    \
     x      x
   /  \    /  \
  x    x  x    x

Хотя мы знаем, что есть лучшие решения.

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

person Rubens    schedule 25.03.2013

arrow_upward
2
arrow_downward

Я думаю, что веса вершин затрудняют жадные решения. Если все веса равны, вы можете попробовать выбрать набор уровней дерева (что, очевидно, проще всего с полным k-арным деревом, но остовные деревья обычно не попадают в этот класс). Может быть, для жадного приближения будет полезно думать об уровнях как об общем весе, поскольку вы всегда можете выбрать все вершины одного и того же уровня дерева (независимо от того, в какой вершине вы его укореняете), чтобы перейти в одну и ту же независимую вершину. установлен; не может быть ребра между двумя вершинами одного уровня. Я не предлагаю решения, потому что это кажется мне сложной проблемой. Основными проблемами, по-видимому, являются веса и тот факт, что вы не можете предположить, что имеете дело с полными деревьями.

РЕДАКТИРОВАТЬ: на самом деле всегда выбирать все вершины одного уровня тоже кажется плохой идеей, как помогает пример Рубенса; представьте, что вершина на втором уровне справа от его дерева имела вес 200.

person G. Bach    schedule 25.03.2013