Najlepsza odpowiedź
Klasyfikacja według celu
Każdy algorytm ma określony cel, na przykład celem algorytmu szybkiego sortowania jest sortowanie danych w kolejności rosnącej lub malejącej. Ale liczba celów jest nieskończona i musimy pogrupować je według rodzaju celów.
Klasyfikacja według implementacji
Algorytm może być implementowany zgodnie z różnymi podstawowymi zasadami.
- Rekursywny lub iteracyjny Algorytm rekurencyjny to taki, który wywołuje siebie wielokrotnie, aż do spełnienia określonego warunku. Jest to metoda wspólna dla programowania funkcjonalnego. Algorytmy iteracyjne używają konstrukcji powtarzalnych, takich jak pętle. Niektóre problemy lepiej pasują do jednej lub drugiej implementacji. Na przykład problem wież Hanoi jest dobrze rozumiany w rekurencyjnej implementacji. Każda wersja rekurencyjna ma iteracyjny odpowiednik iteracyjny i odwrotnie.
- Logiczne lub proceduralny Algorytm można postrzegać jako kontrolowaną dedukcję logiczną. Składnik logiczny wyraża aksjomaty, które mogą być użyte w obliczeniach, a element sterujący określa sposób, w jaki dedukcja jest stosowana do aksjomatów. To jest podstawa programowania logicznego. W językach programowania czystej logiki komponent sterujący jest ustalony, a algorytmy są określane przez dostarczenie tylko komponentu logicznego.
- Serial lub równolegle Algorytmy są zwykle omawiane przy założeniu, że komputery wykonują w danym momencie jedną instrukcję algorytmu. Jest to algorytm szeregowy, w przeciwieństwie do algorytmów równoległych, które wykorzystują architekturę komputera do przetwarzania kilku instrukcji jednocześnie. Dzielą problem na podproblemy i przekazują je kilku procesorom. Algorytmy iteracyjne są generalnie równoległe. Algorytmy sortowania mogą być efektywnie zrównoleglane.
- deterministyczne lub niedeterministyczne Deterministyczne algorytmy rozwiązują problem za pomocą predefiniowanego procesu, podczas gdy algorytm niedeterministyczny musi na każdym kroku odgadnąć najlepsze rozwiązanie przy użyciu heurystyki.
Klasyfikacja według paradygmatu projektu
Paradygmat projektowania to dziedzina badań lub klasa problemów, która wymaga specjalnego rodzaju algorytmu:
- Dziel i rządź Algorytm dziel i zwyciężaj wielokrotnie redukuje wystąpienie problemu do jednego lub więcej mniejszych wystąpień tego samego problemu (zwykle rekurencyjnie), aż wystąpienia będą wystarczająco małe łatwo rozwiązać. Jednym z przykładów dziel i rządź jest sortowanie przez scalanie. Sortowanie można przeprowadzić na każdym segmencie danych po podzieleniu danych na segmenty, a sortowanie całych danych można uzyskać w fazie podboju poprzez ich scalenie. Algorytm wyszukiwania binarnego jest przykładem wariantu dzielenia i zwyciężania o nazwie algorytm zmniejszania i zwyciężania , który rozwiązuje identyczny podproblem i wykorzystuje rozwiązanie tego podproblemu do rozwiązania większy problem.
- Programowanie dynamiczne Najkrótszą ścieżkę na wykresie ważonym można znaleźć, używając najkrótszej ścieżki do celu ze wszystkich sąsiadujących wierzchołki. Kiedy optymalne rozwiązanie problemu można skonstruować z optymalnych rozwiązań do podproblemów, użycie programowania dynamicznego pozwala uniknąć ponownego obliczania rozwiązań, które zostały już obliczone. – Główna różnica w podejściu „dziel i rządź” polega na tym, że podproblemy są niezależne w przypadku dziel i zwyciężaj, podczas gdy nakładanie się podproblemów występuje w programowaniu dynamicznym. – Dynamiczne programowanie i zapamiętywanie idą w parze. Różnica w stosunku do prostej rekurencji polega na buforowaniu lub zapamiętywaniu wywołań rekurencyjnych. Tam, gdzie podproblemy są niezależne, jest to bezużyteczne. Dzięki zapamiętywaniu lub utrzymywaniu tabeli podproblemów już rozwiązanych, programowanie dynamiczne redukuje wykładniczy charakter wielu problemów do złożoności wielomianowej.
- Metoda zachłanna Zachłanny algorytm jest podobny do algorytmu programowania dynamicznego, z tą różnicą, że rozwiązania podproblemów nie muszą być znane na każdym etapie. Zamiast tego można dokonać „chciwego” wyboru tego, co w danej chwili wygląda na najlepsze rozwiązanie. Najpopularniejszym zachłannym algorytmem jest znajdowanie minimalnego drzewa rozpinającego podanego przez Kruskala.
- Programowanie liniowe Problem jest wyrażony jako zbiór liniowych nierówności, a następnie podejmuje się próbę maksymalizacji lub minimalizacji nakładów. Może to rozwiązać wiele problemów, takich jak maksymalny przepływ dla grafów skierowanych, w szczególności przy użyciu algorytmu simplex.Złożony wariant programowania liniowego nazywany jest programowaniem całkowitoliczbowym, w którym przestrzeń rozwiązań jest ograniczona do wszystkich liczb całkowitych.
- Redukcja zwana także przekształcaj i podbijaj Rozwiąż problem, przekształcając go w inny problem. Prosty przykład: znalezienie mediany na nieposortowanej liście polega najpierw na przetłumaczeniu tego problemu na problem sortowania i znalezienie środkowego elementu na posortowanej liście. Głównym celem redukcji jest znalezienie możliwie najprostszej transformacji.
- Korzystanie z wykresów Wiele problemów, takich jak gra w szachy, można modelować jako problemy na wykresach. Stosowane są algorytmy eksploracji wykresów. Ta kategoria obejmuje również algorytmy wyszukiwania i cofanie.
- Paradygmat probabilistyczny i heurystyczny Probabilistyczne Te, które dokonują niektórych wyborów losowo. Genetyka Próba znalezienia rozwiązań problemów poprzez naśladowanie biologicznych procesów ewolucyjnych, z cyklem losowych mutacji prowadzących do kolejnych generacji „rozwiązań”. W ten sposób naśladują rozmnażanie i „przetrwanie najlepiej przystosowanych”. Heurystyka , których głównym celem nie jest znalezienie optymalnego rozwiązania, ale przybliżone rozwiązanie, w którym czas lub zasoby na znalezienie idealnego rozwiązania nie są praktyczne.
Klasyfikacja według złożoności
Niektóre algorytmy działają w czasie liniowym, a inne w czasie wykładniczym oraz niektóre nigdy się nie kończą.
Źródło: Klasyfikacja algorytmów
Uczenie nadzorowane: klasyfikacja
Odpowiedź
Poniżej przedstawiono inny sposób klasyfikowania algorytmów.
W programowaniu konkurencyjnym istnieją 4 główne problemy: rozwiązywanie paradygmatów.
Innymi słowy, biorąc pod uwagę problem, oto różne podejścia / narzędzia, które należy zastosować, aby go rozwiązać.
- Brute Force / Complete Search: metoda, która sprawdza wszystkie możliwości i wybiera najlepsze rozwiązanie.
- Zalety: proste, zawsze należy znaleźć rozwiązanie, ponieważ patrzysz na każdą możliwość
- Wady : niewykonalne, ponieważ liczba możliwości rośnie wykładniczo wraz ze wzrostem liczby elementów
- Dziel i rządź: Metoda, która dzieli problem na mniejsze części, a następnie je rozwiązuje Części. Pomyśl o wyszukiwaniu binarnym.
- Chciwe podejście: metoda, która wybiera najlepszą opcję w danym momencie, bez uwzględnienia przyszłości.
- Zalety: szybko, łatwo, może uzyskać najlepsze rozwiązanie lub być blisko
- Wady: w większości przypadków nie uzyskamy najlepszego rozwiązania
- Programowanie dynamiczne: Metoda, która tworzy rozwiązanie przy użyciu wcześniej znalezionych rozwiązań podrzędnych. Zdecydowanie jedna z bardziej zaawansowanych technik, ale niezwykle potężna i przydatna.
- Zalety: znajduje optymalne rozwiązanie wielu problemów w czasie wielomianowym ( podczas gdy brutalna siła wymagałaby wykładniczej siły)
- Wady : trudne do uchwycenia i zastosowania, zrozumienie różnych stanów i ich nawrotów wymaga czasu
Źródła
Halim, Steven i Felix Halim. Programowanie konkurencyjne: nowa niższa granica konkursów programistycznych . Lulu, 2013.