En informática , un algoritmo de mínimos conflictos es un algoritmo de búsqueda o un método heurístico para resolver problemas de satisfacción de restricciones .
Un algoritmo de este tipo es el de escalada de mínimos conflictos . [1] Dada una asignación inicial de valores a todas las variables de un problema de satisfacción de restricciones (con una o más restricciones no satisfechas), seleccione una variable del conjunto de variables con conflictos que violan una o más de sus restricciones. Asigne a esta variable un valor que minimice el número de conflictos (normalmente desempatando de forma aleatoria). Repita este proceso de selección de variable en conflicto y asignación de valor de mínimo conflicto hasta que se encuentre una solución o se alcance un número máximo de iteraciones preseleccionado. Si no se encuentra una solución, el algoritmo puede reiniciarse con una asignación inicial diferente.
Debido a que un problema de satisfacción de restricciones puede interpretarse como un problema de búsqueda local cuando todas las variables tienen un valor asignado (llamado estado completo), el algoritmo de mínimos conflictos puede verse como una heurística de reparación [2] que elige el estado con el número mínimo de conflictos.
El algoritmo MIN-CONFLICTS es entrada: console.csp , Un problema de satisfacción de restricciones. max_steps , La cantidad de pasos permitidos antes de darse por vencido. current_state , Una asignación inicial de valores para las variables en el csp. salida : Un conjunto de valores de solución para la variable o falla . para i ← 1 a max_steps hacer si current_state es una solución de csp entonces devolver current_state establecer var ← una variable elegida aleatoriamente del conjunto de variables en conflicto CONFLICTED[ csp ] establecer value ← el valor v para var que minimiza CONFLICTS( var , v , current_state , csp ) establecer var ← valor en current_state Fallo de retorno
Aunque no se especifica en el algoritmo, una buena asignación inicial puede ser fundamental para acercarse rápidamente a una solución. Utilice un algoritmo voraz con cierto nivel de aleatoriedad y permita que la asignación de variables rompa las restricciones cuando ninguna otra asignación sea suficiente. La aleatoriedad ayuda a que los conflictos mínimos eviten los mínimos locales creados por la asignación inicial del algoritmo voraz. De hecho, los problemas de satisfacción de restricciones que responden mejor a una solución de conflictos mínimos funcionan bien cuando un algoritmo voraz casi resuelve el problema. Los problemas de coloración de mapas funcionan mal con el algoritmo voraz y con los conflictos mínimos. Las subáreas del mapa tienden a mantener sus colores estables y los conflictos mínimos no pueden escalar colinas para salir del mínimo local. La función CONFLICTOS cuenta la cantidad de restricciones violadas por un objeto en particular, dado que se conoce el estado del resto de la asignación.
Aunque la Inteligencia Artificial y la Optimización Discreta habían conocido y razonado sobre los Problemas de Satisfacción de Restricciones durante muchos años, no fue hasta principios de la década de 1990 que este proceso para resolver grandes CSP se había codificado en forma algorítmica. Al principio, Mark Johnston del Space Telescope Science Institute buscó un método para programar observaciones astronómicas en el Telescopio Espacial Hubble . En colaboración con Hans-Martin Adorf de la Instalación de Coordinación Europea del Telescopio Espacial , creó una red neuronal capaz de resolver un problema de n -reinas de juguete (para 1024 reinas). [3] [4] Steven Minton y Andy Philips analizaron el algoritmo de la red neuronal y lo separaron en dos fases: (1) una asignación inicial utilizando un algoritmo voraz y (2) fases de minimización de conflictos (que más tarde se llamarían "min-conflictos"). Se escribió y presentó un artículo en AAAI-90; Philip Laird proporcionó el análisis matemático del algoritmo.
Posteriormente, Mark Johnston y el personal del STScI utilizaron min-conflictos para programar el tiempo de observación de los astrónomos en el telescopio espacial Hubble.
Min-Conflicts resuelve el problema de las N reinas seleccionando una columna del tablero de ajedrez para la reasignación de reinas. El algoritmo busca en cada movimiento potencial la cantidad de conflictos (cantidad de reinas atacantes) que se muestra en cada casilla. El algoritmo mueve la reina a la casilla con la cantidad mínima de conflictos, rompiendo los empates aleatoriamente. Tenga en cuenta que la cantidad de conflictos se genera por cada nueva dirección desde la que una reina puede atacar. Si dos reinas atacaran desde la misma dirección (fila o diagonal), entonces el conflicto solo se cuenta una vez. Tenga en cuenta también que si una reina está en una posición en la que un movimiento la pondría en un conflicto mayor que su posición actual, no realiza ningún movimiento. De ello se deduce que si una reina está en un estado de conflicto mínimo, no tiene que moverse.
El rendimiento de este algoritmo depende en gran medida de la elección de la posición inicial. Se puede generar una buena posición inicial asignando reinas columna por columna, y asignando cada una a una fila que minimice el número de violaciones de restricciones. Esto da como resultado una posición inicial con un número promedio de violaciones de restricciones que es sorprendentemente pequeño y crece muy lentamente con n (por ejemplo, 12,8 para n=10 6 ).
Dada una buena posición inicial, la cantidad de reasignaciones necesarias para obtener una solución es igualmente constante: este algoritmo resolverá incluso el problema del millón de reinas en aproximadamente 50 reasignaciones. La cantidad de evaluaciones de restricciones para cada reasignación aumenta con n, lo que lleva a un tiempo de ejecución casi lineal.
Este descubrimiento y las observaciones dieron lugar a una gran cantidad de investigaciones en 1990 y dieron inicio a la investigación sobre problemas de búsqueda local y las distinciones entre problemas fáciles y difíciles. N -Queens es fácil para la búsqueda local porque las soluciones están distribuidas densamente en todo el espacio de estados. También es eficaz para problemas difíciles. Por ejemplo, se ha utilizado para programar observaciones para el telescopio espacial Hubble , reduciendo el tiempo necesario para programar una semana de observaciones de tres semanas a unos 10 minutos. [5]