Dowód poprawności algorytmu zachłannego dla minimalnego pokrycia wierzchołka drzewa


14

Istnieje chciwy algorytm znajdowania minimalnego pokrycia wierzchołka drzewa, które korzysta z przejścia DFS.

  1. Dla każdego liścia drzewa wybierz jego element nadrzędny (tzn. Jego element nadrzędny znajduje się w minimalnej osłonie wierzchołków).
  2. Dla każdego węzła wewnętrznego:
    jeśli nie zostanie wybrane żadne z jego elementów podrzędnych, wybierz ten węzeł.

Jak udowodnić, że ta chciwa strategia daje optymalną odpowiedź? Czy nie ma pokrywy wierzchołków mniejszej niż ta, którą wytwarza powyższy algorytm?


Nie sądzę, aby logika drugiego kroku była poprawna. Jeśli weźmiesz pod uwagę zdegenerowane drzewo z 6 węzłami idącymi w dół do końca w prawo (oznacz je jako 1-6 odpowiadające ich głębokości). Następnie pierwszy krok algorytmu wybierze węzeł 5. Drugi krok prawdopodobnie wybierze pierwszy węzeł (root), a następnie drugi węzeł (child) LUB trzeci węzeł. Jest to jednak niepoprawne, ponieważ chcesz wybrać tylko węzeł 2 i 5, aby uzyskać prawidłowe rozwiązanie.
miguel.martin

@ miguel.martin Jeśli osłona wierzchołków zawiera tylko wierzchołki o numerach 2 i 5, krawędź między węzłami 3 i 4 nie zostanie pokryta.
Laschet Jain

Odpowiedzi:



Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.