Strona główna

Algorytmy dla problemów np-zupełnych


Pobieranie 4.41 Kb.
Data19.06.2016
Rozmiar4.41 Kb.
Program przedmiotu:

ALGORYTMY DLA PROBLEMÓW NP-ZUPEŁNYCH
15 godz. wykładów + 15 godz. ćwiczeń

Wymagane wiadomości: znajomość języka C/C++, podstawowe pojęcia kombinatoryki i teorii grafów, podstawowe metody projektowania algorytmów.

1. Algorytmy dokładne dla rozwiązania problemów NP–zupełnych. Przeszukiwanie wyczerpujące. Algorytm z nawrotami dla problemu plecakowego i cyklu Hamiltona w grafie. Drzewo przeszukiwań algorytmu z nawrotami. Algorytm z nawrotami z odcinaniem gałęzi dla problemu plecakowego.
2. Algorytmy z nawrotami z funkcją ograniczającą dla problemu plecakowego. Metoda podziału i ograniczeń dla problemu komiwojażera z funkcją ograniczającą opartą na wartości zredukowanej macierzy odległości.

3. Algorytmy aproksymacyjne dla problemów NP – zupełnych. Definicja algorytmu -optymalnego. Nieaproksymowalność ogólnego problemu komiwojażera TSP. Algorytm aproksymacyjny dla metrycznego problemu drzewa Steinera z wykorzystaniem minimalnego drzewa rozpinającego.


4. Algorytmy aproksymacyjne oparte na metodzie lokalnego ulepszania dla problemu maksymalnego przekroju w grafie i dla problemu komiwojażera.
5. Schematy aproksymacyjne, wielomianowe schematy aproksymacyjne i w pełni wielomianowe schematy aproksymacyjne. W pełni wielomianowy schemat aproksymacyjny dla problemu plecakowego. Związek między silną NP – zupełnością a istnieniem w pełni wielomianowego schematu aproksymacyjnego.

6. Algorytmy heurystyczne. Algorytmy oparte na metodzie symulowanego wyżarzania i na metodzie poszukiwania z tabu dla problemu plecakowego.


7. Algorytmy genetyczne. Algorytm genetyczny dla problemu plecakowego i dla problemu komiwojażera.

Literatura:



V. V. Vazirani, Algorytmy aproksymacyjne.

D. L. Kreher, D. R. Stinson, Combinatorial Algorithms.


©snauka.pl 2016
wyślij wiadomość