ScanImage006 (14)

WPROWADZENIE

Rysunek 1.2 Przykład analizy bardzo dużej liczby połączeń

Obiekty z problemu połączeniowego mogą reprezentować punkty lutownicze, a pary ścieżki drukowane, jak pokazano na wyidealizowanym schemacie połączeń elementów elektronicznych na płytce. Taki rysunek pozwala zauważyć węzły, które nie są ze sobą połączone, ale pamiętajmy, że algorytm operuje nie na rysunku, ale na parach liczb naturalnych. Na rysunku wyróżniono dwa węzły. Czy są one połączone?

Specyfikacje wymienione w poprzednim akapicie zawierają żądanie większej ilości informacji niż ich pierwotne wersje, ale można również zażądać mniej informacji. Możemy po prostu zadać następujące pytanie: „Czy m połączeń wystarczy do połączenia wszystkich n obiektów?”. Ten problem dowodzi, że w celu opracowania efektywnego algorytmu, potrzebujemy często rozumowania na wysokim poziomic dotyczącego abstrakcyjnych obiektów, które przetwarzamy. W tym przypadku można się posłużyć podstawowym twierdzeniem z teorii grafów, z którego wynika, że wszystkie n obiektów będzie połączonych wtedy i tylko wtedy, gdy liczba par wyznaczona przez algorytm połączeniowy wyniesie dokładnie n - l (patrz podrozdział 5.4). Inaczej mówiąc, algorytm połączeniowy nie da w wyniku nigdy więcej par niż n - l, ponieważ każda para napotkana po wyznaczeniu pierwszych n - 1 par będzie już połączona. Podobnie przez drobną przeróbkę tego algorytmu możemy napisać program dający w wyniku swojego działania tylko odpowiedź typu „tak” lub „nie”. Program rozwiązujący problem połączeniowy zamiast wypisywać każdą parę obiektów, które nic były wcześniej połączone, powinien tylko zwiększać licznik. Pozytywną odpowiedź da nam wtedy, gdy licznik osiągnie war-

Wyszukiwarka

Podobne podstrony:
83514 IMGI44 (6) Rysunek 7 Przykład analizy cyklu zamawiania KaHnakroM    Dni 1 2 4
14 Ćwiczenie I2. PRZYKŁAD Analiza szeregu czasowego popytu (wielkości sprzedaży) na dany produkt, a
< 14 >Informatyka + Rysunek 3. Przykładowy labirynt Naszym celem jest podanie algorytmu, który
14 Ćwiczenie I2. PRZYKŁAD Analiza szeregu czasowego popytu (wielkości sprzedaży) na dany produkt, a
wymiany, będące wypadkową bardzo dużej liczby pojedynczych transakcji. Funkcjonowanie rynku wolno
IMG
6 017 (2) 16 1. Siły mifdryatomofte stanów wynosi więc 2n. Wobec bardzo dużej liczby atomów, czy
M045 ująć w pewne reguły. Opierając się na analizie wyników dużej liczby manewrów zatrzymywali swobo
M045 ująć w pewne reguły. Opierając się na analizie wyników dużej liczby manewrów zatrzymywani! swob
12 Wojciech Nowak Rysunek 3. Przykładowe wizualizacje programu e-SWPD - Analizy terenów
14 Wprowadzenie do wydania polskiego funkcji wymaga bardzo dobrej znajomości determinant zdrowia (ró

więcej podobnych podstron