Algoritmo de conflictos mínimos

En informática , un algoritmo de conflictos mínimos es un algoritmo de búsqueda o un método heurístico para resolver problemas de satisfacción de restricciones .

Un ejemplo de este algoritmo es el de ascenso de colinas con 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 violen una o más de sus restricciones. Asigne a esta variable un valor que minimice el número de conflictos (generalmente resolviendo los empates aleatoriamente). Repita este proceso de selección de variables con conflictos y asignación de valores 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.

Dado 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 conflictos mínimos 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: consola. csp , un problema de satisfacción de restricciones. max_steps , el número de pasos permitidos antes de rendirse. 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 fallo . para i ← 1 hasta 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_statefallo de retorno

Aunque no se especifica en el algoritmo, una buena asignación inicial puede ser crucial para aproximarse rápidamente a una solución. Utilice un algoritmo voraz con cierto grado 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 donde un algoritmo voraz casi resuelve el problema. Los problemas de coloración de mapas funcionan mal tanto con el algoritmo voraz como con los conflictos mínimos. Las subáreas del mapa tienden a mantener sus colores estables y los conflictos mínimos no pueden ascender para salir del mínimo local. La función CONFLICTS cuenta el número 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 conocían y razonaban sobre los Problemas de Satisfacción de Restricciones desde hacía muchos años, no fue hasta principios de la década de 1990 que este proceso para resolver grandes CSP se codificó 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 del Space Telescope European Coordinating Facility , creó una red neuronal capaz de resolver un problema de juguete de n -reinas (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 usando un algoritmo voraz y (2) una fase de minimización de conflictos (que más tarde se llamaría "min-conflictos"). Se escribió un artículo que se presentó en AAAI-90; Philip Laird proporcionó el análisis matemático del algoritmo.

Posteriormente, Mark Johnston y el personal del STScI utilizaron los miniconflictos 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 para la reasignación de reinas. El algoritmo busca en cada posible movimiento el número de conflictos (número de reinas atacantes) que se muestra en cada casilla. El algoritmo mueve la reina a la casilla con el mínimo número de conflictos, resolviendo los empates aleatoriamente. Cabe destacar que el número de conflictos se genera para cada nueva dirección desde la que una reina puede atacar. Si dos reinas atacaran desde la misma dirección (fila o diagonal), el conflicto se cuenta solo una vez. Además, si una reina se encuentra en una posición en la que un movimiento la pondría en mayor conflicto que su posición actual, no realiza ningún movimiento. Por lo tanto, si una reina se encuentra en un estado de mínimo conflicto, 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, de modo que cada asignación se realice 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 sorprendentemente pequeño y que crece muy lentamente con n (por ejemplo, 12,8 para n=10⁶ ⁾ .

Partiendo de una buena posición inicial, el número de reasignaciones necesarias para encontrar una solución es prácticamente constante: este algoritmo incluso resuelve el problema del millón de reinas en aproximadamente 50 reasignaciones. El número de evaluaciones de restricciones para cada reasignación aumenta con n , lo que resulta en 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. El problema N -Queens es fácil para la búsqueda local porque las soluciones están densamente distribuidas 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 ]}

• El algoritmo de Warnsdorff
• Búsqueda local guiada

• Stuart J. Russell y Peter Norvig , Inteligencia artificial: un enfoque moderno

• Microforma heurística de conflictos mínimos  : resultados experimentales y teóricos / Steven Minton ... [et al.]. NASA, Centro de Investigación Ames, Rama de Investigación en Inteligencia Artificial. Distribuido a bibliotecas depositarias en microfichas.