ScanImage008 (5)

WPROWADZENIE

1.2.    Wymień wszystkie różne sposoby połączeń między każdymi dwoma różnymi obiektami dla przykładu z rysunku 1.1.

1.3.    Opisz prostą metodę wyznaczania liczby zbiorów powstałych po zastosowaniu operacji scalania i wyszukiwania do rozwiązania problemu połączeniowego.

1.3. Algorytmy wyszukiwania i scalania

Pierwszym etapem procesu opracowania efektywnego algorytmu rozwiązującego dane zadanie jest zaimplementowanie prostego algorytmu rozwiązującego to zadanie. Jeżeli trzeba rozwiązać kilka konkretnych przypadków danego zadania, które wydają się proste, wówczas nasze zadanie możemy zakończyć prostą implementacją. Jeżeli potrzebny jest bardziej zaawansowany algorytm, wtedy niewyszukana implementacja pozwala skontrolować poprawność na prostych przypadkach oraz stanowi podstawę do opracowania oceny wydajności algorytmu. O wydajność należy' dbać zawsze, ale chwilowo głównym naszym celem będzie opracowanie pierwszego przybliżenia programu. Robimy to po to, aby upewnić się, że program pozwoli prawidłowo rozwiązywać zadanie.

Pierwszymi pomysłem, który' może komuś przyjść do głowy, jest zapamiętywanie gdzieś wszystkich par pojawiających się na wejściu i napisanie funkcji, która przejrzy je wszystkie, aby stwierdzić, czy dana para obiektów jest połączona. My zastosujemy odmienne podejście. Po

p		0	1	2	3	4	5	6	7	8	9
3	4	0	1	2	*	4	5	6	7	8	9
4	9	0	1	2		9	5	6	7	8	9
8	0	0	1	2	9	9	5	6	7	0	9
2	3	0	1	i	9	9	5	6	7	0	9
5	6	0	1	9	9	9		6	7	0	9
2	9	0	1	9	9	9	6	6	7	0	9
5	9	0	1	9	9	9	^;:9	9	7	0	9
7	3	0	1	9	9	9	9	9	9	0	9
4	8	0	1	0	0	m	:©	#	0	0	0
5	6	0	1	0	0	0	0	0	0	0	0
0	2	0	1	0	0	0	0	0	0	0	0
6	1		1		ffi	&	ki:	ii-	iii	iii	■i

Rysunek 1.3

Przykład szybkiego wyszukiwania (wolnego scalania)

Ta sekwencja to zawartość tablicy l d po tym, jak każda z par z lewej strony została przetworzona przez algorytm szybkiego wyszukiwania (program 1.1). Liczby zmieniające się w operacji scalania zaznaczone są na szaro. Podczas przetwarzania pary p-q przypisujemy wszystkim elementom o wartości id(p] war-

pierwsze, liczba par może być na tyle duża, by wykluczyć pomysł zapisywania każdej pary w pamięci w' przypadku praktycznych zastosowań. Po drugie i ważniejsze, nie istnieje narzucająca się (prosta) metoda stwierdzenia, czy dw^fa podane obiekty sąpołączone, nawet jeżeli zapisze się wszystkie pary' w pamięci! Prostą metodę opartą na tym pomyśle będziemy analizować w rozdziale 5. W tym rozdziale jednak zajmiemy się metodami prostszymi, bo służącymi do rozwiązywania mniej złożonego zadania, oraz bardziej efektywnymi, bo nie wymagającymi zapisywania wszystkich par. Wszystkie one są oparte na tablicy liczb naturalnych, z których każda odpowiada innemu obiektowi, reprezentacji danych pozwalającej zaimplementować scalanie i wyszukiwanie.

Tablice należą do najbardziej podstawowych struktur danych. Zajmiemy się nimi szczegółowo w pod-ozdziale 3.2. Teraz skorzystamy z nich w najprostszej formie: założymy a priori, żc rozważamy problem dla nie więcej niż na przykład 1000 liczb. Zadeklarujemy więc tablicę instrukcją a [1000], a do /-tego jej elementu będziemy się odwoływać przez a [ i ], dla 0śi< 1000.

Program 1.1 jest implementacją prostego algorytmu, zwanego algorytmem szybkiego wyszukiwania, który