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...
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...
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...
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...
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...