Búsqueda no informada e informada

Un problema de búsqueda describe las opciones antes de que un algoritmo empiece a tomarlas. Su formulación determina tanto qué significa una solución como cuántas posibilidades debe considerar el algoritmo.

Define el problema

Hay seis componentes:

• Los estados describen las situaciones posibles.
• El estado inicial es donde comienza la búsqueda.
• Las acciones son las opciones disponibles en un estado.
• El modelo de transición, $\text{RESULT}(s,a)$, indica el estado después de la acción $a$.
• La prueba de objetivo reconoce un estado aceptable.
• La función de costo de la acción, $c(s,a,s^{\mathrm{\prime }})$, asigna un costo a cada paso.

Aquí todos los costos de las acciones son positivos. Una solución de un problema de búsqueda de caminos es una secuencia de acciones que lleva a un objetivo. Suma los costos de sus acciones para obtener su costo del camino. Una solución óptima en costo minimiza esa suma. Nombrar el destino no le indica a un agente cómo llegar a él.

Formula el rompecabezas de 8 fichas

Un tablero contiene ocho fichas numeradas y una casilla vacía. Registra las nueve posiciones como el estado. El estado inicial es la disposición dada; el objetivo es «1 2 3 / 4 5 6 / 7 8 casilla vacía». Una acción mueve la casilla vacía a la izquierda, derecha, arriba o abajo cuando ese movimiento permanece dentro del tablero. La transición intercambia la casilla vacía con la ficha vecina y cada movimiento cuesta 1. Una esquina permite dos acciones; el centro permite cuatro.

Una solución es una secuencia como «Izquierda, arriba, derecha», si esos movimientos son válidos y alcanzan el objetivo. Como cada movimiento tiene el mismo costo, minimizar el costo significa minimizar el número de movimientos.

Elige el espacio de estados

Piensa en los estados como vértices de un grafo dirigido y en las acciones como aristas etiquetadas con su costo. Una carretera de doble sentido da dos aristas dirigidas. Para buscar una ruta, un estado puede ser el lugar actual y el costo de un paso puede ser la distancia por carretera en kilómetros.

La abstracción omite detalles irrelevantes. La música que suena en un coche no tiene por qué formar parte de un estado de ruta. Una solución abstracta debe seguir siendo posible de llevar a cabo. Eliminar un detalle que cambia qué acciones son válidas cambiaría el problema, no solo simplificaría su descripción.

La formulación puede ahorrar más trabajo que una cola más rápida. Colocar ocho reinas en cualquier casilla vacía da $64\times 63\times \cdots \times 57\approx \mathrm{1,8}\times {10}^{14}$ secuencias ordenadas de colocación posibles. Colocar cada nueva reina en la columna vacía situada más a la izquierda, en una casilla no atacada, deja 2057 estados alcanzables. Son dos construcciones distintas de la misma condición de objetivo.

Genera posibilidades a medida que se necesitan

El rompecabezas de 8 fichas tiene $9!\mathrm{/}2=181440$ estados alcanzables desde un inicio fijo. El de 15 fichas tiene $16!\mathrm{/}2\approx \mathrm{1,05}\times {10}^{13}$. Una representación completa de 8 reinas con una reina por columna tiene $8^8=16777216$ estados.

Estos espacios suelen proporcionarse de forma implícita: la búsqueda recibe un estado inicial y procedimientos para las acciones y las transiciones. Genera la parte pertinente a medida que se ejecuta. Para un problema de caminos, conserva la secuencia de acciones. Para un problema de optimización como la colocación de reinas, la disposición final puede ser la propia respuesta.

El espacio de estados describe lo que es posible. El árbol de búsqueda registra los caminos que ha probado el algoritmo. Varios nodos pueden describir el mismo estado porque llegaron a él por caminos distintos.

Almacena un camino en un nodo

Un nodo almacena un estado, su nodo padre, la acción desde ese padre y el costo del camino $g(n)$. También puede almacenarse la profundidad. La raíz no tiene padre y su costo del camino es 0. Expandir un nodo aplica todas las acciones válidas a su estado y genera sus hijos.

En un mapa de carreteras de doble sentido, los caminos «S, A» y «S, B, C, A» terminan en el mismo estado pero dan nodos distintos. Incluso un mapa finito puede generar un árbol de búsqueda infinito: «S, A, S, A, …» sigue produciendo caminos cada vez más largos.

La frontera, también llamada fringe, contiene los nodos generados que esperan ser expandidos. El conjunto de estados alcanzados registra los estados generados y el mejor nodo encontrado para cada uno. Incluye tanto los estados que siguen en la frontera como los ya expandidos. Un conjunto cerrado o explorado suele referirse solo a los estados expandidos.

Ejecuta el procedimiento general primero el mejor

1. Coloca la raíz en la frontera y en la tabla de estados alcanzados.
2. Si la frontera está vacía, devuelve fallo.
3. Extrae el nodo con el menor valor de evaluación $f(n)$.
4. Si su estado es un objetivo, devuelve ese nodo.
5. Expándelo. Añade cada estado nuevo; para un estado alcanzado anteriormente, sustituye su nodo almacenado solo cuando el nuevo camino sea menos costoso.
6. Repite desde el paso 2.

Un camino menos costoso hacia un estado ya expandido puede requerir su reapertura. Los retornos de igual costo no suponen una mejora. Con un montículo, una entrada anterior puede permanecer físicamente; debe reconocerse como obsoleta y omitirse al extraerla.

La regla de la frontera determina la estrategia. Una cola FIFO selecciona nodos de poca profundidad para BFS. Una pila LIFO selecciona nodos profundos para DFS. Las colas de prioridad ordenadas por $g$, $h$ y $g+h$ dan las búsquedas de costo uniforme, voraz primero el mejor y A*.

Sigue los nodos del mapa de carreteras

Usa estas carreteras de doble sentido, con distancias en kilómetros: S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 y D–G 2. Comienza en S y busca G. Desempata alfabéticamente.

Expandir S genera A con costo 2, B con costo 3 y D con costo 9. Cada uno tiene a S como padre. La frontera contiene A, B y D; la tabla de estados alcanzados también contiene S. Más adelante, se puede alcanzar C por A con costo 6 o por B con costo 4. Son dos nodos para un mismo estado, y el menos costoso debe representar a C.

Para recuperar una solución, sigue hacia atrás los enlaces a los padres del nodo objetivo devuelto e invierte las acciones. Actualizar el costo sin actualizar el padre dejaría un camino que no coincide con su costo registrado.

Decide qué recordar

La búsqueda en grafos recuerda los estados alcanzados para evitar repetir trabajo. La búsqueda en árbol no tiene una tabla global de estados alcanzados; puede limitarse a rechazar ciclos en el camino actual. Ahorra memoria, pero puede generar el mismo estado por muchos caminos.

El procedimiento general comprueba los objetivos al extraerlos. BFS puede comprobarlos al generarlos porque la generación sigue el orden de profundidad. La búsqueda basada en costos debe esperar a la extracción: el primer objetivo generado puede tener un camino más costoso que un objetivo encontrado después.

Un algoritmo puede ser fiable y, aun así, demasiado costoso de ejecutar. Evalúa sus garantías por separado de su uso de recursos y comprueba después si esas garantías se ajustan al problema que necesitas resolver.

Haz cuatro preguntas distintas

La completitud significa encontrar una solución siempre que exista. En un espacio alcanzable finito, agotar todas las posibilidades también puede demostrar que no hay solución. Un espacio infinito sin solución puede explorarse eternamente, incluso con un algoritmo completo.

La optimalidad en costo significa devolver una solución con el menor costo del camino. No dice nada sobre la velocidad de ejecución del algoritmo. Un método puede encontrar una solución de forma fiable y, aun así, devolver una ruta costosa.

La complejidad temporal cuenta los nodos generados o expandidos. Indica qué conteo se usa al comparar mediciones. La complejidad espacial mide el número máximo de nodos mantenidos a la vez, incluidos la frontera y los datos almacenados de la búsqueda.

Identifica los parámetros

Para un espacio de búsqueda implícito, usa:

Para un grafo explícito que ya está en memoria, el número de vértices y aristas suele ser más útil. Una cota de recorrido en función de $\mathrm{\mid }V\mathrm{\mid }$ y $\mathrm{\mid }E\mathrm{\mid }$ responde a una pregunta distinta de una cota para generar un árbol aún desconocido.

Descubre por qué la profundidad es costosa

Un árbol completo hasta profundidad $d$ contiene

nodos para $b\mathrm{\ne }1$. Con factor de ramificación 10 y profundidad 5, son 111 111 nodos incluida la raíz. Aumentar la profundidad en uno añade una capa con diez veces más nodos que la capa anterior.

A un millón de nodos por segundo y 1 kilobyte por nodo, la escala cambia rápidamente:

Estas son unidades de almacenamiento decimales: 1 GB equivale a ${10}^9$ bytes. La memoria puede descartar una búsqueda mucho antes de que su tiempo de ejecución parezca excesivo.

Interpreta las garantías con sus condiciones

BFS acaba llegando a toda profundidad finita cuando la ramificación es finita. DFS puede pasar una eternidad en una rama infinita y nunca probar un objetivo cercano. Esa diferencia explica sus resultados de completitud.

BFS encuentra un camino con el menor número de acciones. Si una ruta de dos pasos cuesta 11 km y una de tres pasos cuesta 9 km, la ruta de menor profundidad no es óptima en costo. Los costos iguales por paso hacen que profundidad y costo coincidan; los costos diferentes pueden separarlos.

Una cota O grande del peor caso no predice todas las ejecuciones. Dos métodos con la misma cota pueden diferir en constantes, tratamiento de duplicados y número de ramas útiles. Una heurística puede mejorar mucho una ejecución típica sin eliminar el peor caso exponencial.

La búsqueda en anchura explora por capas. Su siguiente expansión es el nodo de menor profundidad que sigue esperando, por lo que se considera cada camino de una acción antes de expandir cualquier camino de dos acciones.

Mantén el orden de la cola

La frontera es primero en entrar, primero en salir: extrae por el principio y añade los hijos al final. Registra los estados cuando se generan. Si el estado de un hijo ya se ha alcanzado, omítelo; de lo contrario, dos padres distintos podrían poner el mismo estado en la cola.

Comprueba el estado inicial antes de buscar. Para los nodos posteriores, BFS puede usar una prueba de objetivo al generar el nodo. El primer objetivo generado tiene profundidad mínima porque el algoritmo genera hijos capa por capa. El orden dentro de una capa puede elegir entre soluciones de igual profundidad, pero no puede hacer que aparezca primero una solución más profunda.

Sigue los pasos en el mapa de ejemplo

Las carreteras de doble sentido son S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 y D–G 2 km. Comienza en S, busca G y genera los vecinos por orden alfabético. En la tabla, el siguiente nodo que se extraerá está a la izquierda.

Cuando se expande B, C y D ya se han alcanzado. No cambian de posición en la cola. Cuando D genera G, su cadena de padres es G–D–S. Inviértela para recuperar S–D–G, con dos carreteras y una distancia total de $9+2=11$ km.

C ya se ha generado, pero no se ha expandido. Su ruta a G tendría tres carreteras. BFS puede detenerse sin explorarla porque tres carreteras no pueden mejorar el número de acciones de una solución de dos carreteras.

Conoce qué minimiza el resultado

BFS es completa para una ramificación finita, incluso si el espacio es infinito: cada capa finita se procesa antes que la siguiente. Es óptima en costo cuando todas las acciones cuestan lo mismo. En un rompecabezas deslizante con costo 1 por movimiento, una solución de menor profundidad también es una solución de menor costo.

En este mapa de carreteras, S–B–C–G cuesta $3+1+5=9$ km. BFS devuelve la ruta de 11 km porque la distancia no es su criterio de ordenación. Por tanto, «camino más corto» necesita una unidad: el menor número de carreteras y el menor número de kilómetros son objetivos distintos.

Ten en cuenta la memoria

Con la prueba de objetivo al generar, BFS requiere $O(b^d)$ de tiempo y espacio. Puede generar casi todos los nodos hasta la profundidad del objetivo y conservar la frontera y la información de los estados alcanzados. Si los objetivos solo se comprueban al extraerlos, expandir otros nodos a profundidad $d$ puede generar nodos a profundidad $d+1$, lo que da la cota habitual $O(b^{d+1})$ para esa versión.

Con factor de ramificación 10 y 1 kilobyte por nodo, almacenar un árbol hasta profundidad 10 requiere unos 11 TB. BFS es útil para problemas de poca profundidad y costos iguales cuando hay suficiente memoria, como caminos de red con el menor número de saltos o rompecabezas con el menor número de movimientos. Una cola FIFO no usa los costos numéricos de las aristas, aunque estén escritos en el grafo.

La búsqueda de costo uniforme ordena los caminos según el costo ya pagado. Puede pasar por alto un destino cercano pero costoso mientras investiga rutas más largas formadas por pasos baratos.

Extrae el camino menos costoso

Establece $f(n)=g(n)$ y usa una cola de prioridad. Cuando una expansión encuentra un camino menos costoso hacia un estado alcanzado, actualiza tanto su costo como su padre. Un camino de igual costo no mejora el registro. UCS es la forma de búsqueda del algoritmo de Dijkstra y se detiene cuando extrae un objetivo.

La prueba de objetivo al extraer el nodo es esencial. Generar un objetivo demuestra que existe una ruta. Extraer ese objetivo como el nodo menos costoso de la frontera demuestra que ninguna ruta sin terminar de menor costo puede superarlo, dados costos de acción positivos.

Sigue los pasos en el mapa de ejemplo

Usa las carreteras de doble sentido S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 y D–G 2 km. Desempata alfabéticamente los costos iguales. Las entradas de la frontera muestran a continuación el estado y el costo del camino.

La sustitución de C es decisiva: $3+1=4$ mejora $2+4=6$. El padre de G es C, el padre de C es B y el padre de B es S. La ruta devuelta S–B–C–G cuesta 9 km. D se extrae antes que G solo porque la regla de desempate es alfabética.

Si se añadiera una carretera directa S–G de 12 km, S generaría un objetivo de inmediato. Una prueba al generar devolvería 12 km antes de descubrir la ruta de 9 km. La cola de prioridad no puede proteger la optimalidad si la regla de parada la elude.

Explica la garantía

Con ramificación finita y el costo de cada acción al menos igual a algún $ϵ>0$, solo puede caber un número finito de pasos de un camino por debajo de cualquier cota fija de costo. Por tanto, UCS acaba extrayendo un objetivo siempre que exista uno. Los costos positivos garantizan que extender un camino no pueda hacerlo menos costoso, lo que sustenta la demostración de optimalidad.

Los costos cero requieren cuidado. La búsqueda en árbol puede seguir recorriendo un ciclo de costo cero. La búsqueda en grafos rechaza los retornos de igual costo al mismo estado, pero una cadena infinita de estados distintos con costo acumulado acotado todavía puede retrasar un objetivo eternamente. Los costos negativos por paso invalidan el argumento habitual de optimalidad de UCS.

Entiende el costo

La cota estándar de tiempo y espacio en el peor caso es $O(b^{1+\lfloor C^{\ast }\mathrm{/}ϵ\rfloor })$. En este mapa, $C^{\ast }=9$ y $ϵ=1$, lo que da $O(b^{10})$. Es una cota poco ajustada, no el número real de nodos expandidos en el mapa de seis estados.

Muchos caminos baratos sin salida pueden obligar a UCS a realizar mucho trabajo antes de tomar una acción útil y costosa. Cuando todos los pasos tienen el mismo costo, su prueba de objetivo al extraer da la conocida cota $O(b^{d+1})$. A* con $h=0$ hace exactamente las mismas comparaciones de prioridad que UCS.

La búsqueda en profundidad sigue una rama antes de probar sus alternativas. Esta elección puede reducir mucho el uso de memoria, pero permite que una rama desafortunada retrase todas las demás posibilidades.

Sigue una rama profunda

DFS usa una pila en la que el último en entrar es el primero en salir. En una versión de búsqueda en árbol, rechaza los estados que ya están en el camino actual para evitar ciclos inmediatos. Almacena el camino actual y los hermanos sin expandir a lo largo de él. Para probar los sucesores por orden alfabético con una pila, introdúcelos en orden alfabético inverso.

En el mapa de carreteras de doble sentido S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 y D–G 2 km, comienza en S y busca G. Al probar los vecinos por orden alfabético y comprobar los objetivos al extraerlos, se obtiene S, A, C, B, D, G. En C, B es el primer vecino que aún no está en el camino. La ruta devuelta S–A–C–B–D–G cuesta $2+4+1+6+2=15$ km.

DFS no es óptima en costo. Es completa en un espacio finito con comprobación de ciclos en el camino, pero puede seguir una rama infinita eternamente. Su tiempo en el peor caso es $O(b^m)$ y los caminos y hermanos almacenados necesitan $O(bm)$ de espacio. La búsqueda con retroceso que genera un hijo cada vez reduce el almacenamiento a $O(m)$. Con ramificación 10 y profundidad máxima 12, almacenar el camino y sus hermanos requiere unos 120 nodos, frente a aproximadamente un billón para BFS hasta profundidad 12. Una tabla global de estados alcanzados usaría memoria adicional.

Limita la profundidad

La búsqueda de profundidad limitada deja de expandir a profundidad $\mathrm{\ell }$. Un objetivo situado allí todavía puede reconocerse. Distingue tres resultados:

• Se encontró una solución.
• Corte: el límite de profundidad impidió una búsqueda completa.
• Fallo: se agotaron las posibilidades pertinentes sin encontrar un objetivo ni producirse un corte.

Un corte no demuestra que no exista una solución. Si el objetivo de menor profundidad está a profundidad 7, un límite de 5 no puede alcanzarlo. El tiempo y el espacio en el peor caso son $O(b^{\mathrm{\ell }})$ y $O(b\mathrm{\ell })$.

Aumenta el límite gradualmente

La búsqueda de profundización iterativa, o IDS, ejecuta búsquedas de profundidad limitada con límites 0, 1, 2 y así sucesivamente. Encuentra una solución de menor profundidad sin almacenar una frontera de búsqueda en anchura. Con ramificación finita es completa; con costos de acción iguales es óptima en costo. El tiempo es $O(b^d)$ y el espacio es $O(bd)$.

La mayoría de los nodos de un árbol ancho están en la última capa, por lo que repetir las capas superiores suele ser poco costoso. Para $b=10$ y $d=5$, cuenta los nodos generados por debajo de la raíz:

BFS genera 111 110 nodos de este tipo hasta profundidad 5. IDS genera aproximadamente un 11 % más, pero solo mantiene el almacenamiento de una búsqueda en profundidad. Las visitas repetidas a la raíz se excluyen de ambos conteos.

Para factores de ramificación mayores que 1, el costo adicional en un árbol ancho se aproxima al factor $b\mathrm{/}(b-1)$. Esta ventaja es menor en una cadena estrecha, donde dominan los prefijos repetidos. IDS es una elección no informada útil cuando se desconoce la profundidad de la solución y una frontera completa no cabe en memoria. En espacios con muchas rutas hacia el mismo estado, la ausencia de un conjunto global de estados alcanzados puede causar mucha regeneración.

Una estrategia útil se ajusta al resultado que necesitas y a los recursos disponibles. La búsqueda no informada usa la definición del problema sin una estimación de la distancia restante. Aun así, puede ser sistemática y estar ordenada cuidadosamente.

Compara en igualdad de condiciones

Supón una ramificación finita y las condiciones de costo positivo para UCS. La fila de BFS usa la prueba de objetivo al generar; la de DFS usa comprobaciones de ciclos en el camino y no usa una tabla global de estados alcanzados.

BFS e IDS también minimizan el costo cuando este es una función no decreciente solo de la profundidad. La palabra «solo» importa: todos los caminos de una profundidad dada deben tener el mismo costo para que se cumpla esta condición más amplia. Las aristas positivas por sí solas no hacen que BFS sea óptima en costo.

Busca desde ambos extremos

La búsqueda bidireccional trabaja hacia delante desde el inicio y hacia atrás desde el objetivo. Si las búsquedas se encuentran cerca del centro, cada una llega aproximadamente a profundidad $d\mathrm{/}2$. El trabajo es entonces aproximadamente $2b^{d\mathrm{/}2}$ en lugar de $b^d$. Con factor de ramificación 10 y profundidad de solución 6, la comparación de la última capa es de unos 2000 nodos frente a 1 000 000.

Necesita un estado objetivo explícito y una forma de generar predecesores. Las carreteras reversibles de doble sentido facilitan la expansión hacia atrás. Una propiedad de objetivo como «todas las reinas están a salvo» puede describir demasiados estados objetivo para proporcionar un punto de partida inverso práctico.

Con búsquedas en anchura o basadas en costos, unas reglas adecuadas de encuentro y terminación pueden preservar la completitud y la optimalidad. En un mapa ponderado, detente solo cuando ya no sea posible una conexión menos costosa. La primera intersección entre las dos búsquedas no tiene por qué ser la conexión menos costosa.

Elige según el problema

Para obtener el menor número de movimientos en un rompecabezas deslizante pequeño, los costos iguales hacen adecuada BFS si hay memoria abundante. Para viajar la menor distancia con longitudes de carretera desiguales y sin heurística, elige UCS. Para un rompecabezas enorme de costos iguales y profundidad de solución desconocida, IDS evita una frontera enorme. En un espacio finito con muchos objetivos profundos donde cualquier solución es aceptable, DFS puede ser práctica. Un inicio y un objetivo conocidos con acciones reversibles hacen que valga la pena considerar la búsqueda bidireccional.

El uso de memoria debe incluir lo que almacena la versión elegida. DFS con una tabla global de estados alcanzados ya no tiene el mismo perfil de almacenamiento que DFS en árbol. No debe compararse un seguimiento de BFS con prueba de objetivo al extraer con una cota de complejidad para la prueba al generar como si las versiones fueran idénticas.

Incluso la mejor elección no informada puede enfrentarse a un crecimiento exponencial. Cuando se dispone de conocimiento útil del dominio, una heurística puede reducir la exploración irrelevante. Cuando solo importa una configuración final, la búsqueda local puede evitar conservar un árbol de búsqueda.

Una heurística asigna a un estado una estimación del menor costo restante hasta un objetivo. Escríbela como $h(n)$ para el estado del nodo $n$. Depende del estado, no del camino usado para alcanzarlo, y es cero en un objetivo.

Estima lo que falta

La distancia en línea recta estima la distancia restante por carretera. En una cuadrícula con movimientos horizontales y verticales de una unidad, la distancia de Manhattan suma las diferencias de coordenadas:

Desde la casilla (1,1) hasta (4,5), esto da $3+4=7$ movimientos. La distancia en línea recta entre las mismas coordenadas es $\sqrt{3^2+4^2}=5$. Las estimaciones responden a distintas preguntas sobre movimientos relajados. Una heurística debe usar las mismas unidades que el costo que estima; los kilómetros no estiman directamente el tiempo de viaje sin un modelo de conversión adecuado.

La búsqueda informada usa una estimación para orientar la expansión. La estimación no tiene por qué indicar al algoritmo qué acción tomar. Puntúa los estados producidos por las acciones válidas y la regla de la frontera decide qué camino pendiente investigar a continuación.

Sigue la estimación más pequeña

La búsqueda voraz primero el mejor establece $f(n)=h(n)$. Su cola de prioridad extrae el estado que parece más cercano al objetivo, ignorando el costo ya pagado.

Usa las carreteras de doble sentido S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 y D–G 2 km. Las estimaciones heurísticas hasta G son S 8, A 7, B 5, C 4, D 2 y G 0 km.

1. Expande S. La frontera contiene A con estimación 7, B con 5 y D con 2.
2. Extrae D porque 2 es el menor valor. Expandir D genera G con estimación 0. El costo del camino a G es $9+2=11$ km.
3. Extrae G y devuelve S–D–G.

Solo se expandieron S y D. La ruta S–B–C–G de 9 km estaba disponible, pero la estimación 5 de B parecía peor que el 2 de D. La búsqueda voraz nunca incluyó en su comparación los 9 km ya recorridos para llegar a D.

Distingue la orientación de las garantías

Incluso una heurística que nunca sobreestima no hace que la búsqueda voraz sea óptima en costo. Las estimaciones del ejemplo son admisibles y, aun así, la ruta devuelta es demasiado costosa. La búsqueda voraz solo usa la estimación restante, por lo que puede pagar demasiado antes de llegar a un estado prometedor.

La búsqueda en grafos es completa en un espacio de estados finito cuando trata correctamente los duplicados. La búsqueda voraz en árbol puede entrar en ciclos con estados repetidos que parecen prometedores, y un espacio infinito puede seguir ofreciendo estimaciones bajas engañosas. El tiempo y el espacio en el peor caso son $O(b^m)$, aunque una estimación útil puede hacer que una ejecución real sea corta.

Un lugar puede estar cerca de un destino en línea recta pero requerir un largo desvío alrededor de un río. Los valores heurísticos pequeños no garantizan buenas rutas totales. Calcular la heurística también lleva tiempo: reducir las expansiones solo ayuda si evaluar esas estimaciones no consume el ahorro.

A* evalúa todo el trayecto propuesto: el costo ya pagado más una estimación de lo que falta. Su prioridad es

Usa una cola de prioridad, sustituye los caminos más costosos y comprueba un objetivo cuando se extrae. En un objetivo, $h=0$, por lo que su prioridad es su costo real del camino.

Sigue la regla de costo más estimación

Las carreteras de doble sentido son S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 y D–G 2 km. Las estimaciones heurísticas hasta G son S 8, A 7, B 5, C 4, D 2 y G 0. Desempata alfabéticamente.

A se extrae antes que G por la regla de desempate. A* expande cuatro nodos que no son objetivo y nunca expande D. UCS en el mismo mapa también expande D. Establecer todas las estimaciones heurísticas en cero eliminaría esta orientación y reproduciría UCS.

Explica por qué funciona una estimación optimista

Una heurística admisible nunca supera el costo restante real $h^{\ast }(n)$. Para A* con reapertura, la admisibilidad garantiza la optimalidad en costo; A* en árbol tiene la misma garantía bajo las condiciones de búsqueda con costos positivos.

Supón que estuviera a punto de extraerse un objetivo peor con costo $C>C^{\ast }$. Algún nodo de un camino óptimo debe seguir pendiente. Para el prefijo de ese camino óptimo,

La cola debe elegir ese nodo antes que el objetivo peor. Esto contradice el punto de parada propuesto. La reapertura importa porque debe permitirse que un prefijo menos costoso descubierto después continúe a través de un estado ya expandido.

Una heurística consistente hace que $f$ no disminuya a lo largo de los caminos. Garantiza que la primera expansión de un estado use un camino de menor costo hasta él. A* puede entonces cerrar permanentemente los estados expandidos. Con solo admisibilidad, un conjunto cerrado permanente puede descartar una mejora esencial.

Entiende la poda y sus límites

Con consistencia, A* expande cada nodo pertinente cuyo $f<C^{\ast }$, puede expandir nodos empatados en $C^{\ast }$ y no expande ninguno por encima de ese valor antes de devolver el resultado. La prioridad 11 de D supera el costo 9 de la solución, por lo que permanece sin expandir. En la clase de algoritmos que construyen caminos hacia delante y usan la misma información heurística, A* es óptimamente eficiente salvo en los empates. Esta es una comparación de las expansiones necesarias, no una afirmación de que su código siempre se ejecute más rápido.

La sobreestimación puede invalidar el argumento. Cambia la estimación de B a 9 aunque su costo restante real sea 6. B tiene ahora prioridad 12. A*, siguiendo S, A, C y D, devuelve S–A–C–G con costo 11 mientras B sigue esperando.

A* sigue teniendo un peor caso exponencial y almacena información de búsqueda generada.

Cuando la frontera ya no cabe en memoria o una respuesta tarda demasiado, elige qué recurso o garantía sacrificar. Las variantes orientadas a la velocidad cambian las prioridades o descartan candidatos. Las orientadas a la memoria regeneran caminos que no pudieron conservar.

Da más peso a la estimación

A ponderado* usa $f=g+Wh$ con $W>1$. Suele favorecer con más fuerza el avance hacia un objetivo. Con una heurística admisible y las actualizaciones del mejor camino y la reapertura del procedimiento general, el costo que devuelve es como máximo $W{C}^{\ast }$. Esa cota permite una solución peor, pero no la exige.

En el mapa de carreteras del ejemplo, usa las estimaciones S 8, A 7, B 5, C 4, D 2 y G 0, y peso 2. Desde S, las prioridades son B 13, D 13 y A 16. El desempate alfabético selecciona B. Su hijo C tiene $4+2(4)=12$; C genera entonces G con prioridad 9. La ruta de costo 9 se devuelve tras tres expansiones de nodos que no son objetivo. La garantía permite hasta 18 km, aunque esta ejecución encuentra el óptimo.

En la misma fórmula, el peso 0 da UCS y el peso 1 da A*. A medida que el peso crece, la estimación domina cada vez más las comparaciones y se aproxima al comportamiento voraz.

La búsqueda en haz conserva solo los $k$ mejores nodos pendientes y descarta el resto. La frontera conservada está acotada, pero un candidato descartado puede contener la única solución. Por tanto, no ofrece garantía de completitud ni de optimalidad.

Profundiza según un umbral de costo estimado

IDA* realiza una búsqueda en profundidad con un corte en $f=g+h$. El primer corte es el valor de la raíz. Poda cualquier nodo que lo supere y registra el menor valor que lo haya superado. Ese valor se convierte en el siguiente corte; no es necesariamente el corte anterior más 1. Usa comprobaciones de ciclos en el camino.

Para el mapa del ejemplo, el primer corte es 8. Se podan A con 9 y D con 11; se exploran B y C con 8, pero se poda G con 9. El siguiente corte es 9. En esa iteración, el camino por A produce C con 10 y se poda. El camino S–B–C–G se mantiene dentro de 9 y tiene éxito.

Con admisibilidad, IDA* conserva la optimalidad en costo y solo necesita el almacenamiento de caminos de una búsqueda en profundidad. Sus pasadas repetidas pueden ser costosas cuando los costos producen muchos umbrales distintos. Los costos enteros pequeños suelen hacer más manejable el número de umbrales.

Usa la memoria acotada de forma más selectiva

La búsqueda recursiva primero el mejor (RBFS) almacena la mejor prioridad alternativa en cada nivel. Sigue la rama más prometedora hasta que esa alternativa resulta mejor y entonces retrocede. Usa memoria lineal, pero puede regenerar ramas olvidadas.

SMA* usa la memoria disponible, descarta la hoja de la frontera con peor valor cuando se llena y transmite ese valor a su padre. Este registro permite regenerarla más adelante. Con una heurística admisible es óptimo en costo si un camino de solución óptima cabe en memoria. De lo contrario, puede devolver una solución peor o fallar si no cabe ningún camino de solución.

Elige A* para una respuesta óptima cuando el almacenamiento sea suficiente. Elige IDA* o una variante adecuada con memoria acotada cuando la optimalidad importe pero la frontera no quepa en memoria. A* ponderado ofrece una cota numérica de calidad; la búsqueda en haz ofrece una poda intensa sin esa cota.

Una heurística puede ser optimista en general y, aun así, cambiar demasiado bruscamente entre estados vecinos. La admisibilidad y la consistencia recogen estas distintas comprobaciones y cada una sustenta una versión diferente de A*.

Compara las estimaciones con los costos reales

Una heurística admisible cumple $0\le h(n)\le h^{\ast }(n)$ en cada estado. En un objetivo, el costo restante real es cero, por lo que su estimación también debe ser cero. Admisible no significa precisa: cero en todas partes es seguro, pero no proporciona orientación.

En el mapa de carreteras del ejemplo, las estimaciones y las distancias restantes mínimas exactas hasta G son:

Cada estimación es como máximo su costo real. En un problema grande, calcular estos costos exactos puede ser tan difícil como la búsqueda original. En ese caso, una demostración basada en la estructura del problema es más útil que una tabla exhaustiva.

Comprueba cada acción

La consistencia, también llamada monotonicidad, requiere $h(n)\le c(n,a,n^{\mathrm{\prime }})+h(n^{\mathrm{\prime }})$ para cada acción, además de cero en los objetivos. La estimación actual no puede superar el costo de un paso más la estimación del sucesor.

En el mapa de carreteras, A→C da $7\le 4+4$, C→B da $4\le 1+5$ y D→G da $2\le 2+0$. Las carreteras de doble sentido requieren comprobar ambas direcciones. Se cumplen las 16 comprobaciones dirigidas para estas estimaciones.

Sumar las desigualdades a lo largo de un camino hasta un objetivo cancela las estimaciones intermedias. En un camino óptimo da $h(n)\le h^{\ast }(n)$, por lo que la consistencia implica admisibilidad. También da

Las prioridades no pueden disminuir a lo largo de un camino. Por tanto, la primera expansión de un estado se realiza por un camino de menor costo, aunque su primera generación haya sido más costosa.

Descubre por qué la admisibilidad por sí sola necesita reapertura

Considera las carreteras de doble sentido S–A 1, A–C 1, S–B 1, B–C 2 y C–G 3. Sean las estimaciones S 0, A 4, B 1, C 1 y G 0. No superan los costos reales S 5, A 4, B 5, C 3 y G 0, por lo que son admisibles. Pero A→C incumple la consistencia: $4>1+1$.

A* expande S, luego B con prioridad 2 y después C, alcanzado con costo 3 y prioridad 4. Luego expande A con prioridad 5 y descubre un camino menos costoso hacia C de costo 2. Rechazar C permanentemente porque está cerrado deja un objetivo de costo 6. Reabrir C propaga la mejora y produce el óptimo, de costo 5.

Ajusta la heurística al modelo de movimiento

La distancia de Manhattan es admisible y consistente para movimientos horizontales y verticales de una unidad. Si los movimientos diagonales también cuestan 1, ir de (0,0) a (3,3) solo requiere tres movimientos, mientras que la distancia de Manhattan indica 6. Para ese modelo de movimiento, $\max (\mathrm{\mid }\mathrm{\Delta }x\mathrm{\mid },\mathrm{\mid }\mathrm{\Delta }y\mathrm{\mid })$ da la distancia sin obstáculos. La garantía de una heurística pertenece a un modelo de acciones concreto.

Para diseñar una estimación segura, resuelve una versión más fácil del problema. Un problema relajado elimina restricciones de las acciones, por lo que todas las soluciones originales siguen disponibles. Su costo mínimo no puede superar el costo mínimo original.

Elimina restricciones de forma deliberada

Un costo relajado exacto es una heurística admisible. También es consistente cuando las acciones originales siguen disponibles con sus costos: dar un paso original y después seguir una ruta relajada óptima es una posible ruta relajada, por lo que el óptimo relajado no puede costar más.

En el rompecabezas de 8 fichas, una ficha solo puede moverse a una casilla adyacente cuando esa casilla está vacía. Elimina el requisito de que esté vacía y las fichas podrán pasar por casillas ocupadas. Cada ficha numerada necesita entonces al menos su distancia horizontal más vertical hasta su objetivo. La suma da la distancia de Manhattan, $h_2$.

Elimina también la adyacencia y cada ficha mal colocada podrá saltar directamente a su objetivo en un movimiento. El costo resultante es el número de fichas mal colocadas, $h_1$. Ambas son fáciles de calcular sin buscar en el rompecabezas original.

Calcula ambas estimaciones

Para el objetivo «1 2 3 / 4 5 6 / 7 8 casilla vacía», considera «5 1 3 / 4 casilla vacía 2 / 7 8 6». Numera las filas y las columnas desde 1.

Las demás fichas numeradas ya están en su lugar. Cuatro están mal colocadas, por lo que $h_1=4$. Sus distancias suman $2+1+2+1=6$, por lo que $h_2=6$. La solución óptima requiere 12 movimientos; las relajaciones ignoran interacciones que generan trabajo adicional.

No cuentes la casilla vacía. A un movimiento del objetivo, una ficha numerada y la casilla vacía están ambas desplazadas. Contar ambas daría 2 cuando el costo real es 1. La casilla vacía permite los movimientos; no es una ficha adicional cuyo costo deba contarse.

Almacena subproblemas resueltos

Una base de datos de patrones registra los costos exactos de un subproblema seleccionado, como colocar correctamente las fichas 1 a 4 tratando las demás como intercambiables. Construye la tabla una sola vez mediante búsqueda hacia atrás desde el objetivo. Durante una nueva búsqueda, usa una consulta en lugar de resolver de nuevo el subproblema.

El subproblema no necesita más trabajo que el problema completo, lo que da una cota inferior. Sin embargo, sumar dos costos ordinarios de patrones puede cobrar dos veces el mismo movimiento real. La suma es segura para patrones disjuntos cuando cada base de datos cuenta solo los movimientos de sus propias fichas. Que los nombres de las fichas sean disjuntos no establece por sí solo esa regla de contabilización de costos.

Combina estimaciones seguras

El máximo de estimaciones admisibles es admisible:

Cada candidata se mantiene por debajo del costo restante real, por lo que su máximo también lo hace. Es al menos tan informativo como cada estimación individual. Una suma simple carece de esta protección.

Una heurística aprendida de ejemplos resueltos puede predecir bien el costo restante en promedio. La precisión promedio no establece una cota inferior para cada estado. Solo conserva la garantía de A* con heurística admisible cuando se demuestra que sus estimaciones nunca sobreestiman.

Una estimación más cercana puede reducir la exploración, pero una estimación costosa puede hacer que la búsqueda sea más lenta. Compara tanto la información proporcionada como el cálculo total requerido.

Establece la dominancia en todos los estados

Una heurística admisible $h_2$ domina a la admisible $h_1$ si $h_2(n)\ge h_1(n)$ en todas partes. Un tablero favorable no basta para demostrar esta relación.

La distancia de Manhattan domina al número de fichas mal colocadas en el rompecabezas de 8 fichas. Cada ficha mal colocada debe recorrer al menos una casilla, por lo que su contribución a Manhattan es al menos el 1 que cuenta la heurística más débil. Una ficha bien colocada aporta cero a ambas.

Con estimaciones consistentes, A* debe expandir los caminos con $g+h<C^{\ast }$. Aumentar una estimación segura elimina algunos caminos de esta región de expansión obligatoria. Una heurística consistente dominante no expande más nodos, salvo por diferencias en los empates. Una estimación inadmisible puede ser aún mayor, pero pierde la garantía de optimalidad y no cumple los requisitos de esta comparación de dominancia.

Resume el esfuerzo de búsqueda

El factor de ramificación efectivo, $b^{\ast }$, describe la anchura de un árbol uniforme equivalente. Cuenta $N$ nodos generados por debajo de la raíz y sea $d$ la profundidad de la solución. Resuelve

El 1 adicional corresponde a la raíz. Es importante contar de forma consistente: si una medición ya incluye la raíz, no la añadas dos veces.

Para 52 nodos generados por debajo de la raíz y profundidad de solución 5, el total es 53 y $b^{\ast }\approx \mathrm{1,92}$. Para 1000 nodos generados y profundidad 8, $b^{\ast }\approx \mathrm{2,20}$. Encuentra estos valores numéricamente aumentando o disminuyendo un valor de prueba hasta que su suma geométrica coincida con el total de nodos.

Un valor cercano a 1 indica una búsqueda estrecha. Compara resultados entre instancias representativas, con la misma regla de conteo y profundidades de solución comparables. El factor de ramificación efectivo puede ayudar a estimar la escalabilidad, pero una instancia inusualmente fácil no es una predicción fiable para toda una familia de problemas.

Mide el tiempo de todo el cálculo

Supón que un nodo tarda 10 microsegundos, incluido 1 microsegundo para evaluar la heurística anterior. Una sustituta reduce a la mitad el número de nodos, pero tarda 100 microsegundos por evaluación. El trabajo ajeno a la heurística sigue costando 9 microsegundos, por lo que el nuevo total por nodo es 109. La razón del tiempo total es

La búsqueda es unas 5,5 veces más lenta a pesar de visitar menos nodos. Si la nueva evaluación tarda solo 2 microsegundos, el total por nodo pasa a 11 y la razón de tiempos es $\mathrm{0,5}\times 11\mathrm{/}10=\mathrm{0,55}$. Eso es aproximadamente 1,8 veces más rápido.

Una base de datos de patrones también tiene un costo de construcción. Muchas búsquedas con el mismo objetivo pueden compartir esa inversión; una sola búsqueda pequeña podría no compensarla. Mide por separado el preprocesamiento, el tiempo de consulta, los nodos generados y la memoria para no confundir menos expansiones con una mejora automática de velocidad.

La búsqueda local modifica repetidamente una respuesta candidata completa. Es adecuada para tareas en las que importa la configuración final y puede descartarse la secuencia usada para encontrarla.

Representa una candidata completa

Para las 8 reinas, coloca una reina en cada columna. Representa el estado mediante los ocho números de fila, leyendo las columnas de izquierda a derecha. Todos los estados tienen las ocho reinas, incluidos los estados con conflictos. Un vecino mueve una reina a otra fila de su propia columna.

Hay $8^8=16777216$ estados y $8\times 7=56$ vecinos por estado. Un número fijo de estados actuales sustituye la gran frontera y los registros de padres de la búsqueda de caminos. El almacenamiento sigue dependiendo del tamaño de un estado; conservar una tupla de ocho entradas ocupa menos que conservar un horario enorme.

La elaboración de horarios, la disposición de chips y la elección de un recorrido completo por ciudades siguen el mismo patrón general: cada estado es una propuesta completa. Un recorrido es en sí mismo una disposición candidata, aunque su contenido describa un viaje. La búsqueda local no necesita conservar la secuencia de cambios usada para mejorar ese recorrido.

Define qué significa mejor

Una función objetivo da a cada estado una puntuación que se maximiza. De forma equivalente, define un costo que se minimiza. Para n reinas, haz que $h$ cuente las parejas de reinas que se atacan entre sí. Cuenta cada pareja una vez, incluidos los ataques por filas o diagonales incluso cuando hay otra reina entre ellas. Una solución tiene $h=0$.

Para cuatro columnas, la tupla (1,2,3,4) coloca todas las reinas en una diagonal. Sus $\left(\genfrac{}{}{0px}{}{4}{2}\right)=6$ parejas se atacan. La tupla (2,1,3,4) tiene dos parejas que se atacan, mientras que (2,4,1,3) no tiene ninguna. Aquí los valores menores son mejores; la letra $h$ es un costo objetivo, no una estimación del costo restante del camino usada por A*.

Interpreta el paisaje

Imagina la calidad de los estados como altura. Para maximizar:

• Un máximo global tiene el mejor valor de todo el espacio.
• Un máximo local es mejor que sus vecinos, pero puede ser peor que un estado lejano.
• Una meseta es una región plana conectada. Puede ser un máximo local plano sin salida ascendente o una meseta con salida desde la que los movimientos laterales pueden alcanzar una salida ascendente.
• Una cresta puede ascender en una dirección que los movimientos individuales disponibles no pueden seguir. Cada elección inmediata puede parecer peor.

Para minimizar el costo, invierte la altura: la búsqueda persigue mínimos y valles. Un mínimo local no demuestra que no exista en otro lugar un estado de menor costo. El vecindario determina qué estados pueden compararse en un paso, por lo que cambiar la modificación permitida puede cambiar dónde se atasca la búsqueda.

Comprueba que puede ignorarse el camino

Un agente de búsqueda de rutas debe devolver acciones válidas desde su inicio real. Un buen destino por sí solo no basta. La búsqueda local suele devolver solo el estado candidato, sin una cadena de padres que recorra todas las modificaciones anteriores.

Un método de búsqueda local completo encontraría un objetivo siempre que existiera; uno óptimo encontraría el mejor estado global. Los métodos locales básicos no ofrecen ninguna de estas garantías generales. Su atractivo es que pueden alcanzar buenos candidatos rápidamente cuando no es práctico almacenar un árbol de búsqueda sistemática.

El ascenso de colinas realiza la mejor mejora inmediata que puede encontrar. Para una puntuación que se maximiza, el ascenso de máxima pendiente elige el vecino con mayor puntuación. Para un costo que se minimiza, elige el vecino de menor costo. Se detiene cuando no existe una mejora estricta.

Sigue una ejecución con cuatro reinas

Sea un estado la lista de la fila de la reina en cada columna y sea $h$ el número de parejas que se atacan. Comienza con (1,2,3,4), cuyo costo es 6.

1. Evalúa los movimientos de una reina. Un mejor vecino es (2,2,3,4), con costo 4.
2. Desde ahí, un mejor vecino es (2,1,3,4), con costo 2.
3. Ningún vecino obtenido moviendo una reina tiene costo inferior a 2. El ascenso de colinas estricto se detiene.

La disposición de costo cero (2,4,1,3) existe, pero no puede alcanzarse mediante un movimiento que mejore inmediatamente el estado en el que se detuvo la búsqueda. Esto es una consecuencia de la regla local, no una prueba de que el programa haya contado mal los conflictos.

Permite movimientos laterales útiles

Un movimiento lateral mantiene la misma puntuación. Puede cruzar una meseta con salida hasta una salida que mejore el valor, pero también puede vagar por un óptimo local plano. Limita los movimientos laterales consecutivos para evitar ciclos interminables.

En el experimento de 8 reinas descrito por Russell y Norvig, el ascenso de máxima pendiente desde inicios aleatorios tiene éxito alrededor del 14 % de las veces, con unos 4 pasos cuando tiene éxito y 3 cuando se atasca. Permitir hasta 100 movimientos laterales consecutivos eleva el éxito registrado a alrededor del 94 %, con unos 21 pasos por éxito y 64 por fallo. Son resultados de ese experimento, no tasas de éxito universales del ascenso de colinas.

Cambia cómo se elige un vecino

El ascenso de colinas estocástico selecciona al azar un vecino que mejora el estado, posiblemente favoreciendo las mejoras mayores. El ascenso de colinas por primera elección muestrea vecinos uno por uno y toma la primera mejora. Evita evaluar un vecindario enorme antes de cada movimiento. Ambos siguen rechazando los movimientos peores.

El ascenso de colinas con reinicio aleatorio comienza una nueva ejecución desde un estado recién muestreado después de una ejecución fallida. Con ejecuciones independientes de probabilidad de éxito $p$, el número esperado de ejecuciones hasta el primer éxito es $1\mathrm{/}p$. Para $p=\mathrm{0,14}$, son unas 7 ejecuciones. Usando los números de pasos registrados, el número esperado de pasos totales es

Las ejecuciones fallidas también aportan trabajo. Con probabilidad de éxito positiva y reinicios independientes, la probabilidad de acabar teniendo éxito se aproxima a 1 a medida que crece el número de ejecuciones.

Deja que varios candidatos compartan hallazgos

La búsqueda local en haz mantiene $k$ estados, genera sus vecinos conjuntamente y conserva los $k$ mejores de ese conjunto común. Un padre prometedor puede aportar varios supervivientes mientras que otro no aporta ninguno. Esta puesta en común la distingue de los reinicios independientes.

La puesta en común también puede hacer que todos los candidatos se agrupen en una región. La búsqueda en haz estocástica muestrea los supervivientes con una probabilidad que aumenta con la calidad para conservar más variedad. La elección entre movimientos laterales, reinicios y diversidad de la población depende de por qué falla el progreso: un puente cercano de igual valor, una mala región inicial o demasiados candidatos que exploran la misma zona.

Algunos paisajes requieren una pérdida temporal antes de que pueda alcanzarse un estado mejor. El recocido simulado permite esos movimientos con una probabilidad controlada. Los algoritmos genéticos, en cambio, exploran seleccionando y combinando candidatos completos.

Acepta a veces un movimiento peor

El recocido simulado muestrea un vecino aleatorio. Acepta un movimiento que mejora el estado. Para una función objetivo que se maximiza, escribe su cambio como $\mathrm{\Delta }E$. Si $\mathrm{\Delta }E<0$, acepta el movimiento peor con probabilidad

Para minimizar un costo, sea $\mathrm{\Delta }$ el aumento del costo. Un movimiento peor tiene entonces $\mathrm{\Delta }>0$ y probabilidad de aceptación $e^{-\mathrm{\Delta }\mathrm{/}T}$. Los movimientos de igual valor tienen probabilidad 1 según cualquiera de las dos fórmulas. La temperatura y los cambios de la función objetivo deben usar una escala numérica compatible.

Una caída de la puntuación de 2 se acepta con probabilidad aproximada de 0,819 a temperatura 10, de 0,135 a temperatura 1 y de 0,018 a temperatura 0,5. A temperatura 10, una caída mayor de 5 tiene probabilidad aproximada de 0,607. Así, la temperatura controla la tolerancia, mientras que el tamaño de la pérdida sigue importando a una misma temperatura.

Reduce la temperatura

Un programa de enfriamiento fija la temperatura a lo largo del tiempo. El enfriamiento geométrico usa $T_{k+1}=\alpha T_k$ con un factor cercano a 1, como 0,95. A temperatura alta se aceptan muchos movimientos peores y la exploración se parece a un paseo aleatorio. Cerca de cero, los movimientos peores son poco frecuentes y el comportamiento se parece al ascenso de colinas.

Enfriar demasiado rápido puede atrapar la búsqueda antes de que escape de una mala región. Enfriar muy lentamente aumenta el cálculo. El resultado asintótico de óptimo global requiere un enfriamiento suficientemente lento y la capacidad habitual de alcanzar estados a través del vecindario; una ejecución geométrica finita ordinaria no asegura el éxito global. Usado para la disposición de chips y la programación de tareas desde la década de 1980, el método toma su nombre de calentar y enfriar lentamente un metal para que se asiente en una estructura de menor energía.

Construye una nueva población

Un algoritmo genético representa los candidatos como cadenas. Cada generación puntúa su aptitud, selecciona progenitores dando preferencia a una mayor aptitud, crea descendientes mediante cruce y aplica mutaciones ocasionales.

Para las 8 reinas, ocho dígitos de fila describen una reina por columna. La aptitud puede contar las parejas que no se atacan, con 28 como máximo. Corta las cadenas de los progenitores «64751517» y «64278273» después del cuarto dígito. Al combinar mitades opuestas se obtienen «64758273» y «64271517».

Los progenitores tienen aptitudes de 23 y 24; los descendientes, de 27 y 21. Un descendiente mejora a ambos progenitores, mientras que el otro es peor. El cruce ofrece nuevas combinaciones, no una garantía de mejora. Es útil cuando los buenos bloques tienden a conservar su valor al combinarse. La mutación cambia ocasionalmente una posición y ayuda a introducir variedad más allá de esas combinaciones.

La selección, el cruce y la mutación cumplen funciones distintas: la selección favorece candidatos útiles, el cruce los recombina y la mutación cambia posiciones individuales. Como la búsqueda en haz estocástica, el método mantiene una población, pero los nuevos candidatos pueden tomar material de dos progenitores. Ni un progenitor de alta aptitud ni una temperatura final baja demuestran por sí solos que se haya encontrado el óptimo global.