Witam,
Potrzebuje pomocy z projektem o tytule Algorytm Dijkstry jako algorytm zachlanny. Kilkakrotnie wysylany i poprawiany do wykladowcy ostatnio odpisal mi, ze nie mam calkowitego dowodu na ¨zachlannosc¨ algorytmu, polecil, zebym, cytuje:
¨Należy dopasować ogólny schemat definiujący algorytm zachłanny poprzez uszczegółowienie,
co oznaczają, w przypadku algorytmu Dijkstry, poszczególne obiekty, na których operuje
algorytm zachłanny ( w szczególności: E, w, S).¨
Jestem lekko zdesperowany, zrobilem cala prace, brakuje mi tego elementu. Schemat ogolny z tego co zrozumialem wyglada nastepujaco:
Algorytm zachłanny
1 begin
2 posortuj zbiór \(\displaystyle{ E}\) według malejących wag tak, by
3 \(\displaystyle{ E = \left\{e_{1} ,...,e_{n} \right\}}\), gdzie \(\displaystyle{ w\left(e_{1} \right) \ge w \left(e_{2} \right) \ge ... \ge w\left(e_{n} \right);}\)
4 \(\displaystyle{ S:=Ø;}\)
5 for \(\displaystyle{ i := 1}\)to \(\displaystyle{ n}\) do
6 if \(\displaystyle{ S \cup \left\{ e_{i} \right\} \in \vartheta}\) then \(\displaystyle{ S := S \cup \left\{ e_{i} \right\}}\)
7 end
Twierdzenie
Jesli \(\displaystyle{ M=<E,\vartheta>}\) jest matroidem, to zbior \(\displaystyle{ S}\) znaleziony przez algorytm zachlanny jest zbiorem niezaleznym o najwiekszej wadze. Na odwrot, jesli \(\displaystyle{ M=<E,\vartheta>}\) nie jest matroidem, to istnieje funkcja \(\displaystyle{ w:E \rightarrow R^{+}}\) taka, ze \(\displaystyle{ S}\) nie jest zbiorem niezaleznym o najwiekszej wadze.
Mam to uszczegolowic w odniesieniu do zagorytmu Dijkstry, prosze o pomoc.
Literatura: W. Lipski, Kombinatoryka dla programistow
Algorytm Dijkstry jako algorytm zachlanny
- paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
Algorytm Dijkstry jako algorytm zachlanny
Na pewno mowa o algorytmie Dijkstry? Ten, który przedstawiłeś, to algorytm Kruskala...
-
- Użytkownik
- Posty: 38
- Rejestracja: 7 lut 2010, o 11:46
- Płeć: Mężczyzna
- Lokalizacja: Białystok
- Podziękował: 12 razy
Algorytm Dijkstry jako algorytm zachlanny
Nie jestem pewny, czy znalazlem dobra ¨definicje¨ dla mojego profesora, ale ten polecil mi Ksiazke Lipskiego i wskazal modul dotyczacy tw. Rado-Edmondsa. Moze chodzilo o cos innego? Z profesorem jest bardzo trudny kontakt mailowy, a inaczej nie moge z nim rozmawiac.
- paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
Algorytm Dijkstry jako algorytm zachlanny
Ja nie o to pytam. Pytam, który algorytm jest tematem pracy. Dijkstry (najkrótsze ścieżki w grafie z jednym źródłem), czy Kruskala (minimalne drzewo rozpinające)? Kod, który napisałeś, oraz zastosowanie matroidów wskazują na Kruskala.
Z drugiej strony, uparcie piszesz o Dijkstrze.
Z drugiej strony, uparcie piszesz o Dijkstrze.
-
- Użytkownik
- Posty: 38
- Rejestracja: 7 lut 2010, o 11:46
- Płeć: Mężczyzna
- Lokalizacja: Białystok
- Podziękował: 12 razy
Algorytm Dijkstry jako algorytm zachlanny
W takim razie moglem przepisac zla definicje. Chodzi o algorytm Dijkstry. Mam za zadanie znalesc ogolna definicje algorytmu zachlannego i uszczegolowic go pod katem algorytmu Dijkstry
- paladin
- Użytkownik
- Posty: 148
- Rejestracja: 24 sty 2005, o 22:15
- Płeć: Mężczyzna
- Lokalizacja: Kraków
- Pomógł: 19 razy
Algorytm Dijkstry jako algorytm zachlanny
To niedobrze. Twierdzenie Rado-Edmondsa stosuje się tylko do niektórych algorytmów zachłannych (np. Kruskala), algorytm Dijkstry pod to twierdzenie nie podpada (a przynajmniej ja nie znam i nie widzę związku). W ogóle ciężko mówić o jakiejś ogólnej definicji algorytmów zachłannych - to raczej termin używany potocznie niż precyzyjne pojęcie matematyczne.