Strona główna

Optymalizacja bazy transportowej Wyznaczanie najkrótszej drogi w sieci


Pobieranie 394.18 Kb.
Strona2/4
Data18.06.2016
Rozmiar394.18 Kb.
1   2   3   4

Krok I


W zbiorze Q wyznaczamy węzeł h, dla którego zachodzi: dh= min di

Krok II


Ze zbioru Q usuwamy węzeł h, w wyniku czego Q:=Q\{h}.

Krok III


Wyznaczamy wszystkie węzły, które są następnikami h, a więc S(h).

Krok IV


Kolejno dla każdego węzła jS(h) porównujemy wcześniej przyporządkowana odległość dj z suma odległości dh powiększonej o długość przemieszczenia chj. Sprawdzamy więc, czy spełniona jest nierówność:

dh+chjj


Jeżeli nierówność jest prawdziwa, to:

  • Starą odległość zastępujemy nową: dj:= dh+chj.

  • Dla j identyfikujemy poprzednika:(j):=h.

  • Węzeł j wprowadzamy do zbioru Q:Q:=Q{j}.

W przeciwnym przypadku pozostawiamy dj bez zmiany.

Krok V


Jeżeli Q0, to przechodzimy do następnej iteracji, a więc powracamy do kroku I.

Jeżeli Q = 0, postępowanie kończy się.

W samym postępowaniu koncentrujemy się na obliczeniach odległości dj. W celu odczytania ciągu węzłów leżących na najkrótszych drogach wystarczy odczytywać ich numery w trakcie określania odległości. Pomocą będą zapamiętane wskazania bezpośrednich poprzedników (i).
Przykład

Rozpatrzmy przykład sieci przedstawiony na rysunku 1.1. przyjmijmy, że węzeł 1 odzwierciedla producenta. Należy wyznaczyć najkrótsze drogi od producenta do wszystkich pozostałych oraz odpowiadające im odległości.


Start


Przyjmujemy: a:=1, Q:={1}, d1:=0, d2:=,..., d7:=.

ITERACJA I


Ponieważ Q={1}, wybór h jest zdeterminowany i mamy h=1.

Wykreślamy węzeł 1 ze zbioru Q i otrzymujemy Q=0.

Dla h=1 mamy S(1)={2,4}.

Rozpatrujemy kolejno:


j=2, d2:=, d1+c12=30 d2:=30 i Q:={2}

j=4, d4:=, d1+c14=35 d4:=35 i Q:={2,4}


Wyniki przejściowe zawiera tabela 1.2.

i

1

2

3

4

5

6

7

dj

0

30



35







(i)

*

1

-

1

-

-

-


Tab. Zapis wyników iteracji 1.

ITERACJA 2


W zbiorze Q={2,4} wyznaczamy węzeł h, dla którego dh= min di. Korzystając z wyników pierwszej iteracji otrzymujemy h=2. Wykreślamy węzeł 2 ze zbioru Q i otrzymujemy Q={4}. Dla h=2 mamy S(2)={3,5}.

Rozpatrujemy kolejno:


j=3, d3= , d2+c23=30+13=43 d3:=43 i Q:={3,4}

j=5, d5= , d2+c25=30+30=60 d5:=60 i Q:={3,4,5}.


Wyniki przejściowe zawiera tabela 1.3.


i

1

2

3

4

5

6

7

dj

0

30

43

35

60





(i)

*

1

2

1

2

-

-

Tab. Zapis wyników iteracji 2.

ITERACJA 3

W zbiorze Q={3,4,5} wyznaczamy węzeł h, dla którego dh= min di.


Korzystając z wyników drugiej iteracji otrzymujemy h=4.

Wykreślamy węzeł 4 ze zbioru Q i otrzymujemy Q={3,5}.

Dla h=4 mamy S(4)={3,6}.

Rozpatrujemy kolejno:


j=3, d3:=43, d4+c43=35+12=47 d3:=43
1   2   3   4


©snauka.pl 2016
wyślij wiadomość