This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision | ||
|
en:dydaktyka:csp:lab3 [2019/06/27 15:49] 127.0.0.1 external edit |
en:dydaktyka:csp:lab3 [2020/11/30 12:50] (current) msl [N-Queens Again] |
||
|---|---|---|---|
| Line 5: | Line 5: | ||
| Next we will solve a new issue, where search modeling will have a big impact on the solving process. | Next we will solve a new issue, where search modeling will have a big impact on the solving process. | ||
| + | All files required to solve the assignments are available via the repository, so clone it first. | ||
| ===== Search Modeling ===== | ===== Search Modeling ===== | ||
| - | So far we haven't talked about the way solver looks for the solution. There are many different techniques to solve to constraint programming problem, however basic techniques often perform a DFS (backtracking) search with two steps at every node: | + | So far we haven't talked about the way solver looks for the solution. There are many different techniques to solve a constraint programming problem, however basic techniques often perform a DFS (backtracking) search with two steps at every node: |
| - | - select variable --- choose, which variable will receive a value in this step | + | - select variable --- choose, which variable will receive value in this step |
| - select value --- choose, which value from the variable's domain will be chosen | - select value --- choose, which value from the variable's domain will be chosen | ||
| You may control this procedure in MiniZinc using search annotations just after the solve keyword. e.g. <code> | You may control this procedure in MiniZinc using search annotations just after the solve keyword. e.g. <code> | ||
| solve :: int_search(array, first_fail, indomain_min, complete) satisfy; | solve :: int_search(array, first_fail, indomain_min, complete) satisfy; | ||
| </code> | </code> | ||
| - | mean that że integer (''int'') variables from the ''array'' should be search exhaustively (''complete'') according to the simple strategy: | + | mean that integer (''int'') variables from the ''array'' should be search exhaustively (''complete'') according to the simple strategy: |
| - | * select variable which has to lowest amount of available values (''first_fail'') | + | * select variable which has the lowest amount of available values (''first_fail'') |
| * select the smallest available value (''indomain_min''). | * select the smallest available value (''indomain_min''). | ||
| - | In order to define more interesting search strategies one has to use so called MiniSearch language, which still isn't a part of the MiniZincIDE package. | + | In order to define more interesting search strategies, one has to use so-called MiniSearch language, which still isn't a part of the MiniZincIDE package. |
| ==== N-Queens Again ==== | ==== N-Queens Again ==== | ||
| Line 30: | Line 31: | ||
| int_search(rows, first_fail, indomain_min, complete); | int_search(rows, first_fail, indomain_min, complete); | ||
| int_search(rows, first_fail, indomain_median, complete);</code> | int_search(rows, first_fail, indomain_median, complete);</code> | ||
| - | - Read about the [[https://www.minizinc.org/doc-2.2.0/en/lib-annotations.html?highlight=annotation#search-annotations|different strategies]]. Select one according to your taste. | + | - Read about the [[https://www.minizinc.org/doc-2.5.2/en/fzn-spec.html#annotations|different strategies]]. Select one according to your taste. |
| - | - Compare solving time of the problem using different stragies. | + | - Compare solving time of the problem using different strategies (try at least three different problem sizes, you may just fill csv file in the repository). |
| - Don't worry, be happy. | - Don't worry, be happy. | ||
| Line 39: | Line 40: | ||
| {{ :en:dydaktyka:csp:square_packing.png?nolink&300|}} | {{ :en:dydaktyka:csp:square_packing.png?nolink&300|}} | ||
| - | * **Definition**: having ''n'' squares sized accordingly ''1x1,2x2,...,nxn'', we have to find the rectangle with the smallest area, inside witch we can fit all the sqaures without overlapping.. | + | * **Definition**: having ''n'' squares sized accordingly ''1x1,2x2,...,nxn'', we have to find the rectangle with the smallest area, inside witch we can fit all the squares without overlapping. |
| * **Stage 1:** | * **Stage 1:** | ||
| - Fill the domains' bounds | - Fill the domains' bounds | ||
