Teoretyczne informatyka greedy-algorithms

9

Optymalne algorytmy zachłanne dla problemów trudnych dla NP

Chciwość z braku lepszego słowa jest dobra. Jednym z pierwszych paradygmatów algorytmicznych nauczanym na kursie algorytmów wprowadzających jest podejście zachłanne . Chciwe podejście skutkuje prostymi i intuicyjnymi algorytmami dla wielu problemów w P. Co ciekawe, dla niektórych problemów trudnych dla NP oczywisty i naturalny chciwy / lokalny algorytm skutkuje (możliwym) …

38 cc.complexity-theory lower-bounds approximation-algorithms greedy-algorithms approximation-hardness

2

Algorytm Max-Cut, który nie powinien działać, nie wiadomo dlaczego

OK, może się to wydawać pytaniem o pracę domową iw pewnym sensie tak jest. Jako zadanie domowe w klasie algorytmów licencjackich podałem następujący klasyk: Biorąc pod uwagę nieukierowany wykres , podaj algorytm, który znajdzie cięcie taki sposób, że , gdzie to liczba krawędzi przecinających cięcie. Złożoność czasowa musi wynosić .G=(V,E)G=(V,E)G=(V,E)(S,S¯)(S,S¯)(S,\bar{S})δ(S,S¯)≥|E|/2δ(S,S¯)≥|E|/2\delta(S,\bar{S})\geq …

21 graph-algorithms max-cut greedy-algorithms

1

Dlaczego Chciwa Hipoteza jest tak trudna?

Niedawno dowiedziałem się o chciwych przypuszczeniach dotyczących najkrótszego problemu superstrun . W tym problemie otrzymujemy zestaw ciągów s1, … , Sns1,…,sns_1,\dots, s_n i chcemy znaleźć najkrótszy superstrun sss tj. Taki, aby każdy sjasis_i pojawiał się jako podciąg sss . Problem ten jest trudny do przeprowadzenia w NP i po długiej …

14 reference-request approximation-algorithms greedy-algorithms

1

Jaki algorytm zachłanny spełnia właściwość zachłannego wyboru, ale nie ma optymalnej podbudowy?

Na podstawie podręcznika Wprowadzenie do algorytmów poprawność zachłannego algorytmu wymaga problemu z dwiema właściwościami: chciwy wybór nieruchomości optymalna podkonstrukcja Łatwo jest wymyślić przeciwne przykłady, dla których chciwe rozwiązanie zawodzi z powodu braku właściwości chciwego wyboru, np. Problem plecaka 0/1. Ale trudno mi sobie wyobrazić inną możliwość. Czy ktoś może mi …

14 greedy-algorithms

3

Czy każdy zachłanny algorytm ma strukturę matroidu?

Jest dobrze znane, że dla każdego matroid M.MM żadna funkcja ciężaru www , nie wychodzi algorytm GreedyBasis (M, w )GreedyBasis(M,w)\mbox{GreedyBasis}(M,w) , która zwraca na podstawę maksymalny ciężar MMM . Czy zatem odwrotny kierunek jest również prawdą? Oznacza to, że jeśli istnieje jakiś chciwy algorytm, musi również istnieć pewna struktura matroidu.

13 ds.algorithms greedy-algorithms

3

Czy można udowodnić, że dla danego problemu nie istnieją optymalne algorytmy zachłanne?

Chciwość jest terminem nieformalnym, ale może być (nie jestem pewien, dlatego pytam), że w przypadku niektórych problemów chciwość może być sformułowana matematycznie, a zatem można udowodnić, że nie istnieje optymalny algorytm chciwości. czy to możliwe?

10 ds.algorithms greedy-algorithms

Pytania otagowane jako greedy-algorithms