Algorytm Dijkstry jako algorytm zachlanny

paewel
Użytkownik
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

Post autor: paewel »

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
Awatar użytkownika
paladin
Użytkownik
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

Post autor: paladin »

Na pewno mowa o algorytmie Dijkstry? Ten, który przedstawiłeś, to algorytm Kruskala...
paewel
Użytkownik
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

Post autor: paewel »

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.
Awatar użytkownika
paladin
Użytkownik
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

Post autor: paladin »

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.
paewel
Użytkownik
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

Post autor: paewel »

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
Awatar użytkownika
paladin
Użytkownik
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

Post autor: paladin »

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.
ODPOWIEDZ