WYKŁAD 2

Zastosowania różnią się w zależności od odpowiedzi na pytanie „ czy podzbiór ma być odrzucony”.
Rekurencyjnie generowaliśmy wszystkie możliwe prefiksy i wybieraliśmy te, które tworzyły
rozwiązanie:

1. startujemy z prefiksu pustego
2. tworzyliśmy wszystkie permutacje
3. bierzemy prefiks i robimy wszystkie jego permutacje rekurencyjnie (drzewo).

Zrobiliśmy algorytm który mocno oszczędza pamięć (bo zawse przechowujemy info o węźle).
Teraz chcemy, aby rekurencyjnie sobie on „podróżował”.
Mieliśmy listę A, a na niej był zdefiniowany prefiks (elementy wzoru, które jakoś już
ustaliliśmy)oraz listę B (z elementami nieustawionymi). Próbowaliśmy napisać prostą metodę
eliminacji zrbioró. Kiedy nie należy już takiego prefiksu rozszerzać.

1 metoda. Wszystkie rozwiązania mają pewien określony prefiks
<rysunek 1>
Mamy już zmienną „najlepsze rozwiązanie”. Próba odpowiedzi na pytanie, czty ten węzeł podzilić
czy nie:
Bierzemy miasto, do którego komiwojażer ma dojść. Mamy jakiś prefiks. On się kończy na 3, wiec
dodajemy do jego drogi krawędź do 4.
Naszym celem jest znalezienie jak najkrótszej drogi komiwojażera.

Jeżeli suma tych dróg jest już większa niż wartość dla przejrzanego, to nasze kryterium ma
własność addytywności. Wraz z dodaniem czegoś jeszcze, nie zmienimy już posiadanej wartości.
Skoro nic lepszego nie znajdziemy już, to po co ono? usuwamy zatem to rozszerzenie.

<rysunek 2>

Biorąc uwagę odległości nie ma skrajnych różnic.
Nasza metoda odcięć będzie działa, ale jak mając 50 zadań odcinamy gdzieś na 48 poziomie… lipa.
Jak to ulepszyć?
My patrzymy cały czas tylko na prefiks (zbiór A). A nie ruszamy zbioru B. Musimy się zastanowić,
czy warto mimo wszystko przeszukiwać zbiór B.

D (droga komiwojażera całkowita)
D = Da

Nasz prefiks opisuej nam wiele rozwiązań. Różnią się tym jak El z listy B będą odwiedzane te
miasta. Więc pomyślmy:
Któreś z tych rozwiązań na pewno jest najlepsze., np.:
<rysunek 3>
Ale jak to zrobić, to nie wiadomo, bo to problem trudny. Co możemy zrobić?
Spróbować ją przybliżyć. Spróbujemy oszacować wartość rozwiązania (trójką).
<wzór 1>

Tamten warunek odcięcia wyglądał tak:

if (Kryterium(Najl) >L Da + E(B))
Podział();

Zamiast E spróbujemy oszacować jaka będzie najkrótsza zroga rpzez pozostałe miasta.

Jeżeli podstawimy 0, to nam to trochę przeszkadza.
Jaki jest cel tego? Znalezienie opt rozw. Musimy znaleźć taki zbiór do odcięcia, któ®y nie usunie
nam przypadkowo najlepszego rozwiązania.

Mamy sytuację. Wiemy, ze najlepsze rozwiązanie, to D(trójkąt).

<rysunek 4>

Jakei musi być E tak, aby zgodnie z rysunkiem wybrać właściwe rozwiązanie.

<wzór 2>

Mamy dwie możliwości. Znalezione rozw jest lepsze lub gorsze niż dotychczas najlepsze.

///

Jaki musi być błąd abyśmy wiedzieli że nie odcięliśmy złego rozwiązania?

pierwsza estymacja? Nie da się reszty miast przejść z lepszym wynikiem, niż zero.

Jeżeli najlepsze z danego podzbioru jest gorsze niż najlepsze dotychczas znalezione, to chcemy
dokonać odcięcia.

<wzór 3>

Musimy opracować jakąś relację mniejsze/większe takie, aby nie popełnić błędu.

Chcemy oszacować od dołu najkrótszą drogę.

Ta nasza metoda: to co przechodzi komiwojażer + 0. Jak usprawnić ?

Załóżmy, że:
<rysunek>
Sprawdź wszystkie krawędzie wychodzące z 4 i wybierz najlepsze.

Jak inaczej to ograniczenie oszacować?

Znaleźć najkrótszą drogę i pomnożyć przez ilość wszystkich dróg, które musimy wyznaczyć
pomiędzy miastami.

<wzór 4>

Prowadzi nas to jednak do tego, że mamy jakieś miasta odległe o 1 i wszytki inne bardzo odległe.
Np.:

<rysunek 6>

<wzór 5>

Załóżmy, że mamy listę:

Jeżeli chcemy znaleźć wartość tego oszacowania to sumujemy pierwsze n-1 elementów w liście.

Chcemy tu otrzymać zbiór krawędzi z B posortowane od największego do najmniejszego. Zatem z
listy musimy wykreślić wszystkie krawędzie które są incydentne z 5. Będzie ich O(n).

Mamy procedurę:
Usun(x);

Przeszukuje listę i usuwa krawędzie incydentne z x.

Spróbujmy to zapisać jako fragment z reprezentacji macierzowej.

<rysunek 8>

Chjcąc usunąć krawędzie incydentne z x to będziemy patrzeć na macierz. Wszystkie te zaznaczone
kropkami w takim razie będziemy usuwać. i to realizujemy w czasei O(n).

Załóżmy, ze zamiast wagi, to w tej macierzy przechowujemy wskaźnik na inne elementy.

Tworząc taką macierz oprócz wskaźników alokujemy pamięć na te elementy.

Szybciej się nie da.

Metoda:

Dodaj(x);

Pamietamy, aby przywrócić strukturę:

for (dsivbdsbg){
x = B_pop_front();
A.push_back(x);
…..
x = A.pop_back();
B.push_back(x)
}

Każdy z elementów ma zapamiętanego sąsiada wcześniej. Zatem dowiązujemy wskaźniki. Ale
problem taki, ze wykonując tą metodę przywracamy wszystkie te elementy na listę. Ale załóżmy,
ze mamy taką listę:

<rysunek 10>

Potem przywracamy krawędzie. Przywracamy X i dochodzimy do miejsca S. Ale czy mamy tę
krawędź z powrotem przywracać?

Jak przywracamy to musimy np. mieć znacznik, tkto jest właścicielem danej krawędzie. Jeżeli np.
od x przywracamy, to sprawdzamy, że krawędź S należy do y. Zatem nie przywracamy jej w tym
cyklu.