Pytania otagowane jako simplex

6
Złożoność algorytmu simpleks
Jaka jest górna granica algorytmu simpleks dla znalezienia rozwiązania dla programu liniowego? Jak mam znaleźć dowód na taką sprawę? Wydaje się, że najgorszym przypadkiem jest konieczność odwiedzenia każdego wierzchołka, czyli . Jednak w praktyce algorytm simpleks będzie działał znacznie szybciej niż w przypadku bardziej standardowych problemów.O ( 2n)O(2n)O(2^n) Jak mogę …
3
Konsekwencje istnienia silnie wielomianowego algorytmu programowania liniowego?
Jednym ze świętych graali projektowania algorytmów jest znalezienie silnie wielomianowego algorytmu programowania liniowego, tj. Algorytmu, którego czas działania jest ograniczony wielomianem w liczbie zmiennych i ograniczeń i jest niezależny od wielkości reprezentacji parametrów (przy założeniu arytmetyka kosztów jednostkowych). Czy rozwiązanie tego pytania miałoby implikacje poza lepszymi algorytmami programowania liniowego? Na …
1
Struktura instancji patologicznych dla algorytmów simpleks
O ile rozumiem, wszyscy znają deterministyczne reguły przestawne dla algorytmów simpleksowych mają określone dane wejściowe, na których algorytm wymaga czasu wykładniczego (lub przynajmniej nie wielomianowego), aby znaleźć optymalne. Nazwijmy te przypadki „patologicznymi”, ponieważ zwykle (tj. Na większości danych wejściowych) algorytm simpleks kończy się szybko. Pamiętam z mojego kursu programowania matematycznego, …
5
Najlepsza książka na temat implementacji metody Simplex?
Interesuje mnie implementacja SM dla zadania LP, jednak słyszałem o możliwych pułapkach: książka Cormena mówi, że możliwe jest posiadanie danych wejściowych, które sprawią, że naiwna implementacja zachowa się w wykładniczym czasie. Słyszałem również, że naiwna implementacja może zapętlać dane. Czy istnieje książka / artykuł / źródło wyjaśniające niuanse praktycznego wdrażania …
2
Uzasadnienie metody węgierskiej (Kuhn-Munkres)
Napisałem implementację algorytmu Kuhna-Munkresa dla problemu dwustronnego idealnego dopasowania minimalnej wagi w oparciu o notatki z wykładu, które znalazłem tu i tam w Internecie. Działa naprawdę dobrze, nawet na tysiącach wierzchołków. I zgadzam się, że teoria jest naprawdę piękna. A jednak wciąż zastanawiam się, dlaczego musiałem tak bardzo się starać. …
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.