A. Przeszukiwanie (przechodzenie) grafu.



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

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- Breadth First Search)

 

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 eachuÎ V- {s}

u.odwiedzony = false

s.odwiedzony = true

CLEAR

ENQUEUE(s)

while notIS_EMPTY

u = DEQUEUE

//wykorzystaj u

for eachvÎLS[u]

if notv.odwiedzony thenv.odwiedzony = true

ENQUEUE(v)

 

 

2. Przeszukiwanie grafu wzdłuż (algorytm DFS-Deep First Search)

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

for eachuÎ V-{s}

u.odwiedzony = FALSE

s.odwiedzony = TRUE

DFS_V(s)

 

DFS_V(u);

//wykorzystaj u

u.odwiedzony = true

for eachvÎLS[u]

if notv.odwiedzony thenDSF_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

ifFIND(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

elsePRINT (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)

returntrue

 

 

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.



Последнее изменение этой страницы: 2016-04-23; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.236.212.116 (0.009 с.)