Metoda Forda-Fulkersona – algorytm służący do wyznaczania maksymalnego przepływu. Jest to algorytm bardzo ogólny, dlatego często nie jest nazywany algorytmem, a metodą. Popularną implementacją tej metody jest algorytm Edmondsa-Karpa. Algorytm można opisać następująco:
Sieć residualna jest grafem skierowanym tworzonym na podstawie sieci przepływowej i jej aktualnego przepływu. Wagi łuków w sieci residualnej oznaczają, o ile można zmienić przepływ w odpowiadającym mu łuku sieci przepływowej.
Liczba i układ łuków w sieci residualnej mogą być nieco inne, niż w sieci przepływowej. Jeśli przepływ w danym łuku sieci przepływowej jest większy od zera, to przepływ w tym łuku da się zmniejszyć – w sieci residualnej pojawi się wówczas dodatkowo łuk skierowany w przeciwną stronę, niż łuk w sieci przepływowej. Jeśli natomiast przepływ w łuku sieci przepływowej jest już maksymalny, to nie można go zwiększyć, zatem taki łuk nie będzie występował w sieci residualnej (będzie występował tylko łuk o przeciwnym zwrocie).
Ścieżka powiększająca to ścieżka w sieci residualnej prowadząca od źródła do ujścia. Najmniejsza spośród wag łuków należących do ścieżki powiekszającej jest określana jako jej przepustowość residualna. Jest to wartość, o którą można zwiększyć przepływ w sieci przepływowej.
Powiększenie przepływu w sieci o ścieżkę powiększającą można opisać następująco. Dla każdego łuku należącego do ścieżki powiększającej:
Ze względu na to, że metoda Forda-Fulkersona jest algorytmem bardzo ogólnym, złożoność obliczeniowa zależy od konkretnej implementacji. Jeśli założymy, że przepływy w łukach są liczbami naturalnymi, to możemy oszacować górne ograniczenie tej złożoności. W każdej iteracji algorytmu powiększymy przepływ o co najmniej 1, zatem liczba wykonań głównej pętli algorytmu będzie mniejsza bądź równa od maksymalnego przepływu (oznaczmy go f). W trakcie wyznaczania ścieżki powiększającej i zwiększania przepływu musimy przejrzeć w najgorszym wypadku wszystkie krawędzie (oznaczmy ich liczbę jako e). Kres górny złożoności czasowej jest zatem rzędu O(fe).
Dodano: 12 grudnia 2017 15:56, ostatnia edycja: 24 kwietnia 2020 20:19.
Algorytm Floyda-Warshalla – algorytm służący do wyznaczania najkrótszych ścieżek pomiędzy każdą parą wierzchołków w grafie. Jest to algorytm oparty na programowaniu dynamicznym. Algorytm ma złożoność czasową O(n3) i złożoność pamięciową O(n2), gdzie n jest liczbą wierzchołków.
Algorytm dopuszcza krawędzie o ujemnych wagach, o ile nie tworzą ujemnych cykli. Algorytm może być również wykorzystywany do wyszukiwania ujemnych cykli w grafie.
Metoda z zastosowaniem przepływu blokującego – algorytm wyznaczający maksymalny przepływ w sieci przepływowej. W algorytmie tym przepływ zwiększany jest iteracyjnie, w każdej iteracji wyznaczony przepływ jest powiększany o przepływ blokujący w warstwowej sieci residualnej.
Ten artykuł opisuje algorytm zachłanny rozwiązujący problem wydawania reszty. Algorytm ten polega na wybieraniu zawsze największej dostępnej monety, tzn. takiej, która nie jest większa od kwoty pozostałej do wydania.
Algorytm nie zawsze znajduje rozwiązanie optymalne. Przykładowo, dla zbioru nominałów {1, 3, 4} i kwoty 6 algorytm użyje najpierw monety o nominale 4 (pozostaje do wydania kwota 2), potem monety o nominale 1 (pozostaje kwota 1) i jeszcze raz monety o nominale 1. Łącznie algorytm użyje więc trzech monet, podczas gdy rozwiązanie optymalne wymaga użycia tylko dwóch (dwie monety o nominale 3).