To jest stara wersja strony!


LAB: Wprowadzenie do środowiska ECLiPSe

ECLiPSe jest jednym ze środowisk do programowania z ograniczeniami. Zapewnia ono szerokie możliwości tworzenia własnych ograniczeń oraz doboru właściwego sposobu poszukiwania rozwiązania. Składnia języka ECLiPSe jest oparta o Prolog. Istotne różnice opisane są w następującym przewodniku: http://eclipseclp.org/doc/tutorial/tutorial023.html.

1. Przed laboratorium

Zapoznać się z ideą algorytmów branch and bound.

2. Podstawy środowiska

Proszę utworzyć plik o poniższej zawartości (tradycyjnie pliki z kodem ECLiPSe mają rozszerzenie .ecl):

:- lib(ic).
 
sendmore(Digits) :-
        % zmienne 
        Digits = [S,E,N,D,M,O,R,Y],
 
        % przypisanie dziedziny
        Digits :: [0..9],
 
        % Ograniczenia
        alldifferent(Digits),
        S #\= 0,
        M #\= 0,
                     1000*S + 100*E + 10*N + D
                   + 1000*M + 100*O + 10*R + E
        #= 10000*M + 1000*O + 100*N + 10*E + Y,
 
        % szukanie rozwiązania
        labeling(Digits).

Opis programu

Jest to program rozwiązujący zagadkę SEND+MORE=MONEY.

Przed uruchomieniem przeanalizuj działanie programu. Pierwsza linijka informuje, że będziemy korzystać ze standardowej biblioteki dla dziedzin skończonych. Predykat sendmore Najpierw unifikuje Digits z listą zmiennych wykorzystywanych do opisu problemu. Następnie zmiennym przypisywana jest dziedzina (liczby całkowite od 0 do 9).

Kolejnym etapem jest określenie ograniczeń. predykat alldifferent zapewnia, że wszystkie zmienne będą różne. Następnie wykorzystywane są operatory #\= oraz #= określające odpowiednio relację różności i równości. Istnieją różwnież analogiczne operatory większości i mniejszości, należy jednak pamiętać o znaku # na początku operatora.

Ostatnia linijka powoduje rozpoczęcie wyszukiwania rozwiązania.

Uruchamianie programu

Uruchom eclipse poleceniem tkeclipse.

Wybierz File>Compile i wskaż utworzony plik.

Wywołaj w Query entry predykat sendmore:

sendmore(Digits)

Zwróć uwagę, aby na liście rozwijanej z lewej strony wybrany był moduł eclipse.

Aby sprawdzić, czy nie istnieje więcej rozwiązań, wciśnij przycisk more.

Alternatywna wersja

Problem SEND + MORE = MONEY można też opisać w alternatywny sposób wprowadzając przeniesienia. Dodaj je do modelu

        Carries = [C1,C2,C3,C4],
        Carries :: [0..1],

i przepisz ograniczenia tak, aby je wykorzystywały. Sprawdź poprawność porównując z poprzednią wersją.

Kolorowanie mapy

Na podstawie ostatniego programu napisz predykat rozwiązujący problem kolorowania mapy Australii. Dwa sąsiednie stany muszą mieć różne kolory. Czy trzy kolory wystarczą do pokolorowania mapy?

Przydział zasobów

Ważną klasą problemów rozwiązywaną przez programowanie z ograniczeniami jest przydział zasobów. Przykładowy problem można znaleźć na tej stronie. Poniżej znajduje się zaczerpnięty z niej kod:

:- lib(ic).
:- lib(ic_cumulative).
:- lib(branch_and_bound).
:- lib(lists).
 
schedule(Ss, End,Capacity) :-
        length(Ss, 7),
        Ds = [16, 6,13, 7, 5,18, 4],
        Ss :: 1..30,
 
        Rs = [ 2, 9, 3, 7,10, 1,11],
        End :: 1..50,
 
        after(Ss, Ds, End),
        cumulative(Ss, Ds, Rs, Capacity),
        append(Ss, [End], Vars),
 
        minimize(labeling(Vars),End).
 
after([], [], _).
after([S|Ss], [D|Ds], E) :- E #>= S+D, after(Ss, Ds, E).

Dany jest zbiór zadań do wykonania (ich czasów oraz potrzebnych zasobów) oraz ograniczona liczba zasobów. zasoby są niewyczerpywalne – jest to np. liczba sal w budynku albo maszyn w fabryce. Zadaniem jest tak ustalić początki wykonania, żeby zadanie skończyło się możliwie jak najszybiciej.

Sprawdź wynik działania programu dla ograniczenia wynoszącego 13. Dodaj nowy zasób (procesy potrzebują go odpowiednio 1, 2, 3, 4, 5, 6, 7) z ograniczeniem 8. Jakie jest wyjście programu?

Co należałoby zmienić w programie, jeśli maszyny wymagałyby przerwy technologicznej o zadanej długości pomiędzy zadaniami? Nanieś odpowiednie zmiany i sprawdź wyniki.

W tym momencie wszystkie predykaty użyte w programie (prawdopodobnie z wyjątkiem minimize) powinny być zrozumiałe. Predykat minimize pochodzi z biblioteki branch_and_bound i minimalizuje cel zadany pierwszym argumentem ze względu na zmienną podaną jako drugi argument. Używaną techniką jest metoda branch and bound – po każdym znalezieniu rozwiązania do ograniczeń jest dodawane nowe ograniczenie na minimalizowaną zmienną. Szczegóły opisane są na tej stronie.

3. Problem n hetmanów

Trochę bardziej zaawansowane możliwości systemu ECLiPSe prezentuje program rozwiązujący problem n hetmanów.

:- lib(ic).
 
queens(N, Board) :-
	length(Board, N),
	Board :: 1..N,
	( fromto(Board, [Q1|Cols], Cols, []) do
	    ( foreach(Q2, Cols), count(Dist,1,_), param(Q1) do
		noattack(Q1, Q2, Dist)
	    )
	).
 
noattack(Q1,Q2,Dist) :-
	Q2 #\= Q1,
	Q2 - Q1 #\= Dist,
	Q1 - Q2 #\= Dist.

Opis programu

Po pierwsze, model zawiera pętle (fromto, foreach, count, param). Umożliwiają one bardziej zwarty zapis ograniczeń. Pod drugie, brakuje użycia predykatu label, przez co nie zostanie znalezione żadne rozwiązanie.

Ćwiczenie

Proszę zapisać do pliku i wykonać powyższy kod. Co pojawia się w oknie wyników?

Okazuje się, że propagacja ograniczeń przy określaniu modelu nie jest wystarczająca i potrzebne jest przeszukiwanie. Najprostsze przeszukiwanie realizowane jest przez predykat labeling. Przeszukuje ono zmienne od początku listy do końca i próbuje przypisać kolejne liczby począwszy od najmniejszej. Spróbuj zastosować to przeszukiwanie (było używane we wcześniejszych przykładach). Ile czasu potrzeba, aby wyszukać rozwiązanie dla planszy 24×24?

Jedną z heurystyk, jakie można zastosować jest wybór najbardziej ograniczonej zmiennej (mającej najmniej liczną dziedzinę). Opis kluczowego predykatu delete znajduje się tutaj.

:- lib(ic_search).
labeling_b(AllVars) :-
        ( fromto(AllVars, Vars, VarsRem, []) do
            delete(Var, Vars, VarsRem, 0, first_fail), % wybór zmiennej
            indomain(Var)                              % wybór wartości
        ).

Porówanaj czasy działania dla różnych wielkości planszy. Czy druga metoda przeszukiwania jest zawsze lepsza od pierwszej?

Trzecia metoda to wybór środkowych zmiennych w pierwszej kolejności. Hetman na środku planszy atakuje więcej pól, przez co szybciej możliwe będzie wykrycie niepoprawnego rozstawienia. Skompiluj poniższy kod:

:- lib(lists).
 
middle_first(List, Ordered) :-
        halve(List, Front, Back),
        reverse(Front, RevFront),
        splice(Back, RevFront, Ordered).
 
labeling_c(AllVars) :-
        middle_first(AllVars, AllVarsPreOrdered), % static var-select
        ( foreach(Var, AllVarsPreOrdered) do
            indomain(Var)                         % select value
        ).

Przeanalizuj działanie predykatu middle_first. Jak zachowywałby się predykat labeling_c, gdyby pętla przebiegała po AllVars?

Zanim przetestujemy szybkość działania z nowym wyborem zmiennych, zmodyfikujmy predykat queens tak, aby mógł obsługiwać dowolną metodę wyszukiwania. Dodaj w tym celu dodatkową zmienną Labeling oraz zmodyfikuj wywołanie szukania tak, aby korzystało z nazwy predykatu podanej w tej zmiennej. Podpowiedź: użyj predykatu apply/2.

Sprawdź, po zmianach kod dalej działa, wywołując zmodyfikowany predykat. Następnie użyj predykatu benchmark do sprawdzenia szybkości działania:

:- lib(util).
 
benchmark :-
        ( for(I, 4, 26, 2) do
            write(I),
            util:time(queens(I, _, labeling)),
            util:time(queens(I, _, labeling_b))
            util:time(queens(I, _, labeling_c))
        ).

Limity dla metod (największa, do której szybko liczą się wszystkie o rozmiarze parzystym/największa, dla której szybko się liczy):

  • naiwna: 26 / 26
  • najbardziej ograniczona zmienna: 86 / 160
  • najpierw środkowe: ? / ?
  • najbardziej ograniczona, możliwie najbliższa środkowi zmienna: ? / ?
  • jw, z wyborem środkowych wartości zmiennej ? / ?

Zadania fakultatywne

  1. Wybróbuj swoje własne heurystyki dla problemu n hetmanów. Porównaj ich szybkość działania z tymi zaproponowanymi w ćwiczeniu.
  2. Spróbuj znaleźć możliwie duże plansze, na których szybko działają heurystyki z ćwiczenia. Możesz do tego celu wykorzystać (odpowiednio zmodyfikowany) poniższy predykat:
fll :- writeln('NOT OK'), !.
 
time_is_acceptable :-
        ( for(I, 4, 120, 2) do
            writeln(I),
            timeout:timeout(
                           (!, queens(I, _, labeling), writeln('OK')),
                           2,
                           fll)
        ).
pl/prolog/prolog_lab/csp_eclipse.1360071621.txt.gz · ostatnio zmienione: 2019/06/27 15:59 (edycja zewnętrzna)
www.chimeric.de Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0