This shows you the differences between two versions of the page.
| Both sides previous revision Previous revision Next revision | Previous revision Last revision Both sides next revision | ||
|
en:dydaktyka:csp:lab3 [2019/03/21 14:30] msl |
en:dydaktyka:csp:lab3 [2020/03/22 18:45] msl [Constraint Programming: Search Modeling] |
||
|---|---|---|---|
| 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 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 | ||
