1

Wykład IX

Metody algorytmiczne

Algorytmy i struktury danych
Wyższa Szkoła Biznesu
Semestr  III    Informatyka 
stosowana

2

Wiemy już prawie 

wszystko, ale...

Wydaje  się,  że  możemy  teraz  dalej  pomyślnie  podążać 

naprzód w naszym algorytmicznym znoju.

– Wiemy jaką strukturę mają algorytmy i jak urządzić 

obiekty, którymi manipulują; 

– Wiemy  również,  jak  je  zapisać,  aby  wykonał  je 

komputer (języki programowania). 

– Możemy  zatem  powiedzieć  naszemu  procesorowi, 

co i kiedy ma robić.

Byłaby to jednak nazbyt naiwna ocena sytuacji i wkrótce 

zobaczymy  rozmaite  tego  przyczyny.  Jedna  z  trudności 

tkwi  w  fakcie,  że  nie  podaliśmy  żadnych  metod, 

których dałoby się użyć do wymyślenia algorytmu.

3

Od kawałków do całości

Łatwo się opowiada o  konstrukcjach,  z których 
może  korzystać  algorytm  (czyli  o  kawałkach,  z 
których  może  się  składać),  ale  musimy 
powiedzieć 

nieco 

więcej 

o 

sposobach 

zabierania  się  do  zbudowania  całości  z  tych 
kawałków.
Na  tym  wykładzie  dokonamy  przeglądu  kilku 
całkiem  ogólnych  metod  algorytmicznych, 
których  może  użyć  projektant  do  znalezienia 
rozwiązania zadania algorytmicznego.

4

Tworzenie algorytmów

to zadanie twórcze

Trzeba wszak zauważyć, że na obmyślanie przepisów nie ma 

dobrych  przepisów  Każde  takie  zadanie  stanowi  ambitne 

wyzwanie dla projektanta algorytmów.
Jedne zadania są proste, inne skomplikowane, a w wypadku 

jeszcze  innych  nawet  nadzieja  na  ich  rozwiązanie  jest 

złudna.
Jedyne  zatem  co  możemy  pokazać  to,  że  pewne  algorytmy 

całkiem zgrabnie wypływają z pewnych ogólnych wzorców.
Morałem  niech  będzie  to,  że  projektant  algorytmów 

może  odnieść  korzyść  wypróbowując  właśnie  te 

wzorce  w  pierwszej  kolejności.  Jednak  z  całą  pewnością 

projektowanie  algorytmów  jest  zajęciem  twórczym,  które 

niekiedy może wymagać naprawdę ogromnej pomysłowości.

5

Poszukiwania i wędrówki

W  wielu  zadaniach  algorytmicznych  powstaje  potrzeba 

obejścia wszystkich elementów pewnej struktury.
Czasami  struktura  jest  po  prostu  jedną  z  jawnie 

dostępnych w algorytmie struktur danych;
Innym razem jest to jakaś struktura pośrednio w czymś 

zawarta,  której  być  może  nie  da  się  naprawdę 

„zobaczyć”, ale która kryje się gdzieś pod powierzchnią;
Czasami szuka się w tej strukturze czegoś szczególnego 

(„kto jest kierownikiem działu łączności z klientami?”);
Albo  też  pewną  pracę  należy  wykonać  w  każdym 

punkcie („oblicz średnią ocen wszystkich studentów”).

6

Przykłady

Na  przykład  widać  od  razu,  że  proste  zadanie 

sumowania  zarobków  z  jednego  z  poprzednich 

wykładów wymaga łatwego przejścia po danej liście 

pracowników.
Z drugiej  strony, o zadaniu, które dotyczyło jedynie 

pracowników zarabiających więcej niż ich kierownicy 

(patrz wykład: Algorytmy i dane), można pomyśleć, 

że  wymaga  ono  obejścia  wyimaginowanej  tablicy 

dwuwymiarowej 

o 

wierszach 

i 

kolumnach 

odpowiadających 

poszczególnym 

pracownikom. 

Wykonując  to  obejście  poszukujemy  pewnych  par 

pracownik-kierownik.

7

Dobieramy odpowiednią

metodę obejścia

W  takich  przypadkach  zadanie  polega  na 

znalezieniu  najbardziej  naturalnego  sposobu 

obejścia 

struktury 

danych 

(jawnej 

bądź 

niejawnej),  z  którą  ma  się  do  czynienia, 

i wyprowadzeniu algorytmu właśnie stąd.
Kiedy  w  grę  wchodzą  wektory  i  tablice,  wtedy 

pojawiają się  zwykle  pętle i  zagnieżdżone  pętle, 

co wyjaśniono na wykładzie Algorytmy i dane.
Kiedy w grę wchodzą drzewa, wtedy pojawia się 

rekurencja,  tak  jak  w  przykładzie  z sortowaniem 

drzewiastym (ten sam wykład).

8

Pomysł nie zawsze jest 

oczywisty

Co  prawda,  pomysł  leżący  u  podstaw  algorytmu 

sortowania  drzewiastego  jest  dosyć  subtelny  i  nie 

można  nań  wpaść  wymyślając  po  prostu  najlepszą 

strukturę  sterowania  do  obejścia  danej  struktury 

danych.
Jeśli  już  jednak  trafi  się  na  ten  pomysł,  to 

drobnostką  jest  zdanie  sobie  sprawy  z  tego,  że 

składanie  odwiedzin  za  drugim  przejściem,  w 

którym  elementy  wypisywane  są  według  porządku, 

nie  jest  niczym  więcej  niż  pewnym  sposobem 

obejścia drzewa binarnego, skąd nietrudno dojść do 

konkluzji, że należy użyć rekurencji.

9

Sposoby obchodzenia 

drzew

Obejście  wynikające  z  przyjęcia  rekurencyjnej  trasy 

lewostronnej  (sortowanie  drzewiaste)  bywa  czasami 

nazywane  poszukiwaniem  w  głąb  z  nawracaniem,  jako 

że  procesor  „zanurza  się”  w  drzewo  próbując  dostać  się 

najgłębiej,  jak  można,  a  kiedy  nie  może  już  dalej  iść, 

nawraca  niechętnie,  stale  usiłując  nurkować  na  nowo. 

Jedyną  dodatkowa  cechą  jest  tu  wymaganie,  aby 

nurkować jak najbardziej na lewo.
Są też inne sposoby obchodzenia drzew, z których jeden, 

dualny  wobec  poszukiwania  w  głąb,  otrzymał  miano 

poszukiwania  wszerz.  Obchodzenie  wszerz  oznacza,  że 

wyczerpuje się kolejno poziomy drzewa - najpierw korzeń, 

potem całe jego potomstwo, następnie ich potomstwo itd.

10

Poszukiwanie - 

Przykładowe zadania

Wiele 

ciekawych 

zadań 

algorytmicznych 

obraca się wokół pojęć geometrycznych, takich 
jak  punkty,  linie  i  odległości,  i  stanowi  zatem 
część  obszaru  zagadnień  znanych  jako 
geometria obliczeniowa.
Wiele  problemów  w  tej  dziedzinie  wydaje  się 
wzrokowo 

zwodniczo 

„łatwymi” 

do 

rozwiązania,  stanowią  one  jednak  prawdziwie 
ambitne zadanie dla projektantów algorytmów. 

11

Oto jedno z prostszych 

zadań

Przypuśćmy,  że  mamy  prosty  wielokąt  wypukły 

jak  na  rys.  (następny  slajd)  i  że  interesuje  nas 

znalezienie  takich  dwóch  punktów  na  jego 

obwodzie, które dzieli największa odległość.
Przyjmujemy, że wielokąt jest przedstawiony jako 

ciąg współrzędnych <X,Y> jego wierzchołków, w 

kolejności  zgodnej  z  ruchem  wskazówek  zegara. 

Jako  że  największa  odległość  wystąpi  dla  dwóch 

wierzchołków,  nie  ma  potrzeby  zwracania  uwagi 

na  żadne  inne  punkty  leżące  wzdłuż  boków 

wielokąta różne od wierzchołków.

12

Dwa przykładowe 

wielokąty wypukłe

Banalne  rozwiązanie  polegałoby  na  zbadaniu,  w  jakimś 

porządku, 

wszystkich 

par 

wierzchołków 

i 

przechowywałoby  w  zmiennych  bieżące  maksimum  i 

parę, która to maksimum osiąga.

13

Najprostsze rozwiązanie – 

więcej szczegółów

Dla  każdej  nowej  rozważanej  pary  w  prosty  sposób 

oblicza  się  odległość,  nową  odległość  porównuje  się  z 

bieżącym  maksimum  i  uaktualnia  się  zmienne,  jeśli 

okaże się, że jest ona większa, co oznacza, że stanowi 

właśnie nowe maksimum.
Jeśli rozważymy przez chwilę to rozwiązanie, stanie się 

jasne, że w istocie obchodzimy wyimaginowaną tablicę, 

w  której  każdy  wiersz  i  każda  kolumna  odpowiadają 

pewnemu  wierzchołkowi.  Wyimaginowany  element 

danych  tkwiący  w  pozycji  <I,  J>  tej  tablicy  jest 

odległością między wierzchołkami I a J. Obejścia można 

łatwo  dokonać  przy  pomocy  dwóch  zagnieżdżonych 

pętli.

14

Czy istnieje lepsze 

rozwiązanie ?

W tym rozwiązaniu jednak uwzględnia się o wiele za dużą liczbę 

potencjalnych  par;  czyż  nie  powinno  się  rozważać  tylko 

„przeciwległych” par punktów, takich jak <1,4>, <2,5> i <3,6) 

z rys. a (dwa slajdy wstecz)?
Oznaczałoby  to  obejście  jedynie  wektora  par  „specjalnych”,  a 

nie  tablicy  wszystkich  par,  i  dałoby  oczywiście  w  wyniku 

sprawniejszy algorytm, wymagający zaledwie pojedynczej pętli.
No  cóż,  nie  jest  to  tak  proste,  jak  się  wydaje,  ponieważ 

przeciwległe  pary,  których  sobie  życzymy,  nie  muszą  mieć 

jednakowej  liczby  wierzchołków  po  każdej  stronie;  a  na  tym 

samym  rys.  tylko  w  pkt.  b  pokazano  wielokąt,  w  którym 

maksimum  występuje  dla  sąsiadujących  wierzchołków,  które 

pominąłby  algorytm  rozważający  tylko  pary  o  przeciwległych 

numerach.

15

Lepsze rozwiązanie

w którym rzeczywiście stosuje 

się tylko jedną pętlę i rozważa 

tylko „właściwy” gatunek 

przeciwległych par, 

przedstawiono na rys. obok. 

Najpierw „rysuje” się linię 

prostą wzdłuż krawędzi <1,2>, 

czyli krawędzi między 

wierzchołkami 1 i 2. Następnie 

do wielokąta, z jego drugiej 

strony, stopniowo przysuwa

przysuwa się linię równoległą do poprzedniej dopóty, dopóki 
nie  natrafi  na  jeden  z  wierzchołków.  Za  pierwsze 
przybliżenie  szukanego  maksimum  przyjmuje  się  większą  z 
odległości między tym wierzchołkiem a wierzchołkami 1 i 2.

16

Lepsze rozwiązanie 

(cd.)

Potem  rozpoczyna  się  ruch  w  kierunku  zgodnym  z  obiegiem 

wskazówek  zegara.  Każdy  krok  obejmuje  obrót  jednej  z  dwóch  linii 

tak,  aby  leżała  wzdłuż  krawędzi  następnej  w  tym  kierunku,  i 

dopasowanie drugiej linii tak, aby obie przebiegały równolegle. Którą 

z  linii  obrócić,  a  którą  dopasować,  ustala  się  porównując  wysiłek 

niezbędny do wykonania obrotu; obraca się linię tworzącą mniejszy 

kąt  z  następną  krawędzią.  Po  zakończeniu  obrotu  mamy  nowy 

wierzchołek leżący na właśnie obróconej linii.
Obliczoną  odległość  między  tym  wierzchołkiem  a  wierzchołkiem 

leżącym  na  linii  dopasowanej  porównuje  się,  jak  poprzednio,  z 

bieżącym  maksimum.  Wszystko  to  wykonuje  się  dookoła  całego 

wielokąta.  Wszelkie  akcje  wymagane  przez  ten  algorytm  obejmują 

proste  manipulacje  numeryczne  współrzędnymi  wierzchołków, 

wynikające z elementarnej geometrii analitycznej. Pozostałe rysunki  

ilustrują kolejność przekształceń dokonywanych na tych liniach.

17

W poszukiwaniach 

przydaje się wnikliwość

Wybrano  ten  przykład,  aby  dodatkowo 
zilustrować  fakt,  że  samo  zauważenie 
potrzeby obejścia czegoś i wymyślenie, co 
naprawdę  trzeba  obejść,  jest  ważne  i 
może  stanowić  istotną  pomoc,  ale  nie 
zawsze 

wystarczy 

do 

rozwiązania 

trudniejszych zadań algorytmicznych.
Odrobina  wnikliwości  i  sporo  wiedzy  z 
danej dziedziny nigdy tu nie zawadzą.

18

Dziel i zwyciężaj

Często można uporać się z zadaniem sprowadzając je 
do  mniejszych  zadań  tego  samego  rodzaju  i 
rozwiązując  je.  Później  można  połączyć  te  częściowe 
rozwiązania  w  rozwiązanie  ostateczne  pierwotnego 
zadania.
Jeśli  te  mniejsze  zadania  są  dokładnie  tym  samym 
zadaniem,  z którym  mamy  do  czynienia,  lecz 
postawionym  wobec  „mniejszych”  lub  „prostszych” 
danych,  to  oczywiście  w  algorytmie  można  użyć 
rekurencji.
Nazwa tej metody jest oczywista: dziel i zwyciężaj.

19

„Dziel i zwyciężaj” 

widzieliśmy w przykładzie 

z Wieżami Hanoi

Sam 

pomysł 

widzieliśmy 

już 

pośrednio  w  przykładzie  Wież 
Hanoi:  algorytm  uporał  się  z 
zadaniem 

dla 

N 

krążków 

rozwiązując, 

w 

odpowiednim 

porządku 

i 

kontekście, 

dwa 

zadania dla N-1 krążków.

20

Inny przykład 

zastosowania podziałów i 

zwycięstw

Wyobraź sobie, że wręczono ci książkę telefoniczną o 

porozrzucanych  kartkach  lub  że  -  co  zabrzmi 

poważniej - otrzymałeś nieuporządkowaną listę L. 
Interesuje  nas  nie  posortowanie  listy  L,  lecz  tylko 

znalezienie  jej  najmniejszego  i  największego 

elementu.  Jasne,  że  możemy  po  prostu  raz  przebiec 

tę  listę,  przechowując  w  zmiennych  bieżące 

maksimum  i minimum,  i  cały  czas  porównywać  z 

nimi każdy element.
Algorytm, który teraz podamy, opiera się na strategii 

„dziel  i  zwyciężaj”  i  jest  nieco  lepszy  niż  naiwny 

algorytm wspomniany powyżej.

21

Schemat algorytmu szukania 

minimum i maksimum wg. 

„dziel i zwyciężaj”

(1) jeśli  lista  L  składa  się  z  jednego  elementu,  to  ten 

element  stanowi  zarówno  minimum,  jak  i  maksimum; 

jeśli składa się ona z dwóch elementów, to mniejszy z 

nich stanowi minimum, a większy - maksimum;

(2) w przeciwnym razie wykonaj, co następuje:

(2.1)

podziel listę L na połowy, L

1

 i L

2

;

(2.2)

znajdź ich skrajne elementy MIN1, MAX1, MIN2 

i MAX2;

(2.3)

wybierz mniejszy z MIN1 i MIN2; to właśnie jest 

element minimalny listy L;

(2.4)

wybierz większy z MAX1 i MAX2; to właśnie jest 

element maksymalny listy L.

22

Zastosowanie rekurencji 

wymaga zwrócenia przez 

podprogram wyników

Wiersz  (2.2)  aż  woła  o  wykonanie  go  rekurencyjnie,  jako  że 

występujące tam zadania do rozwiązania są dokładnie zadaniami 

min-i-max dla krótszych list L

1

 i L

2

. 

Zwykła  próba  sklecenia  tej  rekurencji  nastręcza  tylko  pewną 

drobną  trudność:  mianowicie  to,  że  w  tym  miejscu,  w 

przeciwieństwie 

do 

procedury 

Wież 

Hanoi, 

wywołanie 

rekurencyjne  musi  dostarczyć  wyników,  których  trzeba  użyć  w 

dalszej części.
Procesor  musi  w  jakiś  sposób  nie  tylko  zapamiętać  swój  adres 

powrotny  i  to,  jak  przywrócić  w  swym  otoczeniu  sytuację 

poprzedzającą  wyprawienie  się  na  tę  rekurencyjną  wycieczkę, 

ale musi móc przywieźć z powrotem ze swej wyprawy wyniki. W 

tym  przypadku  byłoby  najkorzystniejsze,  gdyby  procesor  mógł 

powrócić  z  rekurencyjnego  wywołania  razem  z  żądanym 

minimum i maksimum.

23

Rekurencyjne min-i-max 

realizujące metodę dziel i 

zwyciężaj

procedura znajdź-min-i-max-w L:
(1)jeśli lista L składa się z jednego elementu, to nadaj MIN i MAX 

właśnie jego wartość; jeśli L składa się z dwóch elementów, to 

nadaj MIN wartość mniejszego z nich, a MAX - większego;

(2)w przeciwnym razie wykonaj co następuje:

(2.1)

podziel listę L na połowy, L

1

 i L

2

;

(2.2)

wywołaj  znajdź-min-i-max-w  L

1

;  umieszczając 

otrzymane w wyniku wartości w MIN1 i MAX1;

(2.3)

wywołaj  znajdź-min-i-max-w  L

2

,  umieszczając 

otrzymane w wyniku wartości w MIN2 i MAX2;

(2.4)

nadaj MIN mniejszą wartość z MIN1 i MIN2;

(2.5)

nadaj MAX większą wartość z MAX1 i MAX2;

(3)

wróć z wartościami MIN i MAX.

24

Nie tylko min i max

Zastosowanie  paradygmatu  „dziel  i  zwyciężaj”  może 

przynieść  wiele  dobrego  przy  sortowaniu  listy,  a  nie 

tylko przy znajdowaniu w niej skrajnych elementów. 
Aby  posortować  listę  L  zawierającą  co  najmniej  dwa 

elementy,  możemy  podobnie  podzielić  ją  na  połówki  L

1

 

i L

2

 i posortować je rekurencyjnie.

Przypadek 

pojedynczego 

elementu 

traktuje 

się 

oddzielnie, tak jak w przykładzie z min-i-max.
Aby  otrzymać  ostatecznie  posortowaną  wersję  listy  L, 

dalej  możemy  scalić  posortowane  połówki.  Aby  scalić 

dwie  posortowane  listy,  w  kółko  wybieramy  i  dołączamy 

do  listy  wynikowej  mniejszy  z  dwóch  elementów  akurat 

znajdujących się na obu początkach list.s

Sposób działania 

algorytmu 

sortowania przez 

scalanie

 

Sortowanie  przez 
scalanie 

jest 

znacznie 

lepsze 

zarówno 

od 

sortowania 
bąbelkowego,  jak 
i drzewiastego.

26

Zachłanne algorytmy i 

budowniczowie kolei

Wiele  zadań  algorytmicznych  wymaga  dostarczenia  wyniku, 

który jest w jakimś sensie najlepszy z odpowiedniego zestawu 

możliwości.
Rozważmy  teraz  sieć  miast  i  leniwego  przedsiębiorcę 

budującego kolej. Przedsiębiorcy zapłacono za takie ułożenie 

torów, aby z każdego miasta można było dotrzeć do każdego 

innego.
W  umowie  nie  ustalono  żadnych  kryteriów,  takich  jak 

potrzeba  wykonania  pewnych  bezpośrednich  połączeń  czy 

największa  dopuszczalna  liczba  miast  leżących  na  drodze 

między każdymi dwoma.
Naszego  przedsiębiorcę,  jako  że  jest  leniwy,  interesuje 

ułożenie  najtańszej  (czyli  najkrótszej)  kombinacji  odcinków 

szyn.

27

Założenia

Przyjmijmy,  że  z  przyczyn  obiektywnych,  takich  jak 
przeszkody  naturalne,  nie  każde  miasto  można 
połączyć 

bezpośrednimi 

odcinkami 

szyn 

ze 

wszystkimi innymi i że odległości podano jedynie dla 
par miast możliwych do bezpośredniego połączenia.
Przyjmijmy 

dalej, 

że 

koszt 

bezpośredniego 

połączenia miasta A z miastem B jest proporcjonalny 
do  odległości  między  nimi.  Co  więcej,  nie 
dopuszczamy 

skrzyżowań 

i 

rozjazdów 

poza 

miastami.

28

Grafy

Taka 

sieć 

nazywa 

się 

grafem 

etykietowanym lub krócej grafem.
Grafy przypominają drzewa, tyle że drzewa 
nie  mogą  „zrastać  się”  gałęziami,  a  więc 
nie  mogą  zawierać  cykli  albo  pętli, 
podczas gdy grafy mogą. 
Przykład grafu miast i jego minimalnej sieci 
kolejowej  widzimy  na  rys.  na  następnym 
slajdzie.

29

Sieć miast i jej 

minimalna rozpinająca 

sieć kolejowa

(Rysunek nie zachowuje proporcji)           Całkowity koszt 63 

30

Minimalne drzewo 

rozpinające

Zauważmy,  że  budowniczemu  zależy  naprawdę  na  tym, 

co nazywamy minimalnym drzewem rozpinającym.
To  takie  drzewo,  na  którym  jest  „rozpięty”  graf  w  tym 

sensie,  że  dociera  ono  do  dokładnie  każdego  z  węzłów 

(w  naszym  przypadku  miast)  i  które  jest  najtańszym  z 

takich drzew w tym sensie, że suma etykiet znajdujących 

się przy krawędziach jest najmniejsza z możliwych.
Żądane  rozwiązanie  musi  być  oczywiście  drzewem, 

gdyż w przeciwnym razie musiałoby zawierać jakiś cykl, 

a leniwy przedsiębiorca mógłby otrzymać tańszą sieć 

kolejową, 

nadal 

łączącą 

wszystkie 

miasta, 

eliminując jeden z odcinków tego cyklu.

31

Metoda zachłanna

Jest  pewne  algorytmiczne  podejście  do  takich  zadań, 

zwane zachłanną metodą.
Zaleca  ono  konstruowanie  minimalnego  drzewa 

rozpinającego  krawędź  po  krawędzi,  w  drodze 

wybierania jako następnej krawędzi zawsze tej, która 

jest najlepsza z punktu widzenia bieżącej sytuacji.
Naprawdę  oznacza  to  przyjęcie  filozofii  rodzaju 

„jedzmy  i  pijmy  dziś,  bo  jutro  może  już  nas  nie 

będzie”.
W  przypadku  rozpinających  sieci  kolejowych  można 

prowadzić  tą  konstrukcję  na  przykład  tak,  jak 

pokazano na rys.

32

Działanie zachłannego 

algorytmu znajdowania min. 

drzewa rozpinającego

33

Sposób poszukiwania 

minimalnego drzewa 

rozpinającego

Zacznijmy 

od 

zdegenerowanego 

drzewa 

składającego się z najtańszej krawędzi grafu. 
W  każdym  kroku  rozbudowujemy  skonstruowane 

dotychczas  drzewo,  dodając  do  niego  najtańszą  z 

krawędzi nie wziętych dotąd pod uwagę, które dają 

nowe drzewo (w szczególności dodanie tej krawędzi 

nie  powinno  doprowadzić  do  powstania  cyklu;  jeśli 

doprowadza  do  tego,  przechodzimy  do  krawędzi 

następnej w porządku rosnących kosztów).
Można wykazać, że ta prosta strategia w rezultacie 

rzeczywiście daje minimalne drzewo rozpinające.

34

Zachłanność nie zawsze 

się opłaca

Zachłanne 

algorytmy 

istnieją 

dla 

ogromnego  mnóstwa  ciekawych  zadań 

algorytmicznych.
Zwykle  można  je  łatwo  wynaleźć  i  w 

niektórych  przypadkach  bywają  bardzo 

intuicyjne.
Trudna  część  polega  zwykle  na  pokazaniu, 

że  zachłanna  strategia  rzeczywiście  działa, 

a jak  zobaczymy  za  chwilę,  są  sytuacje,  w 

których zachłanność zupełnie nie popłaca.

35

Dynamiczne planowanie

i znużeni wędrowcy

Oto  zadanie  podobne  do  znajdowania  minimalnego  drzewa 

rozpinającego, 

ale 

opierające 

się 

zachłannym 

próbom 

rozwiązania.
Dotyczy  ono  również  sieci  miast,  ale  zamiast  leniwego 

budowniczego  kolei  mamy  tu  znużonego  wędrowca,  który  musi 

dostać się z jednego miasta do drugiego.
Chociaż  obaj  mają  przed  sobą  zadanie  do  wykonania  i  chcą 

zminimalizować  jego  ogólny  koszt,  jest  między  nimi  zasadnicza 

różnica: podczas gdy budowniczy ma połączyć siecią torów 

wszystkie  miasta,  wędrowiec  odwiedzi  na  ogół  tylko 

niektóre z nich.
Jest  zatem  jasne,  że  wędrowiec  nie  szuka  minimalnego  drzewa 

rozpinającego. Szuka raczej minimalnej ścieżki, czyli najtańszej 

drogi wiodącej od początkowego miasta do miasta przeznaczenia.

36

Założenia: graf jest 

skierowany, spójny i 

acykliczny

Aby  ułatwić  sobie  prezentację  tego  zadania, 

przyjmiemy,  że  wszystkie  linie  w  grafie  miast  są 

skierowane,  co  oznacza,  że  jeśli  istnieje  jakieś 

bezpośrednie  połączenie  między  tymi  dwoma 

miastami, jest to połączenie w jedną stronę. 
Przyjmiemy  też,  że  graf  jest  spójny,  co  znaczy,  że  z 

każdego  miasta  można  w  końcu  dotrzeć  do  każdego 

innego.
Założymy dalej, że graf miast nie zawiera cykli, tak że 

naprawdę znużony wędrowiec nie będzie narażony na 

błąkanie się w kółko, gdyż takich kółek po prostu nie 

ma. Nasz układ - to skierowany graf acykliczny.

37

Zachłanne podejście do 

zadania

Mamy zatem taki graf i wędrowiec ma dotrzeć z miasta A 
do B.
Zachłanne  podejście  do  tego  zadania  dałoby  w  wyniku 
następującą ścieżkę. Zaczęlibyśmy od A i dodawalibyśmy 
ciągle,  aż  do  osiągnięcia  docelowego  miasta  B,  do 
bieżącej 

częściowej 

ścieżki 

najtańszą 

krawędź 

wychodzącą  z  właśnie  osiągniętego  miasta  i  prowadzącą 
do miasta jeszcze nie odwiedzonego.
Przykład zastosowania tego robiącego naturalne wrażenie 
algorytmu  do  grafu,  w  którym  koszt  minimalnej  ścieżki 
między  A  i  B  wynosi  13  jednostek,  pokazano  na  rys. 
(następny slajd).

38

Algorytm musi być 

bardziej wnikliwy

Nasz  zachłanny  algorytm  znajduje  ścieżkę  o  koszcie  15 

jednostek, co jest nieco gorsze. Zachłanność w tym miejscu 

nie  popłaca,  jako  że  sprytny  algorytm  musi  być 

dostatecznie  wnikliwy,  aby  wybrać  krawędź  o  długości  5 

prowadzącą do C, a potem krawędź o długości 3 do E, mimo 

że taki wybór lokalnie nie wygląda najbardziej obiecująco.

39

Planowanie dynamiczne

Inna,  już  nie  zachłanna,  metoda 
algorytmiczna,  zwana  planowaniem 
dynamicznym,  sprawia,  że  można 
dokonywać  tak  subtelnych  wyborów. 
Planowanie dynamiczne opiera się na 
wysubtelnieniu 

dość 

zgrubnego 

kryterium 

używanego 

przy 

natychmiastowej zachłanności. 

40

Idea planowania 

dynamicznego

Tę  metodę  można  opisać  abstrakcyjnie  w  następujący 

sposób.
Przypuśćmy, 

że 

rozwiązanie 

pewnego 

zadania 

algorytmicznego  ma  składać  się  z optymalnego  ciągu 

wyborów.  Jak  już  wykazaliśmy,  całkiem  możliwe,  że 

wybieranie  z  każdego  lokalnego  ciągu  możliwości 

najbardziej  obiecującego  wariantu  nie  doprowadzi  do 

powstania ciągu optymalnego.
Jednak  często  zdarza  się,  że  można  otrzymać  ciąg 

optymalny rozważając wszystkie kombinacje powstałe z:

a) dokonania konkretnego wyboru
b) znalezienia optymalnej części ciągu pozostałych wyborów.

41

Trzeba poszukać kilku 

ścieżek i je porównać

Na przykład na rys. długość najkrótszej ścieżki wiodącej 

z  A  do  B  jest  najmniejszą  z  trzech  liczb  otrzymanych 

przez  wybranie  najpierw  jednego  z  miast  C,  G  i  D 

(bezpośrednio  osiągalnych  z  A),  a  potem  dodanie  jego 

odległości  od  A  do  długości  najkrótszej  ścieżki 

prowadzącej zeń do B. 
Oznaczywszy długość najkrótszej ścieżki z X do B przez 

L(X), możemy symbolicznie napisać

L(A)=minimum z 5+L(C), 14+L(G), 3+L(D)

(zob.  rys.)  Oznacza  to,  że  możemy  znaleźć  ścieżkę 

optymalną znajdując trzy „mniejsze” ścieżki optymalne, 

a później wykonując kilka dodawań i porównań.

42

Ten proces można 

kontynuować

L(D)=minimum z 7+L(E), 6+L(G), 11+L(C)

Kiedy  już  taki  wywód  doprowadzi  do  wyrażeń 

zawierających  L(B)  (tj.  minimalną  odległość  z B  do 

siebie samego), nie trzeba nam niczego więcej, gdyż 

nawet całkiem wyczerpany wędrowiec wie, że L(B)=0, 

na  mocy  faktu,  że  najlepszym  sposobem  dojścia  z  B 

do B jest po prostu pozostanie tam, gdzie się stoi.
Te  spostrzeżenia  prowadzą  do  algorytmu  planowania 

dynamicznego 

rozwiązującego 

ogólne 

zadanie 

znużonego  wędrowca  (czasami  nazywane  zadaniem 

znajdowania najkrótszej ścieżki).

43

Ogólne rozwiązanie 

zadania poszukiwania 

najkrótszej ścieżki

Jeśli  miastami  są  C

1

,  ...,  C

N

,  a  droga  ma  się 

rozpocząć  w  C

1

  i  skończyć  w  C

N

,  to  algorytm 

wymaga  obliczenia  optymalnej  drogi  częściowej 

L(C

I

),  przedstawiającej  najkrótszą  ścieżkę  z  C

I

  do 

miasta docelowego C

N

 dla każdego I między 1 a N. 

Jednak  L(C

I

)  stanowi  minimum  ze  wszystkich  sum 

postaci

odległość-z-C

I

-do-C

K

 +L(C

K

)

przy  czym  w  obliczaniu  minimum  uwzględnia  się 

wszystkie  miasta  C

K

,  do  których  prowadzą 

bezpośrednio krawędzie z C

I

.

44

Ogólne rozwiązanie 

zadania poszukiwania 

najkrótszej ścieżki 

(cd.)

Ponieważ wszystkie krawędzie są jednokierunkowe, 

a  graf  nie  zawiera  cykli,  możemy  w  ten  sposób 

obliczyć wszystkie L(C

I

) posuwając się z B do tyłu.

Patrząc na rysunek obliczamy najpierw wprost L(F), 

L(E)  i  L(G)  i  otrzymujemy  odpowiednio  7,  5  i  6; 

potem  obliczamy  L(C)  jako  minimum  z  2+L(F)  i 

3+L(E)  (w  tym  wypadku  8);  potem  L(D)  itd.,  aż 

wreszcie 

otrzymamy 

L(A). 

Równocześnie 

powinniśmy  śledzić  tak  skonstruowaną  ścieżkę 

biegnącą  do  tyłu  z  B  do  A,  jest  bowiem  ścieżką 

optymalna, której szukamy.

45

Narzucająca się tu 
rekurencja nie jest 

optymalnym 

rozwiązaniem

Pojawia  się  pokusa  napisania  rekurencyjnej  procedury  opartej 

na obliczaniu L(C

I

) na podstawie L(C

K

) tak, jak opisano powyżej.

A  jednak  byłoby  to  błędem.  Powód  jest  taki,  że  ta  sama 

optymalna ścieżka częściowa może być potrzebna w więcej niż 

jednej  „większej”  ścieżce,  a  naiwny  algorytm  rekurencyjny 

będzie obliczać ją wciąż na nowo.
Na rys.odległości L(E) używa się do obliczania zarówno L(C) jak 

i  L(D),  a  zatem  procesor  wykonujący  naszkicowaną  przed 

chwilą procedurę obliczy tę ścieżkę dwukrotnie.
W  planowaniu  dynamicznym  będzie  właściwe  iteracyjne 

obliczenie  wszystkich  L(C

I

)  w  porządku  wstecznym  i 

przechowanie  ich  w  tablicy,  tak  że  gdy  raz  już  obliczy  się, 

powiedzmy, odległość L(E), to można jej będzie użyć powtórnie 

wyszukując tę wartość w tablicy, a nie obliczając ją na nowo.

46

To nic innego jak daleko 

posunięta metoda „Dziel i 

zwyciężaj”

O  planowaniu  dynamicznym  można  myśleć  jako  o 

strategii  „dziel  i  zwyciężaj”  posuniętej  do 

ostateczności: 

wszystkie 

zadania 

częściowe 

rozwiązuje się w kolejności wzrastania ich rozmiaru, 

a  wyniki  przechowuje  się  w  jakiejś  strukturze 

danych,  tak  aby  ułatwić  otrzymanie  rozwiązań 

większych zadań.
Tę  metodę  można  stosować  do  wielu  znacznie 

bardziej 

wymyślnych 

zadań, 

które 

do 

przechowywania  częściowych  wyników  wymagają 

struktur  danych  bardziej  złożonych  niż  zwykłe 

wektory.

47

Metody algorytmiczne 

-podsumowanie

Jest  niewiele  powszechnie  przyjętych  wzorców 

postępowania,  na  tyle  ogólnych,  aby  można  je 

było nazwać metodami algorytmicznymi.
Większość lepiej znanych metod już opisaliśmy. 
Mimo  to,  nawet  bez  stawiania  sobie  za 

konkretny 

cel 

uzyskania 

ogólnych 

paradygmatów,  informatycy  wciąż  poszukują 

lepszych  metod  rozwiązywania  coraz  to 

trudniejszych zadań algorytmicznych.