Правилен ли е този алгоритъм за намиране на максимално независимо множество в графика?

Имаме следния вход за алгоритъма:

Графика G без цикли (известна още като spanning-tree), където всеки възел има свързано тегло.

Искам да намеря независим набор 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-ary дърво, но обхващащите дървета обикновено не попадат в този клас). Може би ще бъде полезно за алчно приближение да мислим за нивата като с комбинирано тегло, тъй като винаги можете да изберете всички върхове на едно и също ниво на дървото (независимо от това в кой връх го коренувате), за да отидете в същия независим комплект; не може да има ребро между два върха от едно и също ниво. Не предлагам решение, защото това ми се струва труден проблем. Основните проблеми изглежда са тежестите и фактът, че не можете да приемете, че имате работа с цели дървета.

РЕДАКТИРАНЕ: всъщност винаги избирането на всички върхове на едно ниво също изглежда лоша идея, както примерът на Рубенс помага да се визуализира; представете си, че върхът на второто ниво отдясно на неговото дърво има тегло 200.

person G. Bach    schedule 25.03.2013