Algorytm równoległy - techniki projektowania

Wybór odpowiedniej techniki projektowania algorytmu równoległego jest najtrudniejszym i najważniejszym zadaniem. Większość problemów związanych z programowaniem równoległym może mieć więcej niż jedno rozwiązanie. W tym rozdziale omówimy następujące techniki projektowania algorytmów równoległych -

• Dziel i rządź
• Chciwa metoda
• Programowanie dynamiczne
• Backtracking
• Branch & Bound
• Programowanie liniowe

Metoda dziel i zwyciężaj

W podejściu dziel i rządź problem jest podzielony na kilka małych podproblemów. Następnie podproblemy są rozwiązywane rekurencyjnie i łączone w celu uzyskania rozwiązania pierwotnego problemu.

Podejście „dziel i rządź” obejmuje następujące kroki na każdym poziomie:

• Divide - Pierwotny problem jest podzielony na podproblemy.

• Conquer - Podproblemy są rozwiązywane rekurencyjnie.

• Combine - Rozwiązania podproblemów są łączone razem, aby uzyskać rozwiązanie pierwotnego problemu.

Podejście dziel i zwyciężaj jest stosowane w następujących algorytmach -

• Wyszukiwanie binarne
• Szybkie sortowanie
• Sortuj przez scalanie
• Mnożenie liczb całkowitych
• Odwrócenie macierzy
• Mnożenie macierzy

Chciwa metoda

W chciwym algorytmie optymalizacji rozwiązania w dowolnym momencie wybierane jest najlepsze rozwiązanie. Chciwy algorytm jest bardzo łatwy do zastosowania do złożonych problemów. Decyduje, który krok zapewni najdokładniejsze rozwiązanie w następnym kroku.

Ten algorytm to tzw greedyponieważ po zapewnieniu optymalnego rozwiązania dla mniejszej instancji algorytm nie bierze pod uwagę całego programu jako całości. Po rozważeniu rozwiązania zachłanny algorytm nigdy więcej nie bierze pod uwagę tego samego rozwiązania.

Chciwy algorytm działa rekurencyjnie, tworząc grupę obiektów z najmniejszych możliwych części składowych. Rekurencja to procedura rozwiązywania problemu, w której rozwiązanie konkretnego problemu zależy od rozwiązania mniejszej instancji tego problemu.

Programowanie dynamiczne

Programowanie dynamiczne to technika optymalizacji, która dzieli problem na mniejsze podproblemy, a po rozwiązaniu każdego podproblem programowanie dynamiczne łączy wszystkie rozwiązania, aby uzyskać ostateczne rozwiązanie. W przeciwieństwie do metody dziel i rządź, programowanie dynamiczne wielokrotnie wykorzystuje rozwiązania podproblemów.

Algorytm rekurencyjny dla szeregu Fibonacciego jest przykładem programowania dynamicznego.

Algorytm cofania

Wycofywanie się to technika optymalizacji służąca do rozwiązywania problemów kombinacyjnych. Jest stosowany zarówno do problemów programowych, jak i rzeczywistych. Problem z ósemką, łamigłówka Sudoku i przejście przez labirynt to popularne przykłady wykorzystania algorytmu cofania.

W przypadku cofania zaczynamy od możliwego rozwiązania, które spełnia wszystkie wymagane warunki. Następnie przechodzimy do następnego poziomu i jeśli ten poziom nie daje satysfakcjonującego rozwiązania, cofamy się o jeden poziom i zaczynamy od nowej opcji.

Rozgałęzienie i związane

Algorytm rozgałęziony i powiązany to technika optymalizacji mająca na celu uzyskanie optymalnego rozwiązania problemu. Wyszukuje najlepsze rozwiązanie dla danego problemu w całej przestrzeni rozwiązania. Granice funkcji, która ma być zoptymalizowana, są łączone z wartością najnowszego najlepszego rozwiązania. Pozwala to algorytmowi na całkowite znalezienie części przestrzeni rozwiązania.

Celem wyszukiwania gałęzi i powiązanego jest utrzymanie najtańszej ścieżki do celu. Po znalezieniu rozwiązania można je ulepszać. Wyszukiwanie rozgałęzione i powiązane jest implementowane w wyszukiwaniu ograniczonym w głąb i przeszukiwaniu w głąb.

Programowanie liniowe

Programowanie liniowe opisuje szeroką klasę zadań optymalizacyjnych, w których zarówno kryterium optymalizacji, jak i ograniczenia są funkcjami liniowymi. Jest to technika pozwalająca uzyskać najlepszy wynik, taki jak maksymalny zysk, najkrótsza droga lub najniższy koszt.

W tym programowaniu mamy zbiór zmiennych i musimy przypisać im wartości bezwzględne, aby spełnić zestaw równań liniowych i zmaksymalizować lub zminimalizować daną liniową funkcję celu.