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 dwfa 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
Wyszukiwarka
Podobne podstrony:
1. Wprowadzenie Podstawowym i najbardziej naturalnym sposobem komunikacji międzyludzkiej jest mowa.
32281 phoca thumb l slajd17 (8) Różne sposoby połączenia białek błony z dwuwarstwą fosfolipidową 1,2
P1010006 (13) 80 Richard Sheppard jesteśmy przede wszystkim zobowiązani ustalić ciągłość między tymi
Siły grawitacji zwane także siłami powszechnego ciążenia działają między każdymi dwoma ciałami
Poetycki model prozy w dwudziestoleciu międzywojennym (17) wo powieści. O ile w Nietocie żywiołowi p
Rys. 10. Różne sposoby zabezpieczania połączeń śrubowych przed samoczynnym odkręceniem: a) podkładka
ScanImage06 Rys 3 Sposób połączenia miernika MZK-2 przy pomiarach impedancji pętli zwarcia 6
CCF20131114 004 Które pecherze są najbardziej powierzchowne Leczenie kiły 1 .semiotyka-wszystko na r
potencjalnie dostępne dla wszystkich uczestników łańcucha. Transport zapewnia fizyczne połączenie mi
Nie sposób wymienić wszystkich Polaków zasłużonych dla kolejnictwa rosyjskiego. Liczne grupy polskic
DWUDZIESTOLECIE MIĘDZYWOJENNE chronologia i periodyzacja 2 20. ukryte mechanizmy osobowości, ukazywa
więcej podobnych podstron