1531834459

<12>

Informatyka +

Rozwiązanie zachłanne samo się nasuwa: każdy element sąsiaduje z dwoma na niższym poziomie, a zatem, by uzyskać drogę o możliwie największej sumie, spośród tych dwóch elementów wybieramy ten, w którym jest większa liczba. Tylko w pierwszym kroku nie mamy wyboru - zaczynamy bowiem od czubka piramidy.

Ćwiczenie 17. Znajdź rozwiązanie zachłanne dla piramidy pokazanej na rys. 2. Czy jest to droga o największej sumie elementów? Sprawdź inne drogi.

A zatem także w przypadku tego problemu, algorytm zachłanny nie znajduje najlepszego z możliwych rozwiązania.

Ćwiczenie 18. Napisz program, który będzie służył do znajdowania zachłannego rozwiązania problemu najdłuższej drogi na piramidzie. Przyjmij, że piramida ma n wierszy (/'-ty wiersz składa się z i elementów). Piramidę przechowuj w tablicy dwuwymiarowej tak, jakby jej poziomy były przesunięte do lewej, czyli i-ty wiersz tablicy będzie zawierał / elementów. Odpowiedz najpierw, które elementy w wierszu (/'+l)-szym będą sąsiednie dla k-tego elementu w wierszu /-tym.

Rysunek 2.

Piramida z wagami

Teraz mamy nieco trudniejsze zadanie.

Ćwiczenie 19. Drogę na piramidzie o największej sumie można znaleźć zaczynając jej szukać nie od wierzchołka piramidy, ale od podstawy piramidy. Postaraj się zaproponować taką metodę. Podpowiemy Ci tylko, że w tej metodzie są rozważane jednocześnie wszystkie drogi kończące się na ostatnim poziomie, następnie na poziomie przedostatnim itd. aż do wierzchołka piramidy. Jeśli już znajdziesz taki algorytm, to napisz dla niego program, korzystając ze wskazówek umieszczonych w ćwicz. 18.

2.5 INNE PRZYKŁADY UŻYCIA METODY ZACHŁANNEJ Dobór w trwałe pary

Osoby z dwóch równolicznych grup mają połączyć się w pary, które nie powinny rozpaść się zbyt szybko (np. taneczne lub małżeńskie). Każda z osób ma skrystalizowane preferencje wobec wszystkich osób w drugiej grupie. Strategia zachłanna w tym przypadku oznacza, że kolejno każda osoba z jednej grupy dobiera sobie z drugiej grupy najbardziej preferowanego partnera. Takie postępowanie może zakończyć się skompletowaniem wszystkich par tylko wtedy, gdy różne są największe preferencje wszystkich osób, czyli gdy nie ma dwóch osób, które umieściły na pierwszym miejscu tę samą osobę. Na ogół w każdej grupie są osoby bardziej łubiane niż inne. Jak więc postępować, nie rezygnując jednak zbytnio ze swoich największych preferencji? Wystarczy nieco zmodyfikować tę prostą strategię zachłanną - jeśli nasz najlepszy wybór zostaje odrzucony przez wybranego przez nas partnera (gdyż otrzymał propozycję od osoby, którą bardziej preferuje), to wybieramy następną abę w kolejności naszych preferencji. Okazuje się, że takie postępowanie prowadzi do układu trwałyi

¹ pewnym sensie). Problem ten jest szczegółowo opisany w rozdz. 11 w książce [6J.