Warto znać różne narzędzia programistyczne do rozwiązywania odpowiednich problemów. Czasem się zdarzy, że rozwiązanie danego problemu da się wyrazić w postaci zdań logicznych. Jednym z języków, które pozwalają na programowanie w logice jest Prolog. Aczkolwiek czasem chciałoby się coś więcej.
I tu spotykamy Curry - wariant Haskella, który pozwala na programowanie w logice.
Nie będę jakoś specjalnie wchodził we wszystkie szczegóły języka, ale poruszę moje doświadczenia z próbą rozwiązania problemu znalezienia optymalnego rozstawienia sędziów na zawody Quidditcha.
Zaletą Curry nad Prologiem jest część funkcyjna. Jesteśmy w stanie pisać normalny kod z funkcjami, co często pozwala na optymalizacje, w stosunku do pracy z czystą logiką.
Jeśli chcemy aby silnik logiki znalazł jakąś wartość za nas, to możemy użyć notacji free
path 1 2 = True
path 2 3 = True
path a c = path a b && path b c where b free
Następnie możemy zadać pytanie path 1 3 i uzyskać odpowiedź twierdzącą.
Kolejny feature języka to niedeterminizm. Możemy normalnie używać wzorców w funkcjach, ale w przeciwieństwie do Haskella, po tym jak znajdziemy pasujący wzorzec to nie przerywamy.
oneOf :: [a] -> a -> Bool
oneOf (x:y) x' | x =:= x' = True
oneOf (x:y) x' = oneOf y x'
oneOf [] _ = False
Robiąc zapytanie oneOf [1,1] 1 otrzymam dwie odpowiedzi ‘tak’, a w języku tylko funkcyjnym otrzymałbym jedną.
Jednakże, inne feature’y języka Curry znacznie zależą od kompilatora. Jest kilka różnych, z czego mi udało się skompilować i uruchomić MCC. Bardziej popularny PAKCS pozwala na używanie type class, ale potrzebuje preprocesora, żeby wspierać wszystkie elementy specyfikacji Curry, jak np. wzorce 'default.
Jeśli chcesz poznać język Curry to polecam przeczytać ten PDF.
Mój problem
Tak jak wspomniałem, chcę rozwiązać problem przypisania sędziów do meczy. Moja obecna implementacja jest słaba i do następnych zawodów na pewno będę chciał ją poprawić.
Mam typ Team, którego wartościami są drużyny.
Mam typ Referee, którego wartościami są osoby, które będą sędziować.
Mam typ Game, który wylicza mi mecze od G1...G21.
Mam typ Slot SlotNum Day, gdzie SlotNum to S1..S7, a Day to Sat, Sun.
A następnie deklaruję zdania.
team :: Referee -> Team
hr :: Referee -> Bool
ar :: Referee -> Bool
sr :: Referee -> Bool
snitch :: Referee -> Bool
gameSlot :: Game -> Slot
gameTeam :: Game -> (Team, Team)
W Quidditchu na meczu jest sędzia główny (HR), sędzia zniczowy (SR), znicz i dwóch sędziów pomocniczych (AR).
Można łatwo napisać funkcję odwrotną:
gamesForSlot :: Slot -> [Game]
gamesForSlot s = findall (\g -> gameSlot g == s)
Gdzie g jest de facto wolną zmienną.
Następnie zdefiniowałem zasady, według których wybieram możliwy zestaw sędziów na dany slot.
slotSetup :: Slot -> RefSet
Jak widać ta funkcja zwraca jeden zestaw, ale dzięki temu, że używam niedeterminizmu, to tak naprawdę mogę dostać wiele wyników.
Zaimportowałem moduł AllSolutions i napisałem
allSetups :: IO [[(Game, RefSetup)]]
allSetups = getAllValues setup
setup :: [(Game, RefSetup)]
setup = concat $ map findSetup [Slot x y | y <- [Sat, Sun], x <- [S1,S2,S3,S4,S5,S6,S7]]
findSetup = ...
Do tego dołożyłem funkcję kosztu i zacząłem szukać ustawienia z najmniejszą średnią liczbą sędziowanych meczy na osobę i najmniejszym odchyleniem standardowym - żeby każdy sędzia miał jak najmniej do roboty.
Pod spodem mamy backtracking i system sprawuje się nie najgorzej, ale optymalnego wyniku mi nie znalazł. Jednym z problemów jest to, że mamy ogromne pole do przeszukiwań. Na oko jest to coś w stylu
O(refsPerSlot^(_5_) * 21)
gdzie ^(_5_) oznacza dolną silnię (5 sędziów per mecz). Czyli mamy O(n^5) możliwych kombinacji. Przejście przez tą przestrzeń to nie lada wyzwanie.
Więc będę musiał pomyśleć nad jakąś inną metodą zapisania warunków, żeby zmniejszyć przestrzeń przeszukiwania do tych prawie najlepszych ustawień.