Minimalne ważone pokrycie krawędzi - czy chciwy algorytm nie jest optymalny?

Nov 27 2020

Post tutaj: Rozwiązanie minimalnego pokrycia krawędzi przy użyciu algorytmu maksymalnego dopasowania zapewnia sposób na uzyskanie minimalnego pokrycia krawędzi z maksymalnego dopasowania przez zachłanne dodawanie krawędzi na szczycie maksymalnego dopasowania, aż wszystkie wierzchołki zostaną pokryte. Teraz, biorąc pod uwagę problem z minimalną wagą pokrycia krawędzi, wydaje się, że to podejście można rozszerzyć. Najpierw znajdź minimalne ważone dopasowanie z maksymalnymi krawędziami , a następnie zachłannie dodaj krawędzie o najmniejszej wadze, najpierw o najmniejszej wadze.

Jednak czytając rozdział 19.3 książki „Optymalizacja kombinatoryczna: wielościany i efektywność” Schrijvera, przedstawiono bardziej skomplikowany algorytm. To sprawia, że ​​wydaje mi się, że moje podejście powyżej jest nieoptymalne. Czy można znaleźć kontrprzykład, najlepiej na wykresie dwuczęściowym, gdzie mój chciwy algorytm nie zapewni optymalnego rozwiązania? Nie udało mi się znaleźć takiego z kilkoma wykresami zabawek.

Odpowiedzi

1 j_random_hacker Nov 28 2020 at 04:01

Oto kontrprzykład do proponowanego algorytmu:

Optymalne rozwiązanie składa się z 3 krawędzi i kosztuje 3 + 1 + 1 = 5, ale dopasowanie minimalnego kosztu maksymalnej liczności, które składa się z 2 krawędzi i kosztuje 3 + 3 = 6, zostanie wybrane w pierwszym kroku algorytmu i natychmiast zwrócony, ponieważ jest to już rozwiązanie. (Jedyne inne dopasowanie maksymalnej liczności kosztuje 1 + 6 = 7).