Strona główna

Optymalizacja bazy transportowej Wyznaczanie najkrótszej drogi w sieci


Pobieranie 394.18 Kb.
Strona1/4
Data18.06.2016
Rozmiar394.18 Kb.
  1   2   3   4
Optymalizacja bazy transportowej



  1. Wyznaczanie najkrótszej drogi w sieci

Pierwszym zadaniem, które musi być rozwiązane w bazie transportowej, jest przygotowanie bazy podstawowych parametrów. Należy do nich wyznaczenie najkrótszych dróg przejazdów z uwzględnieniem specyfiki sieci połączeń. Przyjmując, że droga z miejscowości i do miejscowości j może być inna niż z miejscowości j do miejscowości i, potencjalne trasy przejazdu będziemy przedstawiać za pomocą strzałek. Gdy kierunek przejazdu nie będzie odgrywał roli, strzałki będą zastąpione krawędziami.

W pierwszej kolejności rozpatrzymy przypadek, gdy kierunek przejazdu jest istotny. Strukturę grafu 1.1 i określone przy strzałkach odległości zapiszemy teraz w macierzy, w której wiersze i kolumny odpowiadają węzłom grafu. Przyjmiemy, że w wierszach będą reprezentowane węzły jako początki a w kolumnach jako końce strzałek. W ujęciu tabelarycznym nasza macierz jest przedstawiona w tabeli 1.1.





























Rys. Graf skierowany z wartościami oznaczającymi odległości.






1

2

3

4

5

6

7

1

*

30

*

35

*

*

*

2

*

*

13

*

42

*

*

3

*

14

*

15

38

27

46

4

*

*

12

*

*

34

*

5

*

*

*

*

*

*

18

6

*

*

*

*

*

*

20

7

*

*

*

*

*

*

*


Tab. Macierz odległości.
Nasze zadanie będzie polegać na podaniu algorytmu wyznaczającego najkrótsze drogi między określoną miejscowością a wszystkimi pozostałymi. Będziemy oczywiście zakładać, że obowiązuje nas kierunek przemieszczania zgodny ze wskazaniami strzałek.

Najpierw jednak musimy poznać pewne podstawowe pojęcia i oznaczenia, których znajomość przyda nam się dla lepszego zrozumienia prowadzonych w dalszej części obliczeń.



  • Drogę w grafie skierowanym określa ciąg węzłów będącymi początkami i końcami następujących po sobie strzałek, przy czym wszystkie strzałki muszą mieć zgodny kierunek. Drogę między węzłami i0 i is będziemy zaznaczać jako F=[i0,i1,...,is]. W naturalny sposób możemy określić długość tej drogi jako:

c(F)= i

  • F = [1,...,j] – ciąg węzłów (wskazujących jednoznacznie ciąg strzałek) najkrótszej drogi od węzła 1 do węzła j;

  • dj - odległość od węzła 1 do węzła j;

  • S(j) -zbiór następników węzła j (rysunek 1.2);

  • P(j) - zbiór poprzedników węzła j (rysunek 1.2);

  • (j) - bezpośredni poprzednik węzła j na najkrótszej drodze z a do j.














Rys. Zbiór poprzedników P(j)={1,2,3} i następników S(j)={4,5}.
Rozpatrzymy ogólny przypadek, gdy między obiektami i oraz j mogą występować dwie strzałki: od i do j oraz od j do i, przy czym każda z nich może mieć przypisaną inną liczbę, a więc dopuszcza się, że cij =cji . Pozwala to rozpatrywać zadania, w których rolę miary odległości może odgrywać czas przejazdu, który wcale nie musi być taki sam dla przejazdu w jedną i drugą stronę.









Rys. Dwie drogi między węzłami i oraz j.
Nasze zadanie ujmiemy następująco: w sieci znany jest pewien wyróżniony węzeł, który dalej będziemy oznaczać symbolem a (np. a=1). Należy wyznaczyć najkrótsze drogi z tego węzła do wszystkich innych węzłów oraz obliczyć odległości od węzła do każdego z węzłów.

Zastosujemy tu algorytm Dijkstry I.


Algorytm Dijkstry I

Założenia startowe:

Znamy węzeł a.

Przyjmujemy: Q:={a} i da:=0, a dla pozostałych węzłów ia przyjmujemy: di:=.

ITERACJE

  1   2   3   4


©snauka.pl 2016
wyślij wiadomość