ASD e 02 2005 5

Egzamin ASD

Studia dzienne, 7go lutego 2005

Nazwisko

Nr studenta............Nr grupy

Zadanie 5(10punktów)

Niech A i B będą zbiorami punktów na płaszczyźnie euklidesowej. spełniającymi warunek |A| = |B| = n. Naszym zadaniem jest połączenie wszystkich punktów ze zbioru A z punktami ze zbioru B w pary, tak aby łączna odległość między wszystkimi punktami w parach była jak najmniejsza.

Polecenia:

Podaj kolejno:

(a)    słowny opis strategii (metody) zachłannej rozwiązującej ten problem,

(b)    oszacuj możliwie dokładnie złożoność rozwiązania względem parametru n (przyjmujemy, że operacją dominującą jest wyliczenie odległości między dwoma dowolnymi punktami odpowiednio ze zbioru A oraz B),

(c)    podaj przykład danych wejściowych, dla których wynik zastosowania zaproponowanej strategii zachłannej nie będzie optymalny, jeżeli takie dane istnieją w przeciwnym przypadku uzasadnij fakt, że strategia jest optymalna dla rozważanego problemu.