Page 4 - Informatyka na czasie. Podejście zachłanne w rozwiązywaniu problemów. Podręcznik klasa 3
P. 4
Rozdział 1. Algorytmika i programowanie w języku C++
4.2. Kolorowanie mapy metodą zachłanną
Podejście zachłanne ma zastosowanie nie tylko w algorytmach liczbo-
Warto wiedzieć
W 1853 r. postawiono wych. Dzięki niemu można np. próbować ustalić, ile minimum kolorów
hipotezę, że cztery kolory wystarczy do wypełnienia mapy w taki sposób, aby dwa sąsiednie obsza-
zawsze wystarczą do ry, np. państwa lub województwa (jak na rys. 4.2), miały różne kolory.
pokolorowania każdej
płaskiej mapy. Dowód
sformułowano dopiero
w 1976 r. Dzięki pracy
matematyków problem
udało się zredukować do
jedynie 1936 układów
państw na mapie. Dalsze
obliczenia przeprowadził już
komputer. Dotąd nikomu
nie udało się udowodnić
tego twierdzenia bez użycia
komputera.
Rys. 4.2. Mapa Polski z podziałem na województwa
Warto wiedzieć Ćwiczenie 2
Mapę można pokolorować
trzema kolorami wtedy W pliku, który otrzymasz od nauczyciela (np. mapa.png), znajduje się
i tylko wtedy, gdy mapa konturowa Polski z podziałem na województwa. Pokoloruj ją, ko-
każdy obszar na mapie rzystając z możliwie najmniejszej liczby kolorów tak, aby dwa sąsiednie
(np. województwo) ma
parzystą liczbę sąsiadów. województwa miały różne barwy.
Problem kolorowania Problem kolorowania mapy, zwany też problemem ubogiego karto-
mapy grafa, sformułowano w połowie XIX w. Ówczesna technika drukarska
pozwalała już na drukowanie barwnych map, w szczególności map
politycznych. Liczbę użytych kolorów starano się jednak jak najbardziej
ograniczyć, by zmniejszyć koszty konstrukcji maszyny drukarskiej.
Okazuje się, że do pokolorowania każdej płaskiej mapy wystarczą
cztery kolory. Nie jest jednak znany algorytm takiego optymalnego
kolorowania. Podejście zachłanne dla niektórych map daje tylko rozwią-
zanie przybliżone: spełniony jest warunek różnych barw dla sąsiednich
obszarów, ale w sumie wykorzystuje się np. pięć barw.
4.3. Wydawanie reszty metodą zachłanną
Wyobraź sobie, że podczas zakupów otrzymujesz przy kasie resztę 8 zł
i 45 gr wydaną wyłącznie monetami o wartości 1 zł oraz 5 gr. Łącznie
to 17 monet. Gdyby w ten sposób wydawano resztę w sklepach, trudno
byłoby ją zmieścić w portfelu, a w kasie mogłoby zabraknąć monet.
Dlatego dąży się do tego, aby liczba monet była możliwie jak najmniejsza.
Problem wydawania reszty Jest to tak zwany problem wydawania reszty.
64