Zaawansowane algorytmy i struktury danych/Ćwiczenia 5: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
|||
| Linia 2: | Linia 2: | ||
{{kotwica|zadanie 1|}} | {{kotwica|zadanie 1|}} | ||
Zaproponuj efektywny algorytm obliczania najkrótszych ścieżek z jednego | Zaproponuj efektywny algorytm obliczania najkrótszych ścieżek z jednego wierzchołka w [[dag|DAGu]] o dowolnych wagach krawędzi. | ||
wierzchołka w [[dag|DAGu]] o dowolnych wagach krawędzi | |||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> '''Rozwiązanie''' <div class="mw-collapsible-content" style="display:none"> Po pierwsze w DAGu nie ma cykli a więc także nie ma cykli o ujemnej wadze. Zauważmy, że wszystkie ścieżki w DAGu idą zgodnie z porządkiem topologicznym, a więc także te najkrótsze. Odległości DAGu można więc policzyć wykonując [[#relaksacja|relaksację]] krawędzi w porządku topologicznym. | |||
</div> | </div> | ||
</div> | </div> | ||
| Linia 16: | Linia 11: | ||
{{kotwica|zadanie 2|}} | {{kotwica|zadanie 2|}} | ||
'''Układ ograniczeń różnicowych''' zadany jest poprzez zbiór zmiennych <math>X=\{x_0, \ldots, x_n\}</math> oraz zbiór nierówności liniowych | '''Układ ograniczeń różnicowych''' zadany jest poprzez zbiór zmiennych <math>X=\{x_0, \ldots, x_n\}</math> oraz zbiór nierówności liniowych <math>O=\{x_{i_0} - x_{j_0} \le b_0, ldots, \{x_{i_m} - x_{j_m} \le b_m\} </math>, gdzie <math>i_k, j_k \in X</math>, <math>b_k\in \mathcal{R}</math> dla <math>k = 0,\ldots, m</math>. Rozwiązaniem układu ograniczeń różnicowych jest wartościowanie zmiennych <math>X</math> dla którego spełnione są wszystkie nierówności z <math>O</math>. Zaproponuj efektywny algorytm znajdujący rozwiązanie układu ograniczeń liniowych. | ||
b_m\} | |||
gdzie <math>i_k, j_k \in X</math>, <math>b_k\in \mathcal{R}</math> dla <math>k = 0,\ldots, m</math>. Rozwiązaniem układu ograniczeń różnicowych jest wartościowanie zmiennych <math>X</math> dla którego spełnione są wszystkie nierówności z <math>O</math>. Zaproponuj efektywny algorytm znajdujący rozwiązanie układu ograniczeń liniowych. | |||
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 <math>X</math> i <math>O</math> konstruujemy na ich podstawie graf <math>G=(X,E)</math> oraz funkcję wagową <math>w:E \to \mathcal{R}</math> w następujący sposób: | <div class="mw-collapsible mw-made=collapsible mw-collapsed"> '''Rozwiązanie''' <div class="mw-collapsible-content" style="display:none"> | ||
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 <math>X</math> i <math>O</math> konstruujemy na ich podstawie graf <math>G=(X,E)</math> oraz funkcję wagową <math>w:E \to \mathcal{R}</math> w następujący | |||
sposób: | |||
| Linia 40: | Linia 27: | ||
Łatwo teraz pokazać, że w grafie <math>G</math> nie ma cyklu ujemnej długości jeżeli układ ograniczeń różnicowych ma rozwiązanie, oraz odległości w grafie <math>G</math> zadają rozwiązanie tego układu. | Łatwo teraz pokazać, że w grafie <math>G</math> nie ma cyklu | ||
ujemnej długości jeżeli układ ograniczeń różnicowych ma rozwiązanie, | |||
</div> | oraz odległości w grafie <math>G</math> zadają rozwiązanie tego | ||
</div> | układu. | ||
</div> </div> | |||
{{zadanie|3|2= | |||
< | Zaproponuj jak wykorzystać algorytm Bellmana-Forda do sprawdzenia, czy w grafie <math>G=(V,E)</math> | ||
i wagach krawędzi opisanych funkcją <math>w:E \to \mathcal{R}</math> istnieje cykl o ujemnej wadze. | |||
|3= | |||
}} | |||
Wersja z 17:16, 23 lip 2006
Zadanie 1
Zaproponuj efektywny algorytm obliczania najkrótszych ścieżek z jednego wierzchołka w DAGu o dowolnych wagach krawędzi.
Rozwiązanie
Zadanie 2
Układ ograniczeń różnicowych zadany jest poprzez zbiór zmiennych oraz zbiór nierówności liniowych , gdzie , dla . Rozwiązaniem układu ograniczeń różnicowych jest wartościowanie zmiennych dla którego spełnione są wszystkie nierówności z . Zaproponuj efektywny algorytm znajdujący rozwiązanie układu ograniczeń liniowych.
Rozwiązanie
Zadanie 3
Zaproponuj jak wykorzystać algorytm Bellmana-Forda do sprawdzenia, czy w grafie i wagach krawędzi opisanych funkcją istnieje cykl o ujemnej wadze.
Rozwiązanie
