W kolejnym odcinku serii z Alicją i Bogdanem najpierw ilustrujemy problem dominowania w grafach (kratowych): klasyczny i rzymski. Następnie ilustrujemy znany fakt, że zachłanność nie zawsze się opłaca. Pokażemy mianowicie, że algorytmy zachłanne nie gwarantują uzyskania rozwiązania optymalnego, nawet wówczas gdy problem da się rozwiązać w czasie wielomianowym.
Zagadka 1
Alicja i Bogdan mają działkę kwadratową o boku 100 m, którą odziedziczyli po dziadku. Działka jest podzielona na identyczne grządki-poletka o wymiarze 6,25 m × 6,25 m. Chcą ją zazielenić, sadząc trawę na jak najmniejszej liczbie grządek. Wiedzą przy tym, że jeśli grządka przylega do dwóch obsianych (bezpośrednio lub narożnikowo), to po roku na niej również zaczyna rosnąć trawa. Jaka jest najmniejsza początkowa liczba grządek, na których mogą posiać trawę, tak by zaczęła ona rosnąć na całej działce?