A. Przeszukiwanie (przechodzenie) grafu.

Przyjmujemy, że graf jest reprezentowany przez listę sąsiedztwa (LS) oraz każdy wierzchołek ma pole "odwiedzony".

 

1. Przeszukiwanie grafu wszerz (algorytm BFS - B readth F irst S earch )

 

Pomocniczo wykorzystujemy procedury obsługi kolejki:

CLEAR - utwórz pustą kolejkę

IS_EMPTY - czy kolejka jest pusta?

ENQUEUE - wstaw do kolejki

DEQUEUE - pobierz z kolejki (funkcja)

 

Przechodzenie rozpoczynamy od wierzchołka s. Zakładamy, że graf jest spójny. Jeśli nie należy dodać zewnętrzną pętlę.

 

BFS(s)

for each uÎ V- {s}

u.odwiedzony = false

s.odwiedzony = true

CLEAR

ENQUEUE(s)

while not IS_EMPTY

u = DEQUEUE

//wykorzystaj u

for each vÎLS[u]

if not v.odwiedzony then v.odwiedzony = true

ENQUEUE(v)

 

 

2. Przeszukiwanie grafu wzdłuż (algorytm DFS - D eep F irst S earch )

DFS(s) { Przechodzenie rozpoczynamy od wierzchołka s.}

for each uÎ V-{s}

u.odwiedzony = FALSE

s.odwiedzony = TRUE

DFS_V(s)

 

DFS_V(u);

//wykorzystaj u

u.odwiedzony = true

for each vÎLS[u]

if not v.odwiedzony then DSF_V(v)

 

 

B. Minimalne drzewo rozpinające.

 

Algorytm Kruskala.

Danymi dla tego algorytmu są: zbiór wierzchołków grafu (V) i lista jego krawędzi (LK) uporządkowana rosnąco ze względu na wagi. Wynikiem jest zbiór MST (Minimal Spanning Tree) zawierający krawędzie tworzące drzewo rozpinające o minimalnej sumie wag krawędzi.

 

Pomocniczo wykorzystamy procedury obsługi zbiorów rozłącznych MAKE_SET,FIND i UNION.

 

Przedstawiony algorytm należy do klasy algorytmów zachłannych.

 

MST_KRUSKAL

MST = {} {zbiór pusty}

for each vÎV

MAKE_SET(v)

for each <u,v> Î LK

if FIND(u) <> FIND(v) then

MST = MST È {<u,v>}

UNION(u,v)

 

Złożoność O(|E| log|E|).

 

Inny algorytm został zaproponowany przez Prima.

Dane to: zbiór wierzchołków grafu (V), każdy wierzchołek v jest wzbogacony o dwa pola: prev - wskazuje wierzchołek drzewa z którym łączy się v, pr - priorytet, czyli odległość wierzchołka od już zbudowanej części drzewa. Algorytm wykorzystuje kolejkę priorytetową wierzchołków uporządkowaną według rosnącego pola pr i listę sąsiedztwa (LS).

Dodatkowe operacje kolejki:

IN_QUEUE (v) - czy element v jest w kolejce

MOD_PRIORITY(v, prior) - ustaw nowy priorytet elementu v i przebuduj kolejkę.

Budowę drzewa rozpoczyna się od wskazanego wierzchołka startowego s.

 

Pomocnicza operacja to:

INIT (s)

for each vÎV-{s}

v.pr =

ENQUEUE(v)

s.pr = 0 s.prev = null ENQUEUE(s)

 

MST_PRIM(s)

INIT(s)

while not IS_EMPTY

u=DEQUEUE

for each vÎ LS(u)

if IN_QUEUE(v) and (w<u,v> < v.pr)

v.prev = u

MOD_PRIORITY(v, w<u,v>)

 

Złożoność obliczeniowa: O(|E| log |V|).

Tym razem MST jest zapisane w sposób niejawny - poprzez pola prev.

 

C. Najkrótsza ścieżka między dwoma wierzchołkami.

 

Algorytm Dijkstry.

Zakładamy, że mamy ważony graf skierowany o nieujemnych wagach krawędzi. Należy znaleźć najkrótszą drogę od źródła s do ujścia w. Danymi do tego algorytmu jest lista sąsiedztwa grafu(LS- z zapisanymi wagami krawędzi). Dodatkowymi danymi związanymi z każdym węzłem (należącym do zbioru V) są: pr - priorytet wierzchołka czyli odległość od źródła, oraz prev - węzeł poprzedzający na najkrótszej ścieżce. Wykorzystujemy zbiór S - węzłów już wykorzystanych oraz kolejkę priorytetową (uporządkowaną według niemalejącej odległości od źródła).

Pomocnicze operacje:

INIT(s) // patrz wyżej

 

RELAX(u,v)

if v.pr > u.pr + w<u,v>

then MOD_PRIORITY(v, u.pr + w<u,v>)

v.prev=u

 

DIJKSTRA(s,w)

INIT(s)

while not IS_EMPTY

u=DEQUEUE

for each vÎLS[u]

RELAX(u,v)

PRINT(s,w)

 

 

PRINT (s, v)

if v = s then write s

else PRINT (s, v.prev)

write v

 

Jeśli wykorzystamy kolejkę priorytetową wykorzystując kopiec, to złożoność wynosi O(|E|log|V|). Algorytm ten jest bardzo podobny do algorytmów BSF i MST_PRIM.

 

Algorytm Bellmana-Forda.

Tym razem wagi krawędzi mogą być ujemne, ale nie mogą istnieć cykle o ujemnej wadze (algorytm sam wyjrywa czy są takie). Znajdujemy najkrótszą drogę od źródła s do ujścia w. Danymi do tego algorytmu jest lista krawędzi (LK- z zapisanymi wagami krawędzi). Dodatkowymi danymi związanymi z każdym węzłem (należącym do zbioru V) są: pr - priorytet wierzchołka czyli odległość od źródła, oraz prev - węzeł poprzedzający na najkrótszej ścieżce. Tym razem nie wykorzystujemy kolejki więc upraszcza się metoda MOD_PRIORITY (modyfikuje tylko pole pr).

 

BELLMAN_FORD (s,w)

INIT(s)

for i =1 to |V|-1

for each <u,v>ÎLK

RELAX(u,v)

for each <u,v>ÎLK

if v.pr > u.pr +w<u,v>

return false

PRINT(s,w)

return true

 

 

Złożoność tego algorytmu to O(|V|*|E|).

Uwaga: w obu algorytmach można zrezygnować z pola prev - ścieżkę zawsze można odtworzyć korzystając z wyznaczonych wartości pola pr i wag krawędzi.

 

Temat 10. Algorytmy geometryczne.

Pojęcia podstawowe: punkt, odcinek, wektor, prosta.

Problemy:

- po której stronie wektora p->q leży punkt r

- czy punkty x i y leżą po tej samej stronie prostej p-q

- czy punkt r należy do odcinka p-q

- czy podcinki p-q i r-s przecinają się

- czy punkt p leży wewnątrz wielokąta W

a. W jest wielokątem wypukłym

b. W jest dowolnym wielokątem

- Znajdowanie otoczki wypukłej zbioru punktów

a. algorytm Grahama

b. algorytm Jarvisa

c. algorytm przyrostowy

 

Temat 11. Przetwarzanie tekstów.

- wyszukiwanie wystąpień wzorca w tekście

Prosty interfejs do wyszukiwania wzorca w tekście począwszy od wskazanej pozycji:

 

package ssearching;

public interface StringSearcher { public int search(CharSequence text, int from); }

 

a. algorytm naiwny (siłowy - brute force)

 

package ssearching;

public class BruteForceSearcher implements StringSearcher {

private final CharSequence _pattern;

 

public BruteForceSearcher(CharSequence pattern)

{ _pattern = pattern; }

 

public int search(CharSequence text, int from) {

int s = from;

while (s <= text.length() - _pattern.length()) {

int i = 0;

while (i < _pattern.length() && _pattern.charAt(i) == text.charAt(s + i))

++i;

if (i == _pattern.length()) return s;

++s;

}

return -1;

}

}

 

B. algorytm Knutha-Morrisa-Pratta

 

package ssearching;

 

public class KnuthMorrisPrattSearcher implements StringSearcher

{ private final CharSequence _pattern;

 

private final int[] _shuffle;

 

public KnuthMorrisPrattSearcher(CharSequence pattern)

{ _pattern = pattern;

_shuffle = computeShuffle(pattern);

}

 

public int search(CharSequence text, int from) {

int s = from;

int i = 0;

while (s <= text.length() - _pattern.length()) {

i=_shuffle[i];

while (i <_pattern.length() && _pattern.charAt(i) == text.charAt(s + i))

++i;

if (i >=_pattern.length())

return s;

s += Math.max(1,i-_shuffle[i]);

}

return -1;

}

 

private static int[] computeShuffle(CharSequence pattern) {

int[] shuffle = new int[pattern.length()];

shuffle[0]=0;

int tmp=0;

for (int i = 1; i < pattern.length(); ++i){

while (tmp>0 && pattern.charAt(tmp)!= pattern.charAt(i))

tmp=shuffle[tmp];

if(pattern.charAt(tmp)==pattern.charAt(i))

tmp++;

shuffle[i]=tmp;

}

return shuffle;

}

}

C. algorytm Boyera-Moore'a

 

package ssearching;

 

public class BoyerMooreSearcher implements StringSearcher {

/** The supported character set size (ASCII). */

private static final int CHARSET_SIZE = 256;

 

private final CharSequence _pattern;

 

/** The position (0, 1, 2...) of the last occurrence of each character within the pattern. */

private final int[] _lastOccurrence;

 

public BoyerMooreSearcher(CharSequence pattern) {

_pattern = pattern;

_lastOccurrence = computeLastOccurrence(pattern);

}

 

public int search(CharSequence text, int from) {

int s = from;

while (s <= text.length() - _pattern.length()) {

int i = _pattern.length() - 1;

char c = 0;

while (i >= 0 && _pattern.charAt(i) == (c = text.charAt(s + i)))

--i;

if (i < 0)

return s;

s += Math.max(i - _lastOccurrence[c], 1);

}

return -1;

}

 

private static int[] computeLastOccurrence(CharSequence pattern) {

int[] lastOccurrence = new int[CHARSET_SIZE];

for (int i = 0; i < lastOccurrence.length; ++i)

lastOccurrence[i] = -1;

for (int i = 0; i < pattern.length(); ++i)

lastOccurrence[pattern.charAt(i)] = i;

return lastOccurrence;

}

}

D. algortym Karpa-Rabina

 

package ssearching;

 

public class KarpRabinSearcher implements StringSearcher {

private final CharSequence _pattern;

private static int chars=256; //liczność alfabetu

private static int q=8388607; //liczba pierwsza taka że q*chars < MAX_INT

private int cm; //chars do potęgi pattern.length()-1 modulo q

private int hp; //funkcja haszująca wzorca

 

 

public KarpRabinSearcher(CharSequence pattern)

{_pattern = pattern;

hp=h(pattern);

cm=computeCM(pattern.length());}

 

public int search(CharSequence text, int from) {

int s = from;

int ht=h(text.subSequence(s,s+_pattern.length()));

while (s <= text.length() - _pattern.length()) {

if(hp==ht) return s;

if(s < text.length() - _pattern.length())

ht=((ht-text.charAt(s)*cm)*chars+text.charAt(s+_pattern.length()))%q;

s++;

}

return -1;

}

 

private int computeCM(int m)

{ int res=1;

for(int i=1;i<m;i++)

res=(res*chars)%q;

return res;

}

 

private int h(CharSequence s)

{ int res=s.charAt(0);

for(int i=1;i<s.length();i++)

res=(res*chars+s.charAt(i))%q;

return res;

}

}

Prosta klasa do testowania wyszukiwarek:

package ssearching;

import java.io.*;

public class TestStringSearcher

{ void test(){

CharSequence text= "aaaaaaaaaaaaaababababacaaaaaa";

CharSequence pattern = "ababababac";

StringSearcher ss1 = new BruteForceSearcher(pattern),

ss2 = new BoyerMooreSearcher(pattern),

ss3 = new KnuthMorrisPrattSearcher(pattern),

ss4 = new KarpRabinSearcher(pattern);

 

System.out.println(" ss1 = " + ss1.search(text,0));

System.out.println(" ss2 = " + ss2.search(text,0));

System.out.println(" ss3 = " + ss3.search(text,0));

System.out.println(" ss4 = " + ss4.search(text,0));

}

}

 

- kompresja tekstu (kodowanie)

a. algorytm Huffmana

 

I to by było na tyle - na razie, bo parę rzeczy wymaga uzupełnienia.

jr

 

Będę wdzięczny za wszelkie (poza wytykaniem literówek) uwagi dotyczące przedstawionego materiału.