Wiele problemów optymalizacyjnych to problemy NP-zupełne. Wiele z nich to problemy o istotnym praktycznym znaczeniu. Jak mamy więc postępować z zagadnieniem, o którym wiadomo, że jest NP-trudne, a jednak jego rozwiązanie jest dla nas niezbędne? Czy jest sposób rozwiązania takiego problemu, mimo wszystko?

Rozważmy problem komiwojażera. Skoro znalezienie najkrótszej drogi przechodzącej przez wszystkie miasta jest właściwie niemożliwe, bo problem jest NP-trudny, wydaje się być rozsądnym rozważyć ew. algorytmy znajdujące "prawie najkrótszą" drogę komiwojażera. Jeśli zrezygnujemy z wymagania, by szukana droga była najkrótsza, to okazuje się, że możemy zastosować np. algorytm Kruskala, do skonstruowania minimalnego drzewa rozpinającego, i na tej podstawie utworzyć co najwyżej dwukrotnie tak długą drogą komiwojażera, jak droga najkrótsza. Czasami takie rozwiązanie jest lepsze niż żadne!

Klasa algorytmów pozwalających rozwiązać trudne problemy optymalizacyjne, w sposób, który nie daje rozwiązania optymalnego, ale jednak rozwiązanie bliskie optymalnemu, za to z rozsądnym kosztem, nazywana jest klasą algorytmów aproksymacyjnych. Zakładamy, że w wielu przypadkach rozwiązanie "prawie dobre" otrzymane w rozsądnym czasie jest lepsze, niż rozwiązanie najlepsze, którego znalezienie wymaga "nierozsądnie dużo" czasu.

Rozważmy problem plecakowy sformułowany w punkcie 3 tego wykładu (por. Sara Baase, Computer Algorithms). Niech s₁,...,s_n będzie ciągiem wag przypisanych obiektom i niech c będzie maksymalną, dopuszczalną wagą wybranych obiektów. Szukamy takiego algorytmu, który znajduje wektor (x_i)_i
£n o elementach 0, 1, tak by suma

Idea rozwiązania przybliżonego jest następująca: skoro nie możemy przejrzeć wszystkich możliwych podzbiorów zbioru obiektów, to przynajmniej przejrzyjmy podzbiory o mocy co najwyżej k i na ich bazie spróbujmy zbudować rozwiązanie. W przedstawionym algorytmie przyjmujemy, że obiekty są ponumerowane liczbami naturalnymi {1, ..., n}, a Set oznacza podzbiór zbioru {1, ..., n} i służy do zapamiętania wybranego podzbioru obiektów.

Knapsack_k {
	Ustaw obiekty w porządku nierosnących wartości ich wag.
	Niech to będzie ciąg s_i1, s_i2,...,s_in.
	MaxSum := 0;
	Set := {}; // Set jest na początku zbiorem pustym
	for każdego podzbioru T zbioru {1,..., n} o co najwyżej k elementach do
	sum := suma wag obiektów w zbiorze T;
	for j := 1 to n do //przeglądamy pozostałe obiekty
	if (obiekt i_j nie należy do T) then //i ewentualnie uzupełniamy zbiór T
	if ((sum + s_ij) £ c ) then
	sum := sum + s_ij;
	T := TÈ {i_j}
	fi
	fi
	od;
	if (MaxSum < sum) then //jeśli znalezione właśnie rozwiązanie jest lepsze
	MaxSum := sum; // zapamiętujemy je
	Set := T;
	fi
	od
}

Ten prosty schemat definiuje ciąg algorytmów Knapsack_k dla wszystkich k. Im większe k, tym rozwiązanie uzyskane przez ten algorytm jest bliższe optymalnemu. Natomiast dla ustalonego k, koszt algorytmu Knapsack_k można oszacować przez O(k* n ^k+1). Jest to więc dla każdego k, algorytm wielomianowy ze względu na rozmiar danych n.J

Nie do wszystkich problemów da się zastosować podejście aproksymacyjne. Udowodniono na przykład dla problemu kolorowania grafu, że jeśli istnieje algorytm, który w czasie wielomianowym wyznacza kolorowanie co najwyżej dwa razy większą liczbą kolorów niż liczba minimalna, to istnieje także algorytm wielomianowy, który rozwiązuje ten problem. Ponieważ problem kolorowania grafu jest problemem NP-zupełnym, wynika stąd, że znalezienie algorytmu aproksymacyjnego, dającego "prawie" dobre wyniki, jest tak samo trudne, jak problem P = NP.

Pytanie 7: Przypuśćmy, że dane są obiekty o wagach 54, 45, 43, 29, 23, 21, 14, 1, oraz c= 110. Jakie rozwiązanie znajdzie algorytm Knapsack_2?