PHP 7. Algorytmy i struktury danych
−25%44,25 zł
Jak się nie pomylić, czyli potęga matematycznego myślenia
−30%27,93 zł
Programowanie w języku C. Ćwiczenia praktyczne. Wydanie II
−25%14,92 zł
Algorytmy. Ilustrowany przewodnik
−25%41,17 zł
ASP.NET Core MVC 2. Zaawansowane programowanie. Wydanie VII
129,00 zł
JavaScript i jQuery. Interaktywne strony WWW dla każdego
−25%74,25 zł

Kategoria: Algorytmy

Podkategorie:

Zobacz też

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:

  1. Wyznacz sieć residualną (opis sieci residualnej znajduje się w dalszej części artykułu).
  2. Znajdź w sieci residualnej dowolną ścieżkę powiększającą.
  3. Jeśli nie udało się wyznaczyć żadnej ścieżki powiększającej, zakończ działanie algorytmu.
  4. W przeciwnym razie zwiększ przepływ w sieci (w sposób opisany w dalszej części artukułu) i wróć do punktu 1.
→ Czytaj całość

Wyznaczanie maksymalnego przepływu – problem obliczeniowy polegający na wyznaczeniu maksymalnego przepływu w sieci przepływowej.

Sieć przepływowa jest skierowanym grafem prostym. Każdy łuk (krawędź skierowana w grafie) ma swoją nieujemną wagę, która oznacza maksymalny dopuszczalny przepływ w tym łuku. Na potrzeby tego artykułu nazwijmy rzeczy przepływające przez sieć danymi. Jeden z wierzchołków sieci jest źródłem, z którego wypływają przesyłane dane. Inny z wierzchołków to ujście, do którego te dane wpływają. Zakłada się ponadto, że dla każdego z pozostałych wierzchołków istnieje ścieżka ze źródła do ujścia przechodząca przez ten wierzchołek.

Przepływem w sieci nazywamy przyporządkowanie każdemu łukowi pewnej wartości, która oznacza liczbę danych aktualnie przesyłanych przez ten łuk. Wartości te muszą spełniać następujące warunki:

  • Wartość przyporządkowana krawędzi musi być mniejsza lub równa jej wadze (warunek przepustowości).
  • Do każdego wierzchołka (poza źródłem i ujściem) musi wpływać tyle samo danych, ile z niego wypływa (warunek zachowania przepływu).

Omawiany problem polega na dobraniu takiego przepływu, aby liczba danych wypływających ze źródła (i zarazem wpływających do ujścia) była jak największa.

→ Czytaj całość

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.

→ Czytaj całość
Polityka prywatnościKontakt