Zastosowania algorytmu BFS

Algorytm Dijkstry: uogólnienie algorytmu BFS przeszukiwania grafu wszerz do grafów z wagami.

ASD240 - Algorytmy i struktury danych – p.2

Zastosowania algorytmu BFS

Algorytm Dijkstry: uogólnienie algorytmu BFS przeszukiwania grafu wszerz do grafów z wagami.

Dane:

graf skierowany

G

= (V, E)

i funkcja wagowa

w

: E → R

+

(BFS:

∀e w(e) = 1

)

ASD240 - Algorytmy i struktury danych – p.2

Zastosowania algorytmu BFS

Algorytm Dijkstry: uogólnienie algorytmu BFS przeszukiwania grafu wszerz do grafów z wagami.

Dane:

graf skierowany

G

= (V, E)

i funkcja wagowa

w

: E → R

+

(BFS:

∀e w(e) = 1

)

2

2

2

2

6

1

5

4

1

1

3

3

s

b

a

d

c

e

f

ASD240 - Algorytmy i struktury danych – p.2

Zastosowania algorytmu BFS

Algorytm Dijkstry: uogólnienie algorytmu BFS przeszukiwania grafu wszerz do grafów z wagami.

Dane:

graf skierowany

G

= (V, E)

i funkcja wagowa

w

: E → R

+

(BFS:

∀e w(e) = 1

)

2

2

2

2

6

1

5

4

1

1

3

3

s

b

a

d

c

e

f

Pytanie 1: Maj ˛

ac dane wierzchołki

u

i

v,

jaka jest

najkrótsza ´scie˙zka z

u

do

v

?

ASD240 - Algorytmy i struktury danych – p.2

Zastosowania algorytmu BFS

Algorytm Dijkstry: uogólnienie algorytmu BFS przeszukiwania grafu wszerz do grafów z wagami.

Dane:

graf skierowany

G

= (V, E)

i funkcja wagowa

w

: E → R

+

(BFS:

∀e w(e) = 1

)

2

2

2

2

6

1

5

4

1

1

3

3

s

b

a

d

c

e

f

Pytanie 1: Maj ˛

ac dane wierzchołki

u

i

v,

jaka jest

najkrótsza ´scie˙zka z

u

do

v

?

Pytanie 2: Maj ˛

ac dany wierzchołek pocz ˛

atkowy

s,

jaka

jest najkrótsza ´scie˙zka z

s

do ka˙zdego z pozostałych

wierzchołków?

ASD240 - Algorytmy i struktury danych – p.2

Algorytm Dijkstry

Wej ´scie:

graf skierowany

G

= (V, E),

wierzchołek

pocz ˛

atkowy

s,

funkcja wagowa

w

: E → R

+

ASD240 - Algorytmy i struktury danych – p.3

Algorytm Dijkstry

Wej ´scie:

graf skierowany

G

= (V, E),

wierzchołek

pocz ˛

atkowy

s,

funkcja wagowa

w

: E → R

+

Dla ´scie˙zki

P

= (v

1

, v

2

, . . . , v

k

)

definiujemy jej

długo´s´c

(wag ˛e)

w

(P ) =

k

−1

P

i=1

w

(v

i

, v

i+1

)

, najkrótsza ´scie˙zka to ´scie˙zka o

minimalnej wadze.

ASD240 - Algorytmy i struktury danych – p.3

Algorytm Dijkstry

Wej ´scie:

graf skierowany

G

= (V, E),

wierzchołek

pocz ˛

atkowy

s,

funkcja wagowa

w

: E → R

+

Dla ´scie˙zki

P

= (v

1

, v

2

, . . . , v

k

)

definiujemy jej

długo´s´c

(wag ˛e)

w

(P ) =

k

−1

P

i=1

w

(v

i

, v

i+1

)

, najkrótsza ´scie˙zka to ´scie˙zka o

minimalnej wadze.

ASD240 - Algorytmy i struktury danych – p.3

Algorytm Dijkstry

Wej ´scie:

graf skierowany

G

= (V, E),

wierzchołek

pocz ˛

atkowy

s,

funkcja wagowa

w

: E → R

+

Dla ´scie˙zki

P

= (v

1

, v

2

, . . . , v

k

)

definiujemy jej

długo´s´c

(wag ˛e)

w

(P ) =

k

−1

P

i=1

w

(v

i

, v

i+1

)

, najkrótsza ´scie˙zka to ´scie˙zka o

minimalnej wadze.

Cel:

wyznaczy´c najkrótsze ´scie˙zki z

s

do ka˙zdego

wierzchołka w

V

\ {s}.

ASD240 - Algorytmy i struktury danych – p.3

Algorytm Dijkstry

Wej ´scie:

graf skierowany

G

= (V, E),

wierzchołek

pocz ˛

atkowy

s,

funkcja wagowa

w

: E → R

+

Dla ´scie˙zki

P

= (v

1

, v

2

, . . . , v

k

)

definiujemy jej

długo´s´c

(wag ˛e)

w

(P ) =

k

−1

P

i=1

w

(v

i

, v

i+1

)

, najkrótsza ´scie˙zka to ´scie˙zka o

minimalnej wadze.

Cel:

wyznaczy´c najkrótsze ´scie˙zki z

s

do ka˙zdego

wierzchołka w

V

\ {s}.

Struktura danych: K

OLEJKA PRIORYTETOWA

: priorytet zale˙zy od

aktualnego przybli˙zenia odległo´sci wierzchołków od
wierzchołka

s

ASD240 - Algorytmy i struktury danych – p.3

Algorytm Dijkstry

Wej ´scie:

graf skierowany

G

= (V, E),

wierzchołek

pocz ˛

atkowy

s,

funkcja wagowa

w

: E → R

+

Dla ´scie˙zki

P

= (v

1

, v

2

, . . . , v

k

)

definiujemy jej

długo´s´c

(wag ˛e)

w

(P ) =

k

−1

P

i=1

w

(v

i

, v

i+1

)

, najkrótsza ´scie˙zka to ´scie˙zka o

minimalnej wadze.

Cel:

wyznaczy´c najkrótsze ´scie˙zki z

s

do ka˙zdego

wierzchołka w

V

\ {s}.

Struktura danych: K

OLEJKA PRIORYTETOWA

: priorytet zale˙zy od

aktualnego przybli˙zenia odległo´sci wierzchołków od
wierzchołka

s

Algorytm odwiedza w pierwszej kolejno´sci wierzchołek w
najbli˙zszej odległo´sci od

s

.

ASD240 - Algorytmy i struktury danych – p.3

Algorytm Dijkstry

Dijkstra

(G = (V, E, w), s)

inicjalizuj pust ˛

a kolejk˛e

Q := ∅

for

u ∈ V − {s}

do

d[u] := ∞

odległo´s´c od

s

d[s] := 0

Wstaw

(s, Q)

while

Q 6= ∅

do

u :=

Extract_MIN

(Q)

element minimalny z kolejki priorytetowej

oznacz

(u)

for

v ∈ S[u]

do

if

v

nieoznaczony i

d[v] > d[u] + w(u, v)

then

d[v] := d[u] + w(u, v)

Wstaw

(v, Q)

ASD240 - Algorytmy i struktury danych – p.4

Algorytm Dijkstry - przykład

2

2

2

2

6

1

5

4

1

1

3

3

s

b

a

d

c

e

f

ASD240 - Algorytmy i struktury danych – p.5

Algorytm Dijkstry - przykład

2

2

2

2

6

1

5

4

1

1

3

3

0

2

3

5

6

4

6

s

b

a

d

c

e

f

ASD240 - Algorytmy i struktury danych – p.5

Algorytm Dijkstry - zło˙zono´s´c

Wykonuje nast ˛epuj ˛

ace operacje:

Wstaw

:

|E|

razy

Extract_MIN

:

|V |

razy

ASD240 - Algorytmy i struktury danych – p.6

Algorytm Dijkstry - zło˙zono´s´c

Wykonuje nast ˛epuj ˛

ace operacje:

Wstaw

:

|E|

razy

Extract_MIN

:

|V |

razy

Ka˙zda z nich zale˙zy od

implementacji kolejki priorytetowej

Q

ASD240 - Algorytmy i struktury danych – p.6

Algorytm Dijkstry - zło˙zono´s´c

Wykonuje nast ˛epuj ˛

ace operacje:

Wstaw

:

|E|

razy

Extract_MIN

:

|V |

razy

Ka˙zda z nich zale˙zy od

implementacji kolejki priorytetowej

Q

Implementacja kolejki

Q

Extract_MIN

Wstaw

Razem

tablica

O

(n)

O

(1)

O

(n

2

)

kopiec

O

(log n)

O

(log n)

O

(m log n)

kopiec Fibonacciego*

O

(log n)

O

(1)

O

(n log n + m)

*nie omawiamy

ASD240 - Algorytmy i struktury danych – p.6

Algorytm Dijkstry - poprawno´s´c

Idea:

Nale˙zy pokaza´c, ˙ze zawsze gdy wierzchołek

u

zostaje

oznaczony,

d

[u]

jest najkrótsz ˛

a odległo´sci ˛

a z

s

do

u.

ASD240 - Algorytmy i struktury danych – p.7

Algorytm Dijkstry - poprawno´s´c

Idea:

Nale˙zy pokaza´c, ˙ze zawsze gdy wierzchołek

u

zostaje

oznaczony,

d

[u]

jest najkrótsz ˛

a odległo´sci ˛

a z

s

do

u.

Niech

δ

(s, v)

b ˛edzie długo´sci ˛

a najkrótszej ´scie˙zki z

s

do

v

w

G.

Fakt.

∀v ∈ V (G) d[v] ≥ δ(s, v)

ASD240 - Algorytmy i struktury danych – p.7

Algorytm Dijkstry - poprawno´s´c

Idea:

Nale˙zy pokaza´c, ˙ze zawsze gdy wierzchołek

u

zostaje

oznaczony,

d

[u]

jest najkrótsz ˛

a odległo´sci ˛

a z

s

do

u.

Niech

δ

(s, v)

b ˛edzie długo´sci ˛

a najkrótszej ´scie˙zki z

s

do

v

w

G.

Fakt.

∀v ∈ V (G) d[v] ≥ δ(s, v)

Dowód:

na tablicy

ASD240 - Algorytmy i struktury danych – p.7

Ograniczenia algorytmu Dijkstry

Problematyczne dane wej´sciowe dla alg. Dijkstry - ujemne
wagi

ASD240 - Algorytmy i struktury danych – p.8

Ograniczenia algorytmu Dijkstry

Problematyczne dane wej´sciowe dla alg. Dijkstry - ujemne
wagi

−2

s

a

b

2

3

3

ASD240 - Algorytmy i struktury danych – p.8

Ograniczenia algorytmu Dijkstry

Problematyczne dane wej´sciowe dla alg. Dijkstry - ujemne
wagi

−2

3

3

2

0

3

2

b

a

s

ASD240 - Algorytmy i struktury danych – p.8

Ograniczenia algorytmu Dijkstry

Problematyczne dane wej´sciowe dla alg. Dijkstry - ujemne
wagi

−2

3

3

2

0

3

2

b

a

s

Wtedy alg. Dijkstry nie działa i trzeba zastosowa´c inny algo-

rytm.

ASD240 - Algorytmy i struktury danych – p.8

Algorytm Dijkstry - podsumowanie

Jest to algorytm zachłanny.

ASD240 - Algorytmy i struktury danych – p.9

Algorytm Dijkstry - podsumowanie

Jest to algorytm zachłanny.

Cechy algorytmu zachłannego:

buduje rozwi ˛

azanie w małych krokach

w ka˙zdym kroku podejmuje decyzj ˛e optymalizuj ˛

ac

pewne zadane kryterium

lokalnie optymalny krok prowadzi do wyznaczenia
globalnego optimum.

ASD240 - Algorytmy i struktury danych – p.9

Algorytm Dijkstry - podsumowanie

Jest to algorytm zachłanny.

Cechy algorytmu zachłannego:

buduje rozwi ˛

azanie w małych krokach

w ka˙zdym kroku podejmuje decyzj ˛e optymalizuj ˛

ac

pewne zadane kryterium

lokalnie optymalny krok prowadzi do wyznaczenia
globalnego optimum.

tzw. „krok zachłanny” to wybór nieodwiedzonego
wierzchołka, który znajduje si ˛e „najbli˙zej” zbioru
wierzchołków ju˙z odwiedzonych z

s

ASD240 - Algorytmy i struktury danych – p.9

Problem podró˙zuj ˛

acego komiwoja˙zera

Komiwoja˙zer chce odwiedzi´c dokładnie jeden raz ka˙zde spo´sród

n

miast i wróci´c do punktu

wyj´scia pokonuj ˛

ac drog ˛e o minimalnym koszcie.

ASD240 - Algorytmy i struktury danych – p.10

Problem podró˙zuj ˛

acego komiwoja˙zera

Komiwoja˙zer chce odwiedzi´c dokładnie jeden raz ka˙zde spo´sród

n

miast i wróci´c do punktu

wyj´scia pokonuj ˛

ac drog ˛e o minimalnym koszcie.

A

38

56

B

C

D

E

122

17

39

67

121

92

111

73

87

59

103

134

89

F

ASD240 - Algorytmy i struktury danych – p.10

Problem podró˙zuj ˛

acego komiwoja˙zera

Komiwoja˙zer chce odwiedzi´c dokładnie jeden raz ka˙zde spo´sród

n

miast i wróci´c do punktu

wyj´scia pokonuj ˛

ac drog ˛e o minimalnym koszcie.

A

38

56

B

C

D

E

122

17

39

67

121

92

111

73

87

59

103

134

89

F

Inaczej: pytamy o cykl zawieraj ˛

acy wszystkie wierzchołki grafu (tzw.

cykl Hamiltona

) o

minimalnej wadze kraw ˛edzi.

ASD240 - Algorytmy i struktury danych – p.10

Problem podró˙zuj ˛

acego komiwoja˙zera

Komiwoja˙zer chce odwiedzi´c dokładnie jeden raz ka˙zde spo´sród

n

miast i wróci´c do punktu

wyj´scia pokonuj ˛

ac drog ˛e o minimalnym koszcie.

A

38

56

B

C

D

E

122

17

39

67

121

92

111

73

87

59

103

134

89

F

Inaczej: pytamy o cykl zawieraj ˛

acy wszystkie wierzchołki grafu (tzw.

cykl Hamiltona

) o

minimalnej wadze kraw ˛edzi.

Sprawdzaj ˛

ac wszystkie cykle Hamiltona mamy

4!/2

mo˙zliwo´sci.

ASD240 - Algorytmy i struktury danych – p.10

Problem podró˙zuj ˛

acego komiwoja˙zera

Komiwoja˙zer chce odwiedzi´c dokładnie jeden raz ka˙zde spo´sród

n

miast i wróci´c do punktu

wyj´scia pokonuj ˛

ac drog ˛e o minimalnym koszcie.

Inaczej: pytamy o cykl zawieraj ˛

acy wszystkie wierzchołki grafu (tzw.

cykl Hamiltona

) o

minimalnej wadze kraw ˛edzi.

Sprawdzaj ˛

ac wszystkie cykle Hamiltona mamy

4!/2

mo˙zliwo´sci.

Ogólnie:

(n − 1)!/2,

a to jest bardzo du˙za liczba, dla

n = 25

wynosi ok.

3, 1 × 10

23

,

co

wymagałoby ok. 10 milionów lat oblicze ´n.

ASD240 - Algorytmy i struktury danych – p.10

Problem podró˙zuj ˛

acego komiwoja˙zera

Komiwoja˙zer chce odwiedzi´c dokładnie jeden raz ka˙zde spo´sród

n

miast i wróci´c do punktu

wyj´scia pokonuj ˛

ac drog ˛e o minimalnym koszcie.

Inaczej: pytamy o cykl zawieraj ˛

acy wszystkie wierzchołki grafu (tzw.

cykl Hamiltona

) o

minimalnej wadze kraw ˛edzi.

Sprawdzaj ˛

ac wszystkie cykle Hamiltona mamy

4!/2

mo˙zliwo´sci.

Ogólnie:

(n − 1)!/2,

a to jest bardzo du˙za liczba, dla

n = 25

wynosi ok.

3, 1 × 10

23

,

co

wymagałoby ok. 10 milionów lat oblicze ´n.

Wielomianowy algorytm dla tego problemu nie jest znany, a problem jest

NP-trudny

, tzn.

znacznie trudniejszy ni˙z wszystkie omawiane na tym wykładzie.

ASD240 - Algorytmy i struktury danych – p.10