headerphoto

Algorytmy z powrotami - Przykładowe zastosowania algorytmów z powrotami

Problem sumy podzbiorów i pakowania plecaka (0-1)

Załóżmy, że istnieje pewien zbiór elementów, którym przypisane są wagi, oraz pewna liczba W. Problem sumy podzbiorów polega na dobraniu elementów z tego zbioru w taki sposób, aby ich sumaryczna waga była równa dokładnie liczbie W. Zadanie to łatwo zobrazować na przykładzie załadowywania ciężarówki. Jej maksymalna ładowność to liczba W, a zbiór towarów, którymi można ją wypełnić, to zawartość zbioru elementów. Ciężarówka musi zostać tak załadowana, aby całkowita waga przewożonych towarów, była równa maksymalnej ładowności auta.

Gdyby każdemu z przedmiotów ładowanych na ciężarówkę przypisać jeszcze wartość i założyć, że ciężarówka nie musi być w całości wypełniona, to otrzymamy w ten sposób problem pakowania plecaka (0-1). Problem ten polega na załadowaniu ciężarówki w taki sposób, aby sumaryczna wartość załadowanych przedmiotów była możliwie jak najwyższa, a ich waga nie przekraczała maksymalnej ładowności pojazdu.

Symbol (0-1) oznacza, że dany towar jest ładowany w całości na ciężarówkę lub nie. Odnosi się to również do logiki postępowania algorytmu z powrotami dla obu przedstawianych wyżej problemów. Algorytmy te tworzą drzewo przestrzeni stanów i poruszają się w dół po wierzchołkach, kierując się lewą bądź prawą krawędzią w zależności od tego czy waga przypisana danemu poziomowi jest dodawana do ogólnej sumy wag czy też nie.

Podsumowując, zadaniem algorytmu z powrotami dla problemu sumy podzbiorów jest odnalezienie wszystkich możliwych kombinacji liczb ze zbioru elementów (wag), które w sumie dadzą liczbę W. Jeśli zaś chodzi o problem plecakowy (0-1), celem jest wyznaczenie takiej kombinacji elementów, aby ich sumaryczna wartość była możliwie jak najwyższa, a waga nie przekraczała liczby W.