Zaawansowane algorytmy i struktury danych/Ćwiczenia 5: Różnice pomiędzy wersjami
Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 1: | Linia 1: | ||
{{zadanie|1|2= | |||
{{ | Zaproponuj efektywny algorytm obliczania najkrótszych ścieżek z jednego wierzchołka w [[dag<nowiki>|</nowiki>DAGu]] o dowolnych wagach krawędzi. | ||
|3= | |||
Zaproponuj efektywny algorytm obliczania najkrótszych ścieżek z jednego wierzchołka w [[dag|DAGu]] o dowolnych wagach krawędzi. | 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<nowiki>|</nowiki>relaksację]] krawędzi w porządku topologicznym. | ||
}} | |||
== Zadanie 2 == | == Zadanie 2 == | ||
| Linia 13: | Linia 10: | ||
'''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. | '''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. | ||
<div class="mw-collapsible mw-made=collapsible mw-collapsed"> '''Rozwiązanie''' <div class="mw-collapsible-content" style="display:none"> | <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 | 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: | sposób: | ||
| Linia 31: | Linia 30: | ||
oraz odległości w grafie <math>G</math> zadają rozwiązanie tego | oraz odległości w grafie <math>G</math> zadają rozwiązanie tego | ||
układu. | układu. | ||
</div> </div> | |||
</div> | |||
</div> | |||
Wersja z 17:24, 23 lip 2006
Zadanie 1
Zaproponuj efektywny algorytm obliczania najkrótszych ścieżek z jednego wierzchołka w [[dag|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
