Ocena brak

Na czym polega idea konstruowania algorytmów przybliżonych?

Autor /Barnim7777 Dodano /29.12.2011

Główna idea konstruowania takich algorytmów bazuje na założeniu, że w wielu przypadkach wynik gorszy od optymalnego jest i tak lepszy od całkowitego braku rozwiązania dla danego zadania. Takie „zastępcze” algorytmy noszą nazwę algorytmów aproksymacyjnych.

Przykład:

Problem komiwojażera jest problemem trudno-rozwiązywalnym (NP – zupełnym), ale można w czasie wielomianowym wyznaczyć całkiem niezłe jego przybliżenie, obchodzące wszystkie wierzchołki grafu.

Miarą dobroci takiego rozwiązania jest współczynnik Sa = otrzymany wynik / najlepsze rozwiązanie.

W przypadku rozwiązania zastępczego dla problemu komiwojażera Sa<1,5, a złożoność czasowa tego rozwiązania wynosi zaledwie O(N3).

Do góry