Both sides previous revision
Previous revision
Next revision
|
Previous revision
|
en:dydaktyka:csp:lab3 [2019/03/21 14:30] msl |
en:dydaktyka:csp:lab3 [2020/11/30 12:50] msl [N-Queens Again] |
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 ==== |
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. |
| |
| |
{{ :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 |