WYKŁAD 03

Lista A = 1; B = 2 , ... , n
best = inf;
Drzewo(){
if(|B| == 0){
}
else for(int i = 0; i < |B|; i++){
x = B.pop_ffront();
A.push_back(x); //D+ = ......
if(...) Drzewo();
x = A.pop_back // D- = ...
B.push_back(x);
}
}

To nam dzisiaj będzie bardzo potrzebne, dlatego niech to sobie tutaj będzie.

Węzeł jest opisany prefiksem A i listą B.
Prezentuje nam on się tak:
<rysunek 1>
Chcemy znaleźć jak najlepsze dolne ograniczenie.

K(A) + K(B)
K(A) - koszt związany z prefiksem. To możemy oszacować bez problemu, ale nie wiemy jak K(B)

chcemy stworzyć procedurę, która zagwarantuje nam to, że:

<wzór 1>

Potem stworzyliśmy drugą bardziej wyrafinowaną metodę:
Szukaliśmy krawędzi o minimalnej wadze i założyliśmy, że komiwojażer musi się poruszać po
drodze conajmniej o takiej wadze, czyli:

<wzór 2>

Trzecia metoda to rozwinięcie poprzedniej.
Pozbyliśmy się patologii spośród poprzedniej.
Czyli Sortowaliśmy te krawędzie wg wag niemalejąco.

<wzór 3>

Ten algorytm początkowy ma duży nadkład obliczeń. Bo musimy wiecej niż n! rozwiązań zrobić.

Koszt związany z prefiksem:
W każdymwęźle drzewa musimy zbadać koszt estymacji.

Ale problem ze zmiennoprzecinkowymi liczbami. Jak tego sie pozbyć?

Można tak:

<rysunek 2>

______________

TEraz pracujemy nad innymi formami odcinania.
A może warto jeszcze zapytać, czy to co już mamy, to jest dobrym rozwiązaniem. Czy ten prefiks,
którym operujemy jest dobry.

Najprostsza metoda odcinania.
Załóżmy, ze komiwojażer chodzi po takim prefiksie:

<rysunek 3>

Czy taki może być początkiem rozwiązania optymalnego?

Jeżeli z danych odcinkół możemy skonstruować krótszą drogę, to będzie to ta droga lepsza.

Jaką złożoność ma ten sposób? Załóżmy, ze te przecinanie można sprawdzić w czasie O(1).

Jeżeli do Y to nasz dotychczasowy prefiks i dotąd doszliśmy i nie było żadnych przecięć, to jest
dobrze, bo inaczej byśmy zatrzymali rekurencję.

Mamy prefiks A który rozpoczyna sie miastem 1 , kończy X. Mając taki prefik możemy optymalnie
wyznaczyć kolejność miast? Załóżmy, ze możemy i to jak możemy uzupełnić ten prefiks
zaznaczmy symbolem gamma.

Mamy A', który rozpoczyna się 1, kończy X, w środku te same miasta, ale w innej kolejności. Jak
optymalnie uzupełnić ten prefiks? Tak samo!
Z ptk widzenia tego co dalej, to każde prefiksy są takie same.
Wiec, jeśli zachodzi warunek

<wzór 4>

To K(a) nie może być rozwiązaniem.
Możemyw iec kolejną metodę odcinania wyprowadzić.

Algorytmy heurystyczne. Nie można szybko sprawdzić czy jest odcięcie. Bo musimy każdą
permutację sprawdzić.
Pomysły:
Próbujemy losowo 100 prefiksów wylosować. Może któryś lepszy. Jeżeli tak, to poprzedni
odrzucamy.
Ale mozna się w różne metody bawić sprawdzania czy da sie uzyskać w roozsądnym czasie lepszy
prefix.

Heurystyczne: konstruują rozwiązanie na podst zdroworozsądkowej przesłanki.
Strategia zach łanna:
Komiwojażer musi z miasta 1 zacząć. Idzie tam, gdzie najbliżej jest. No i mamy prefiks. Spełnia od
warunki metody eliminacji (bo zaczyna sie i kończy tak samo). I sprawdzamy czy wartość funkcji
celu jest lepsza niż dla poprzedniego. Jeżeli tak, to udało się i odcinamy fragment. Jeżeli nie, to
straciliśmy czas. Na labach okaże sie, że prawie zawsze te algorytm to strata czasu.

//Co się stanie, jak ten algorytm (z początku wykładu) odpalimy kilka razy? No, lepszego
rozwiązania nie dostaniemy.

Problem w tym, że często mamy tak, że na końcu mamy kawał drogi do pkt X (patrz rysunek 5>
Próbujemy inaczej:

Startujemy

<rysunek 6>

Dodajemy wierzchołki.

Okazuje się, że to rozw jest całkiem fajne. Dosyć często dokonujemy odcięcia,ale... złożoność jest
bardzo duża. Mnie więcej O(n^3).
Pomyślmy, że w każdy węźle wykonujemy n^3 operacji. Zysk jest mały, a operacji dużo.

Inne pomysły na algorytmy heurystyczne:

<rysunek 7>

Dla danego grafu określonego przez wierzchołki szukamy minimalnego drzewa rozpinającego.
Dokonując przeglądu drzewa robimy otoczkę wokół rozwiązania i budujemy drogę. Co ciekawe:
ten alg ma wykonaną analizę najgorszego przypadku.

PRzejdźmy teraz do drugiego problemu i nad nim popracujmy.

-----------------------------------------

Te problem to szeregowanie zadań o notacji:
<wzór 1>
Zmaksymalizować funkcję zadań, minimalizacja strat wartości.

Jak wygląda węzeł z pkt widzenia tego problemu. Prefix A mówi w jakiej kolejności są
wykonywania zadania z listy A.

Na A umiemy wyrazić moment zakończenia zadań z listy A

<rysunek 1>

Dlaczego chcąc tu pracować, musimy odwracać kryterium? Bo my chcemy maksymalizować
wartość, w przeciwieństwie do komiwojażera.

A więc Za to pewnik. Więc Za + górne oszacowanie.

Popatrzmy na ten problem.

<rysunek 2>

Każde zadanie z dalszych... nie wiemy w którym momencie się skończy, ale na pewno nie w
odcinku (0, Ta). Jeżeli przyjmiemy, że każde zadanie B ma wartość tą, co w pkt Ta, to nie
popełnimy błędu.

Dla każdego zadania, które bedzie wykonywanie po tych z prefiksu, zamiast rpzyjmować
prawdziwą wartość która może występować, to wybieramy tę, na któ¶ej się dotychczas kończy.

Tutaj zakładamy, że tpo zadaniach określone przez prefiks każde zadanie ma czas równy zero. I
skończy się w tym samym momencie, bez względu na kolejność.

Jak zrobić lepsze ograniczenie?
Każde zadanie z B ma czas wykonywania. Więc każde zadanie nie skończy się w tym momencie
wykonywać, tylko np w "K".

<wzór 2>

My w ograniczamy coś takiego, że każde zadanie ma funkcję spadku wykonania zadanaia, a my od
danego miejsca prostujemy funkcję.

<rysunek 3>

Co możemy zrobić?

<rys 4>

Jaki byłby problem, gdyby funkcje spadku wartości zadania były liniowe? Wtedy można dojść do
wniosku, że istnieje wielomianowy algorytm rozwiązania. Więc przekształćmy ten problem tak:

Zaznaczamy pkt, puszczamy prostą, mamy takie przybliżenie, dochodzimy do wniosku, że to
ograniczenie to wartość optymalna. Tutaj potrzebujemy sortowania po współczynnikach nachylenia
prostej. Będzie algorytm wolniejszy, ale może częściejj będzie dokonywał odcięć. Ale okazuje się,
że on dobrze działa.

Można pokusić się o metody eliminacyjne, które nam cośtam będą odcinały.