Encyklopedia Algorytmów
O stronie
Encyklopedia algorytmów to strona internetowa opisująca wybrane zagadnienia z dziedziny algorytmiki. Jest ona kierowana do osób interesujących się algorytmiką, np. do studentów informatyki. Strona ma przedstawiać omawiane zagadnienia w sposób jak najbardziej przystępny, a jednocześnie możliwie fachowy. Oprócz typowych artykułów strona zawiera też samouczki (tutoriale), które przedstawiają wybrane algorytmy na przykładach, krok po kroku.
Zawartość
Najnowsze artykuły
Najnowsze samouczki
- Symulowane wyżarzanie
- Quicksort
- Algorytm Floyda-Warshalla
- Problem komiwojażera, algorytm genetyczny
- Algorytm Dijkstry
Aby przeglądać strony tematycznie, przejdź do głównej kategorii.
Czy wiesz…
- …które algorytmy wykorzystuje algorytm Johnsona?
- …czym jest sieć residualna, wykorzystywana m.in. w metodzie Forda-Fulkersona?
- …jaką złożoność czasową ma algorytm Helda-Karpa?
- …kiedy występuje przypadek pesymistyczny w sortowaniu szybkim?
- …czym się różnią trasa, ścieżka i droga w grafie?
- …jak rozwiązać problem wydawania reszty wykorzystując programowanie dynamiczne?
- …który algorytm sortujący jest uznawany za najgorszy z możliwych?
- …na czym polega algorytm memetyczny?
- …jak działa powtarzalny algorytm najbliższego sąsiada?
- …jak zbudować minimalne drzewo rozpinające?
Polecany artykuł
Algorytm najmniejszej krawędzi – algorytm służący do rozwiązywania problemu komiwojażera. Jest to algorytm wykorzystujący strategię zachłanną, jednak w inny sposób, niż algorytm najbliższego sąsiada. W anglojęzycznej literaturze algorytm jest najczęściej określany po prostu jako greedy algorithm (algorytm zachłanny), w skrócie GR.
Algorytm działa podobnie do algorytmu Kruskala poszukującego minimalnego drzewa rozpinającego. Polega on na kolejnym dołączaniu do rozwiązania najkrótszych spośród dopuszczalnych krawędzi.
Przykładowe wykonanie algorytmu najmniejszej krawędzi
Zobacz też
Problem komiwojażera (ang. travelling salesman problem, w skrócie TSP) – problem obliczeniowy polegający na poszukiwaniu w grafie takiego cyklu, który zawiera wszystkie wierzchołki (każdy dokładnie raz) i ma jak najmniejszy koszt. Bardziej formalnie, problem komiwojażera polega na poszukiwaniu w grafie cyklu Hammiltona o najmniejszej wadze.
Problem ma liczne zastosowania w życiu codziennym. Najlepszym przykładem jest praca kuriera, który musi wyjechać z magazynu, zawieźć przesyłki w różne miejsca i wrócić do magazynu.
Nie jest znany efektywny (tj. działający w czasie co najwyżej wielomianowym) algorytm dający gwarancję znalezienia optymalnego rozwiązania problemu komiwojażera. Problem ten jest bowiem zaliczany do klasy problemów NP-trudnych. W wersji decyzyjnej (czy istnieje cykl o długości mniejszej od x) problem jest zaliczany do klasy problemów NP-zupełnych. W grafie pełnym mającym n wierzchołków liczba możliwych cykli Hammiltona wynosi aż (n-1)!/2. W praktyce sprawdzenie wszystkich możliwości jest zatem wykonalne tylko dla niewielkiej liczby wierzchołków.
Ten artykuł opisuje pewną modyfikację algorytmu opartego na programowaniu dynamicznym rozwiązującego problem wydawania reszty. Algorytm ten daje gwarancję znalezienia rozwiązania optymalnego. Algorytm zaproponował J.W. Wright w pracy The Change-Making Problem (link w bibliografii).