Zaawansowane algorytmy i struktury danych/Ćwiczenia 5

Zadanie 1

Zaproponuj efektywny algorytm obliczania najkrótszych ścieżek z jednego wierzchołka w DAG-u o dowolnych wagach krawędzi.

Rozwiązanie

Po pierwsze w DAG-u nie ma cykli, a więc także nie ma cykli o ujemnej wadze. Zauważmy, że wszystkie ścieżki w DAG-u idą zgodnie z porządkiem topologicznym, a więc także te najkrótsze. Odległości DAG-u można więc policzyć wykonując relaksację krawędzi w porządku topologicznym.

Zadanie 2

Układ ograniczeń różnicowych zadany jest poprzez zbiór zmiennych $X=\{x_0,\dots ,x_n\}$ oraz zbiór nierówności liniowych $O=\{x_{i_0}-x_{j_0}\le b_0,\dots ,x_{i_m}-x_{j_m}\le b_m\}$, gdzie $i_k,j_k\in X$, $b_k\in {ℛ}$ dla $k=0,\dots ,m$. Rozwiązaniem układu ograniczeń różnicowych jest wartościowanie zmiennych $X$, dla którego spełnione są wszystkie nierówności z $O$. Zaproponuj efektywny algorytm znajdujący rozwiązanie układu ograniczeń liniowych.

Rozwiązanie

Problem ten można rozwiązać poprzez sprowadzenie do problemu najkrótszych ścieżek z jednym źródłem i wykorzystanie algorytmu Bellmana-Forda. Mając dane zbiory $X$ i $O$, konstruujemy na ich podstawie graf $G=(X,E)$ oraz funkcję wagową $w:E\to {ℛ}$ w następujący sposób:

$E=\{(x_i,x_j):x_i-x_j\le b\in O\},$ $w(x_i,x_j)=\min \{b:x_i-x_j\le b\in O\}.$

Łatwo teraz pokazać, że w grafie $G$ nie ma cyklu ujemnej długości, jeżeli układ ograniczeń różnicowych ma rozwiązanie, oraz odległości w grafie $G$ zadają rozwiązanie tego układu.

Zadanie 3

Skrzynka $d$-wymiarowe o wymiarach $(x_1,x_2,\dots ,x_d)$ mieści się w skrzynce o wymiarach $(y_1,y_2,\dots ,y_d)$, jeżeli istnieje permutacja $p$ zbioru $\{1,2,\dots ,d\}$ tak, że $x_{p_1}<y_1,x_{p_2}<y_2,\dots ,x_{p_d}<y_d$.

1. Uzasadnij, że relacja mieszczenia się jest przechodnia.
2. Opisz skuteczną metodę określania, czy jedna $d$-wymiarowa skrzynka zagnieżdża się w drugiej.
3. Przypuścimy, że dany jest zbiór $n$ $d$-wymiarowych skrzynek $B_1,B_2,\dots ,B_n$. Podaj skuteczny algorytm określający najdłuższy ciąg $\{B_1,B_2,\dots ,B_n\}$ skrzynek mieszczących się w sobie nawzajem, tzn. takich, że $B_j$ mieści się w $B_{j+1}$ dla $j=1,2,\dots ,n-1$. Podaj czas działania algorytmu ze względu na $n$ i $d$.

Rozwiązanie

1. Jeżeli $p$ to permutacja pokazująca, że $A$ mieści się w $B$, a $p^{\prime }$ pokazuje, że $B$ mieści się w $C$, to złożenie permutacji $p\cdot p^{\prime }$ pokazuje, że $A$ mieści się w $C$.
2. W celu sprawdzenia, czy dwie skrzynki mieszczą się w sobie, można użyć metody zachłannej. Jeżeli chcemy sprawdzić czy skrzynka o wymiarach $(x_1,x_2,\dots ,x_d)$ mieści się w skrzynce o wymiarach $(y_1,y_2,\dots ,y_d)$ to sprawdzamy, czy po ich posortowaniu zachodzi $x_i<y_i$ dla $i=1,\dots ,d$.

Najpierw sortujemy wymiary skrzynek

Zadanie 4

Arbitraż walutowy polega na operacji jednoczesnego kupna i sprzedaży waluty na tym samym rynku w celu osiągnięcia zysku wynikającego z różnic kursowych. Na przykład: załóżmy, że kurs wymiany 1 USD wynosi 46.4 rupii, kurs rupii w jenach japońskich wynosi 2.5, natomiast 1 jen kosztuje 0.0091 USD. Poprzez wymianę walut, spekulant może rozpocząć transakcję kupna USD: 46.4 × 2.5 × 0.0091 = 1.0556 USD, osiągając korzyść finansową w wysokości 5.56 %. Przypuścimy, że mamy dane $n$ walut $c_1,c_2,\dots ,c_n$ i $n\times n$ tabelę $R$ kursów walutowych, tak że kurs 1 jednostki waluty $c_i$ wynosi $R[i,j]$ jednostek waluty $c_j$. Podaj skuteczny algorytm stwierdzający istnienie następującego ciągu walut, takich że:

1. Parser nie mógł rozpoznać (błąd składni): {\displaystyle R[i_1, i_2] \cdots R[i_2, i_3] \cdot R[i_{k-1}, i_k] · R[i_k, i_1] > 1} . Zanalizuj czas działania algorytmu.

1. Podaj skuteczny algorytm drukowania takiego ciągu walut, jeżeli on istnieje. Ponadto, zanalizuj czas działania tego algorytmu.

Rozwiązanie