Lab CSP: Podstawowe problemy

W ramach laboratorium będziemy rozwiązywać standardowe problemy pojawiające się w literaturze dotyczącej programowania z ograniczeniami. Zaprogramowane modele będą następnie ulepszane poprzez stosowanie podstawowych technik modelowania w CSP.

Rozgrzewka

Problem n-hetmanów

  • Treść problemu: w jaki sposób na szachownicy o wymiarach nxn umieścić n hetmanów w taki sposób, by żaden z nich nie mógł zbić innego w jednym ruchu (patrz: wikipedia).
  • Ćwiczenia:
    1. Proszę uzupełnić poniższy model problemu n-hetmanów
      %%%%%%%%%%%%% 
      % DZIEDZINA %        
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      % miejsce na dziedzinę           %
      % podpowiedź:                    %
      % var 1..N: x; deklaruje zmienną %
      % o dziedzinie 1..N;             % 
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
        
      %%%%%%%%%%%%%%%%
      % OGRANICZENIA %
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
      % miejsce na ograniczenia                    %
      % podpowiedź:                                %
      % row_i = row_j (-/+) (j - i)                % 
      % opisuje hetmanów stojących na              %
      % tej samej diagonali, gdzie:                %
      % - i,j - numery kolumn                      %
      % - row_n - pozycja hetmana w n-tej kolumnie %
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
        
      solve satisfy; 
        
      %%%%%%%%%%%%%%%%%%%%%%%%
      % PRZYKŁADOWE WYJŚCIE  %
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      % - rows[i] pozycja hetmana w i-tym wierszu %
      % - N - liczba hetmanów                     %
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      output [ if fix(rows[j]) == i then "H" else "." endif ++
        if j == N then "\n" else "" endif | i,j in 1..N]

Przykładowe złożone wyrażenie agregujące:
forall([tablica[i,j] = z | i,j in 1..M, z in 1..N where j < i])
lub równoważnie:
forall(i,j in 1..M, z in 1..N where j < i)(tablica[i,j] = z)

Kolorowanie grafów

  • treść problemu: problem kolorowania grafu polega na przyporządkowaniu wierzchołkowom grafu odpowiednich kolorów tak, aby wierzchołki o wspólnej krawędzi miały różne kolory. W najgorszym przypadku (klika) będzie potrzebne tyle kolorów, ile jest wierzchołków. W przypadku grafu planarnego zawsze wystarczą cztery (sławny dowód matematyczny, warto sprawdzić, dlaczego). Twierdzenie o czterech barwach Kolorowanie na angielskim wiki.
  • Ćwiczenia:
    1. Proszę uzupełnić poniższy model kolorowania grafu (przykładowe dane wejściowe):
%%%%%%%%%%%%%
% PARAMETRY %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Powinny być wczytane z pliku z danymi.%
% Traktujmy graf jako tablicę booli     %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 
%%%%%%%%%%%%% 
% DZIEDZINA %        
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% miejsce na dziedzinę           %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%%%%%%%%%
% OGRANICZENIA %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
% miejsce na ograniczenia                    %
% podpowiedź:                                %
% - warto użyć if'a, by sprawdzić, czy dwa   % 
% wierzchołki są połączone                   %
% - liczba kolorów to może być maksymalny    %
% numer użytego koloru                       %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%%%%%%%
% CEL  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Zminimalizuj użytą liczbę kolorów %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
solve minimize coloursNumber;

%%%%%%%%%%%%%%%%%%%%%%%%
% PRZYKŁADOWE WYJŚCIE  %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% - coloursNumber - liczba użytych kolorów  %
% - nodes - tablica wierzchołków grafu z    %
%           ich kolorami                    %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
output [show(coloursNumber), " colours\n",] ++
       [show(nodes[i]) ++ " " | i in 1..nodesNumber]

Definicja tablicy dwuwymiarowej booli:

array[1..2,1..3] of bool: bool_array = [|true, true, true | true, true, true|];

Konstrukcja warunkowa:

if bool then val1 else val2 endif

Operatory logiczne:

/\ -- i, \/ -- lub, != -- różne, == -- równe 

Globalne ograniczenia

Jedną z najprostszych metod tworzenia dobrego modelu w programowaniu z ograniczeniami jest korzystanie z gotowych globalnych ograniczeń. Dzięki wyspecjalizowanym algorytmom i implementacji są one w stanie lepiej wykorzystać informacje na temat struktury problemu od ograniczeń na pojedynczych zmiennych. Niektóre z globalnych ograniczeń są nawet w stanie zamodelować dynamiczne zachowanie systemu, np. ograniczenie cumulative uniemożliwia równoczesne wykorzystanie zasobu przez kilka zadań. W MiniZinc, aby korzystać z globalnego ograniczenia, należy je najpierw zaimportować, np. aby korzystać z ograniczenia cumulative należy wcześniej dopisać do kodu linijkę:

include "cumulative.mzn";

Sudoku

  • Treść problemu: należy zaimplementować solver sudoku (patrz: wikipedia)
  • Ćwiczenia:
    1. Proszę uzupełnić poniższy model sudoku:
      %%%%%%%%%%%%%%%%%
      % PRZYPOMNIENIE %
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      % Coś tu jeszcze powinno być.%
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      
      %%%%%%%%%%%%% 
      % DZIEDZINA %        
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      % miejsce na dziedzinę, podpowiedź:  %
      % dwie oddzielne tablice, jedna      %  
      % odpowiedzialna z stan początkowy;  %
      % druga przechowuje zmienne decyzyjne% 
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      
      %%%%%%%%%%%%%%%%
      % Ograniczenia %
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      % - constraint alldifferent(tablica zmiennych);  %
      % globalne ograniczenie, w którym wszystkie      %
      % zmienne z tablicy muszą mieć różną wartość     %
      % - należy zapewnić, aby wartości zmiennych były %
      %   równe odpowiednik polom stanu początkowego   %   
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      
      solve satisfy;
      
      %%%%%%%%%%%%%%%%%%%%%%%%
      % PRZYKŁADOWE WYJŚCIE  %
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      % - puzzle - dwuwumiarowa tablica zmiennych %
      %            o rozmiarze NxN                %
      % - N - rozmiar planszy, równy S*S          %
      % - S - rozmiar sektora planszy             %
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      output [ show(puzzle[i,j]) ++ " " ++
        if j mod S == 0 then " " else "" endif ++ if j == N /\ i != N then
        if i mod S == 0 then "\n\n" else "\n" endif else "" endif
          | i,j in PuzzleRange ] ++ ["\n"];
    2. Poniżej przykładowe dane wejściowe:
        % 0 to pola o nieznanej wartości
      board = array2d(1..9, 1..9, [   
        0,  0,  0,  2,  0,  5,  0,  0,  0,
        0,  9,  0,  0,  0,  0,  7,  3,  0,
        0,  0,  2,  0,  0,  9,  0,  6,  0,
        2,  0,  0,  0,  0,  0,  4,  0,  9,
        0,  0,  0,  0,  7,  0,  0,  0,  0,
        6,  0,  9,  0,  0,  0,  0,  0,  1,
        0,  8,  0,  4,  0,  0,  1,  0,  0,
        0,  6,  3,  0,  0,  0,  0,  8,  0,
        0,  0,  0,  6,  0,  8,  0,  0,  0
      ]);
    3. Proszę zastosować globalne ograniczenia do problemu n-hetmanów

Lista globalnych ograniczeń dostępnych w MiniZinc: http://www.minizinc.org/downloads/doc-latest/mzn-globals.html

Zadanie Dodatkowe: Magiczne ciągi

  • Treść problemu: magicznym ciągiem nazywamy taki ciąg liczb x0, x1, x2,.., xN w którym wartość xi dla dowolnego i jest równa liczbie wystąpień i w tym ciągu. Przykładowy magiczny ciąg o długości 5 to 2, 1, 2, 0, 0 — na 0-wym miejscu znajduje się liczba wszystkich 0 w ciągu, na miejscu o indeksie 1 liczba 1 w ciągu, etc.
  • Ćwiczenia:
    1. Zamodelować znajdywanie magicznych ciągów o zadanej długości w MiniZinc.
    2. Zastosować globalne ograniczenia.
      %%%%%%%%%%%%% 
      % DZIEDZINA %        
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      % miejsce na dziedzinę                 % 
      % - parametr określający długość ciągu %
      % - tablica zmiennych decyzyjnych      %
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
        
      %%%%%%%%%%%%%%%%
      % Ograniczenia %
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      % Podpowiedzi:                                 %
      % - sum(wyrażenie tablicowe) sumuje elementy   %
      % - bool2int(5==5) da w wyniku 1               %
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
        
      solve satisfy;
        
      %%%%%%%%%%%%%%%%%%%%%%%%
      % PRZYKŁADOWE WYJŚCIE  %
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      % - magic - magiczny ciąg     %
      %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
      output [ "magiczny ciag = ", show(magic),";\n"];
pl/dydaktyka/csp/lab1.txt · ostatnio zmienione: 2017/07/17 08:08 (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