Algoritmo de conflictos del minuto

El algoritmo de conflictos de minuto es un algoritmo de búsqueda para solucionar problemas de satisfacción de coacción (problemas de CSP).

Asigna valores arbitrarios a todas las variables de un CSP. Entonces selecciona al azar una variable, cuyo valor entra en conflicto con cualquier coacción del CSP. Entonces asigna a esta variable el valor con los conflictos mínimos. Si hay más de un mínimo, elige un entre ellos al azar. Después de esto, una nueva iteración comienza otra vez hasta que una solución se encuentre o un número máximo preseleccionado de iteraciones se alcanza.

Como un CSP se puede interpretar como un problema de búsqueda local cuando todas las variables han asignado un valor (estados completos), el algoritmo de conflictos de minuto se puede ver como un heurístico que elige el estado con el número mínimo de conflictos.

Algoritmo

funcione conflictos del MINUTO (csp, max_steps) devuelve una solución o fracaso

entradas: csp, un problema de satisfacción de coacción

max_steps, el número de pasos permitidos antes de rendirse

corriente

Los conflictos del minuto solucionan el problema de N-Queens seleccionando al azar una columna del Tablero de ajedrez para la reasignación de la reina. El algoritmo busca cada movimiento potencial el número de conflictos (número de atacar a las reinas), mostrado en cada cuadrado. El algoritmo mueve a la reina al cuadrado con el número mínimo de conflictos, rompiendo lazos al azar. Note que el número de conflictos es generado por cada nueva dirección de la cual una reina puede atacar. Si las dos reinas atacaran de la misma dirección (fila o diagonal) entonces el conflicto sólo se cuenta una vez. También note que si una reina está en una posición en la cual un movimiento lo pondría en el mayor conflicto que su situación actual, no hace un movimiento. Resulta que si una reina está en un estado del conflicto mínimo, no se tiene que mover.

El tiempo de ejecución de este algoritmo para solucionar N-Queens es independiente de la talla del problema. Este algoritmo solucionará hasta el millón de problema de reinas en el promedio de 50 pasos. Este descubrimiento y observaciones llevan a una gran cantidad de la investigación en 1990 y comenzaron la investigación en problemas de búsqueda locales y las distinciones entre problemas fáciles y difíciles. N-Queens es fácil para la búsqueda local porque las soluciones densamente se distribuyen en todas partes del espacio estatal. También es eficaz para problemas difíciles. Por ejemplo, ha sido usado para programar observaciones para el Telescopio espacial Hubble, reduciendo el tiempo tomado para programar una semana de observaciones de tres semanas a aproximadamente 10 minutos.

Véase también

Enlaces externos



Buscar