Algorytmy
i
struktury danych
WYKA
AD 7
Dr inż. Krzysztof Pancerz
Krzysztof Pancerz
Algorytmy i struktury danych
Algorytmy z powrotami

Algorytmy z powrotami są wykorzystywane do
rozwiązywania problemów, w których z
określonego zbioru wybierana jest sekwencja
obiektów tak, aby spełniała ona określone
kryteria.

Algorytmy z powrotami są zmodyfikowanym
przeszukiwaniem drzewa w głąb.

Ścieżka od korzenia do liścia jest potencjalnym
rozwiązaniem.

Drzewo jest w tym przypadku nazywane
drzewem przestrzeni stanów.
Krzysztof Pancerz
Algorytmy i struktury danych
Algorytmy z powrotami

Algorytm z powrotami jest algorytmem, w
którym po zorientowaniu się, że węzeł nie
prowadzi do rozwiązania, wracamy do węzła
nadrzędnego i kontynuujemy wyszukiwanie od
węzła następnego.

Węzeł nieobiecujący  węzeł, przy którego
odwiedzaniu można określić, że nie prowadzi
on do rozwiązania.

Węzeł obiecujący  węzeł, przy którego
odwiedzaniu można określić, że prowadzi on do
rozwiązania.
Krzysztof Pancerz
Algorytmy i struktury danych
Algorytmy z powrotami

Algorytm z powrotami polega na wykonywaniu
przeszukiwania w głąb drzewa przestrzeni
stanów, aby sprawdzić czy dany węzeł jest
obiecujący, czy nie.

Przycinanie drzewa (ang. pruning)  powrót do
węzła nadrzędnego jeżeli dany węzeł nie jest
obiecujący.
Krzysztof Pancerz
Algorytmy i struktury danych
Ogólna struktura algorytmu z powrotami
sprawdz
_węzeł(x)
{
jeśli x jest obiecujący
{
jeśli istnieje rozwiązanie dla x
{ drukuj rozwiązanie; }
w przeciwnym razie
{ dla każdego węzła potomnego y węzła x
{ sprawdz
_węzeł(y); }
}
}
}
Krzysztof Pancerz
Algorytmy i struktury danych
Różnica między przeszukiwaniem w głąb a
algorytmem z powrotami

Algorytm przeszukiwania w głąb:

węzeł pochodny jest zawsze odwiedzany

Algorytm z powrotami

węzeł pochodny jest odwiedzany tylko w
przypadku, gdy węzeł macierzysty jest obiecujący i
nie znaleziono w nim rozwiązania
Krzysztof Pancerz
Algorytmy i struktury danych
Przykłady wykorzystania algorytmów z powrotami

Problem plecakowy (każdy element posiada
wartość oraz wagę, należy spakować do
plecaka elementy o jak największej wartości
sumarycznej jednak tak, aby nie przekroczyć
ustalonej wagi).

Problem n królowych (umieszczenie n
królowych na szachownicy w taki sposób, aby
nie szachowały się).
Krzysztof Pancerz
Algorytmy i struktury danych