Algoritmo de alpinismo simple ejemplo

Question

Estoy un poco confundido con el algoritmo Hill Climbing. Quiero "ejecutar" el algoritmo hasta que encontré la primera solución en ese árbol ("a" es inicial yh y k son estados finales) y dice que los números cercanos a los estados son los valores heurísticos. Aquí está el árbol:

Mi pregunta: estoy tratando de correr colina que sube en el árbol, por lo bien que empezamos a-> f-> g y luego qué ?? acabado (sin resultado), pero leí que la escalada no puede regresar y hacer una nueva elección (ejemplo j o e)? Es esto correcto ? Si puedo regresar, ¿cómo? me refiero a donde cambiamos nuestro ejemplo de elección inicial elegimos e en lugar de g o j en lugar de f

Lo siento si mi pregunta es demasiado simple.

Answer 1

La escalada no tiene ninguna garantía contra atascarse en un mínimo/máximo local. Sin embargo, solo la forma más pura de alpinismo no le permite retroceder.

Un riff simple en el alpinismo que evitará el problema de los mínimos locales (a expensas de más tiempo y memoria) es una búsqueda tabú, donde recuerda los malos resultados previos y los evita a propósito.

Answer 2

Una forma común de evitar atascarse en los máximos locales con Hill Climbing es utilizar reinicios aleatorios. En su ejemplo, si G es un máximo local, el algoritmo se detendrá allí y luego elegirá otro nodo aleatorio para reiniciar. Entonces, si J o C fueran escogidos (o posiblemente A, B, o D), usted encontraría los máximos globales en H o K. Enjuague y repita suficientes veces y encontrará los máximos globales o algo cercano; dependiendo de las limitaciones de tiempo/recursos y el espacio problemático.

Tenga en cuenta que la búsqueda local como Hill Climbing no está completa y no puede garantizar la búsqueda de los máximos globales. El beneficio, por supuesto, es que requiere una fracción de los recursos. En la práctica y aplicado a los problemas correctos, es una solución muy efectiva.

Answer 3

uno de los problemas con la escalada se queda atascado en los mínimos locales & esto es lo que sucede cuando llegas a F. Una versión mejorada de la escalada (que en realidad se usa prácticamente) es reiniciar todo el proceso seleccionando un nodo aleatorio en el árbol de búsqueda & nuevamente continúe hacia la búsqueda de una solución óptima. Si una vez más te quedas atascado en algunos mínimos locales, debes reiniciar nuevamente con algún otro nodo aleatorio. En general, hay un límite en el no. de tiempo puede volver a hacer este proceso de encontrar la solución óptima. Después de alcanzar este límite, selecciona el mínimo entre todos los minimas locales que alcanzó durante el proceso. Aunque todavía no está completo, pero este tiene mejores posibilidades de encontrar la solución óptima global.

Answer 4

Puede intentar utilizar una técnica llamada simulated annealing para evitar que su búsqueda se atasque en los mínimos locales. Esencialmente, en el recocido simulado, existe un parámetro T que controla su probabilidad de realizar un cambio a estados vecinos no óptimos. Si T es alto, es más probable que realice un movimiento subóptimo a un estado vecino y, por lo tanto, podría escapar a un mínimo local cuando se quede atascado allí, lo que no ocurriría si utilizara la escalada normal.

Answer 5

Actualmente, en Hill Climbing generalmente no retrocedes, porque no estás siguiendo el estado (es búsqueda local) y te estarías alejando de un máximo. Ni retroceder ni Tabu Search ayudan a responder la pregunta: la primera simplemente te aleja de un máximo local y la segunda te impide volver a visitar los mismos máximos locales. Ninguno de los dos te ayudaría a alcanzar un máximo global.- Tyson 16 de octubre de 12 a 22:59

"donde recuerdas malos resultados previos y los evitas a propósito" No puedo estar de acuerdo, marcas como tabú también buenas soluciones, pero no quieres seguir el mismo camino de nuevo. -

Answer 6

Aquí está la solución:

A -> F, con el menor coste posible F -> G con el coste 3 pero no hay camino.

Reinicie desde el menor costo posible que no sea G, bueno, es E porque E ya estaba insertado en la cola de cola/pila/prioridad o cualquier estructura de datos que use.

lo tanto E -> I pero tiene costo mayor que E por lo tanto usted está atascado: S

Reiniciar en el menor costo que no sea FE & G, por lo tanto nos recoger J porque J tiene costo menor que B con diferencia de 2 es decir, J = 8 B = 10

J-> K con coste 0 por lo tanto K es el objetivo

NOTA: la variación propuesta de bajada para recoger un punto al azar, pero recogiendo el menor coste otro que los nodos ya visitados es mejor que elegir aleatoriamente.

OTRA NOTA: cuando el nodo E no visitó I porque tengo un valor mayor que E, el algoritmo ya lo insertó en la estructura de datos, por lo que elegir el menor costo aparte de los ya visitados crearía una nueva ruta de I porque nunca fui visitado y, por lo tanto, tiene un valor inferior al de J, este es el único camino que he omitido.

Answer 7

la ruta de acuerdo con subida de la colina pura será a-> J -> k si expande de niños de izquierda a derecha, si a ampliar de derecha a izquierda por lo que recibirá en este mínimos local A - > F -> G, pero generalmente nos expandimos de izquierda a derecha.