this repo has no description
dekker.one
1.. _sec-search:
2
3Búsqueda
4========
5
6.. index::
7 single: annotation
8
9Por defecto en MiniZinc no hay una declaración de cómo queremos buscar soluciones. Esto deja la búsqueda completamente al solucionador subyacente. Pero a veces, en particular para los problemas de entero combinatorio, es posible que deseemos especificar cómo debe realizarse la búsqueda. Esto requiere que nos comuniquemos con el solucionador a una estrategía :index:`search` strategy. Tenga en cuenta que la estrategia de búsqueda *no* es realmente parte del modelo. De hecho, no se requiere que cada solucionador implemente todas las posibles estrategias de búsqueda. MiniZinc usa un enfoque consistente para comunicar información adicional al solucionador de restricciones usando *anotaciones*.
10
11Búsqueda de dominio finito
12--------------------------
13
14.. index::
15 single: search; finite domain
16
17La búsqueda en un solucionador de dominio finito implica examinar los restantes valores posibles de las variables y elegir restringir aún más algunas variables. La búsqueda agrega una nueva restricción que restringe los valores restantes de la variable (en efecto, adivinar dónde podría estar la solución), y luego aplica la propagación para determinar qué otros valores todavía son posibles en las soluciones. Para garantizar la integridad, la búsqueda deja otra opción que es la negación de la nueva restricción. La búsqueda finaliza cuando el solucionador de dominio finito detecta que se cumplen todas las restricciones y, por lo tanto, se ha encontrado una solución o que las restricciones no son satisfactorias. Cuando se detecta insatisfacción, la búsqueda debe continuar por un conjunto diferente de opciones. Normalmente, los solucionadores de dominio finito usan :index:`depth first search <search; depth first>` donde deshacer la última elección realizada y luego intentar hacer una nueva elección.
18
19.. literalinclude:: examples/nqueens_es.mzn
20 :language: minizinc
21 :name: ex-queens
22 :caption: Modelo para n-reinas (:download:`nqueens_es.mzn <examples/nqueens_es.mzn>`).
23
24
25
26
27Un ejemplo simple de un problema de dominio finito es el problema matemático :math:`n` reinas, que requiere que pongamos :math:`n` reinas en un tablero de ajedrez :math:`n \times n` para que ninguno pueda atacar a otro.
28
29La variable :mzn:`q[i]` registra en qué fila se coloca la reina en la columna :mzn:`i`. Las restricciones :mzn:`alldifferent` aseguran que no haya dos reinas en la misma fila o diagonal.
30
31Un árbol de búsqueda típico (parcial) para :mzn:`n = 9` se ilustra en :numref:` fig-9q-a`.
32
33Primero establecemos :mzn:`q[1] = 1`, esto elimina los valores de los dominios de otras variables. De modo que, por ejemplo :mzn:`q[2]` no puede tomar los valores 1 o 2.
34
35Luego establecemos :mzn:`q[2] = 3`, esto elimina los valores de los dominios de otras variables. Establecemos :mzn:`q[3] = 5` (su valor más temprano posible).
36
37El estado del tablero de ajedrez después de estas tres decisiones se muestra en :numref:`fig-9q-b` donde las reinas indican la posición de las reinas ya fijadas y las estrellas indican las posiciones donde no podemos colocar una reina ya que podría tomar una reina ya colocada.
38
39.. _fig-9q-a:
40
41.. figure:: figures/tree-4.*
42
43 Árboles de búsqueda parcial para 9 reinas
44
45.. _fig-9q-b:
46
47.. figure:: figures/chess9x9-3.*
48
49 El estado después de la adición de ``q[1] = 1``, ``q[2] = 4``, ``q[3] = 5``
50
51.. _fig-9q-c:
52
53.. figure:: figures/chess9x9-4.*
54
55 La propagación inicial al agregar más ``q[6] = 4``
56
57Una estrategia de búsqueda determina qué opciones tomar. Las decisiones que hemos tomado hasta ahora siguen la simple estrategia de elegir la primera variable que aún no se ha solucionado e intentar establecerla en su menor valor posible. Siguiendo esta estrategia, la siguiente decisión sería :mzn:`q[4] = 7`.
58
59Una estrategia alternativa para la selección de variables es elegir la variable cuyo conjunto actual de valores posibles (*dominio*) sea más pequeño.
60
61En virtud de la llamada estrategia de selección de variables *first-fail*, la siguiente decisión sería :mzn:`q[6] = 4`.
62
63
64Si tomamos esta decisión, inicialmente la propagación elimina los valores adicionales que se muestran en :numref:`fig-9q-c`. Pero esto deja solo un valor para :mzn:`q[8]`, :mzn:`q[8] = 7`, entonces esto es forzado, pero esto deja solo un valor posible para :mzn:`q[7]` y :mzn:`q[9]`, eso es 2. Por lo tanto, se debe violar una restricción. Hemos detectado insatisfacción, y el solucionador debe retroceder deshaciendo la última decisión :mzn:`q[6] = 4` y agregando su negación :mzn:`q[6]! = 4` (llevándonos al estado (c) en el árbol en :numref:`fig-9q-a`) que fuerza :mzn:`q[6] = 8`. Esto elimina algunos valores del dominio y luego reinvocamos la estrategia de búsqueda para decidir qué hacer.
65
66Muchas búsquedas de dominio finito se definen de esta manera: elija una variable para restringir aún más, y luego elija cómo restringirla aún más.
67
68
69
70
71Anotaciones de búsqueda
72-----------------------
73
74.. index::
75 single: search; annotation
76 single: solve
77
78Las anotaciones de búsqueda en MiniZinc especifican cómo buscar para encontrar una solución al problema. La anotación se adjunta al elemento de resolver, después de la palabra clave :mzn:`solve`.
79
80La anotación de búsqueda
81
82.. literalinclude:: examples/nqueens_es.mzn
83 :language: minizinc
84 :lines: 11-12
85
86
87Aparece en el elemento de resolver. Las anotaciones se adjuntan a las partes del modelo utilizando el conector :mzn:`::`.
88
89Esta anotación de búsqueda significa que debemos buscar seleccionando de la matriz de variables enteras :mzn:`q`, la variable con el dominio actual más pequeño (esta es la regla :mzn:`first_fail`), e intenta configurarlo en su valor más pequeño valor posible (selección del valor :mzn:`indomain_min`), mirando a través de todo el árbol de búsqueda (búsqueda :mzn:`complete`).
90
91
92
93.. % \begin{tabular}{|c|c|c|c|c|c|c|c|c|}
94.. % \hline
95.. % Q & . & . & . & . & . & . & . & . \\ \hline
96.. % . & . & . & & & . & & & \\ \hline
97.. % . & Q & . & . & . & . & . & . & . \\ \hline
98.. % . & . & . & . & & & & & \\ \hline
99.. % . & . & Q & . & . & . & . & . & . \\ \hline
100.. % . & . & . & . & . & . & & & \\ \hline
101.. % . & . & . & & . & . & . & & \\ \hline
102.. % . & . & . & & & . & . & . & \\ \hline
103.. % . & . & . & & & & . & . & . \\ \hline
104.. % \end{tabular}
105
106.. defblock:: Anotaciones de Búsqueda Básicas
107
108 .. index::
109 single: int_search
110 single: bool_search
111 single: set_search
112
113 Hay tres anotaciones de búsqueda básicas correspondientes a diferentes tipos de variables básicas:
114
115 - :mzndef:`int_search( <variables>, <varchoice>, <constrainchoice>, <strategy> )`
116 where :mzndef:`<variables>` is a one dimensional array of :mzn:`var int`,
117 :mzndef:`<varchoice>` is a variable choice annotation discussed below,
118 :mzndef:`<constrainchoice>` is a choice of how to constrain a variable, discussed
119 below, and :mzndef:`<strategy>` is a search strategy which we will assume for now
120 is :mzn:`complete`.
121 - :mzndef:`bool_search( <variables>, <varchoice>, <constrainchoice>, <strategy> )`
122 where :mzndef:`<variables>` is a one dimensional array of :mzn:`var bool`
123 and the rest are as above.
124 - :mzndef:`set_search( <variables>, <varchoice>, <constrainchoice>, <strategy> )`
125 where :mzndef:`<variables>` is a one dimensional array of :mzn:`var set of int`
126 and the rest are as above.
127 - :mzndef:`float_search( <variables>, <precision>, <varchoice>, <constrainchoice>, <strategy> )`
128 where :mzndef:`<variables>` is a one dimensional array of :mzn:`var float`,
129 :mzndef:`<precision>` is a fixed float specifying the :math:`\epsilon` below which
130 two float values are considered equal,
131 and the rest are as above.
132
133 .. index::
134 single: search; variable choice
135 single: input_order
136 single: first_fail
137 single: smallest
138
139 Ejemplo de anotaciones de elección de variable son:
140
141 - :mzn:`input_order`: choose in order from the array
142 - :mzn:`first_fail`: choose the variable with the smallest domain size, and
143 - :mzn:`smallest`: choose the variable with the smallest value in its domain.
144
145 .. index::
146 single: search; constrain choice
147 single: indomain_min
148 single: indomain_median
149 single: indomain_random
150 single: indomain_split
151
152 Ejemplos de formas de restringir una variable son:
153
154 - :mzn:`indomain_min`: asignar a la variable su valor de dominio más pequeño,
155 - :mzn:`indomain_median`: asignar la variable su valor de dominio mediano,
156 - :mzn:`indomain_random`: asignarle a la variable un valor aleatorio de su dominio, y
157 - :mzn:`indomain_split` bisectar el dominio de variables excluyendo la mitad superior.
158
159 El :mzndef:`<strategy>` casi siempre es :mzn:`complete` para una búsqueda completa.
160 Para obtener una lista completa de las anotaciones de opciones de restricciones y restricciones, consulte la especificación FlatZinc en la documentación de referencia MiniZinc.
161
162Podemos construir estrategias de búsqueda más complejas utilizando anotaciones de constructor de búsqueda. Solo hay una anotación de este tipo en el presente:
163
164.. index::
165 single: search; sequential
166 single: seq_search
167
168.. code-block:: minizinc
169
170 seq_search([ <search-ann>, ..., <search-ann> ])
171
172El constructor de búsqueda secuencial primero emprende la búsqueda dada por la primera anotación en su lista, cuando todas las variables en esta anotación son fijas, emprende la segunda anotación de búsqueda, etc. hasta que todas las anotaciones de búsqueda estén completas.
173
174
175Considere el modelo de planificación de puestos de trabajo que se muestra en :numref:`ex-jobshop3`.
176
177Podríamos reemplazar el elemento de resolver con:
178
179.. code-block:: minizinc
180
181 solve :: seq_search([
182 int_search(s, smallest, indomain_min, complete),
183 int_search([end], input_order, indomain_min, complete)])
184 minimize end
185
186Que intenta establecer tiempos de inicio :mzn:`s` al elegir el trabajo que puede comenzar más temprano y establecerlo en ese momento. Cuando se completan todos los tiempos de inicio, el tiempo de finalización :mzn:`end` no se puede arreglar. Por lo tanto, lo establecemos en su valor mínimo posible.
187
188
189Anotaciones
190-----------
191
192.. index::
193 single: annotation
194
195Las anotaciones son un objeto de primera clase en MiniZinc. Podemos declarar nuevas anotaciones en un modelo, declarar y asignar a las variables de anotación.
196
197.. defblock:: Anotaciones
198
199 .. index::
200 single: ann
201
202 Las anotaciones tienen un tipo :mzn:`ann`.
203 Puede declarar una anotación :index:`parameter` (con asignación opcional):
204
205 .. code-block:: minizincdef
206
207 ann : <ident>;
208 ann : <ident> = <ann-expr> ;
209
210 Y asignar a una variable de anotación como cualquier otro parámetro.
211
212 Los elementos :index:`Expressions <expression>`, :index:`variable declarations <variable; declaration>`, y :mzn:`solve` se pueden anotar utilizando el operador :mzn:`::`.
213
214 Podemos declarar un nuevo :index:`annotation` utilizando el :mzn:`annotation` :index:`item <item; annotation>`:
215
216 .. code-block:: minizincdef
217
218 annotation <annotation-name> ( <arg-def>, ..., <arg-def> ) ;
219
220.. literalinclude:: examples/nqueens-ann_es.mzn
221 :language: minizinc
222 :name: ex-queens-ann
223 :caption: Modelo anotado para n-reinas (:download:`nqueens-ann_es.mzn <examples/nqueens-ann_es.mzn>`).
224
225El programa en :numref:`ex-queens-ann` ilustra el uso de declaraciones de anotación, anotaciones y variables de anotación.
226
227Declaramos una nueva anotación :mzn:`bitdomain`, que pretende decirle al solucionador que los dominios variables deben representarse mediante matrices de bits de tamaño :mzn:`nwords`.
228
229La anotación se adjunta a las declaraciones de las variables :mzn:`q`.
230
231Cada una de las restricciones :mzn:`alldifferent` se anota con la anotación incorporada :mzn:`domain` que indica al solucionador que use la versión de propagación de dominio de :mzn:`alldifferent` si tiene una.
232
233Una variable de anotación :mzn:`search_ann` se declara y se usa para definir la estrategia de búsqueda. Podemos dar el valor a la estrategia de búsqueda en un archivo de datos separado.
234
235Las anotaciones de búsqueda de ejemplo pueden ser las siguientes (donde imaginamos que cada línea está en un archivo de datos separado).
236
237.. code-block:: minizinc
238
239 search_ann = int_search(q, input_order, indomain_min, complete);
240 search_ann = int_search(q, input_order, indomain_median, complete);
241 search_ann = int_search(q, first_fail, indomain_min, complete);
242 search_ann = int_search(q, first_fail, indomain_median, complete);
243
244El primero solo prueba las reinas para establecerlas en el valor mínimo, el segundo prueba las variables reinas en orden, pero las establece en su valor mediano, el tercero prueba la variable reina con el dominio más pequeño y lo establece en el valor mínimo, y la estrategia final prueba la variable reinas con el dominio más pequeño configurándola en su valor mediano.
245
246Las diferentes estrategias de búsqueda pueden marcar una diferencia significativa en lo fácil que es encontrar soluciones. En la siguiente tabla se muestra una pequeña comparación de la cantidad de elecciones realizadas para encontrar la primera solución de los problemas de n-reinas utilizando las 4 estrategias de búsqueda diferentes (donde --- significa más de 100,000 opciones). Claramente, la estrategia de búsqueda correcta puede marcar una diferencia significativa.
247
248.. cssclass:: table-nonfluid table-bordered
249
250+-----+-----------+--------------+--------+-----------+
251| n | input-min | input-median | ff-min | ff-median |
252+=====+===========+==============+========+===========+
253| 10 | 28 | 15 | 16 | 20 |
254+-----+-----------+--------------+--------+-----------+
255| 15 | 248 | 34 | 23 | 15 |
256+-----+-----------+--------------+--------+-----------+
257| 20 | 37330 | 97 | 114 | 43 |
258+-----+-----------+--------------+--------+-----------+
259| 25 | 7271 | 846 | 2637 | 80 |
260+-----+-----------+--------------+--------+-----------+
261| 30 | --- | 385 | 1095 | 639 |
262+-----+-----------+--------------+--------+-----------+
263| 35 | --- | 4831 | --- | 240 |
264+-----+-----------+--------------+--------+-----------+
265| 40 | --- | --- | --- | 236 |
266+-----+-----------+--------------+--------+-----------+