Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 32 vistas

    Inteligencia Artificial

    Cargado por

    Ferney Gustavo Gutierrez Sepulveda
    El documento describe diferentes métodos de ascensión de colinas para la resolución de problemas de búsqueda. El algoritmo de ascensión de colinas básico selecciona el primer movimiento que mejora el estado actual, mientras que la ascensión de colinas por máxima pendiente selecciona el mejor movimiento. El documento también presenta algoritmos formales e informales de ascensión de colinas y discute problemas como máximos locales y crestas, así como posibles soluciones.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Inteligencia Artificial

    Cargado por

    Ferney Gustavo Gutierrez Sepulveda
    32 vistas7 páginas
    El documento describe diferentes métodos de ascensión de colinas para la resolución de problemas de búsqueda. El algoritmo de ascensión de colinas básico selecciona el primer movimiento que mejora el estado actual, mientras que la ascensión de colinas por máxima pendiente selecciona el mejor movimiento. El documento también presenta algoritmos formales e informales de ascensión de colinas y discute problemas como máximos locales y crestas, así como posibles soluciones.

    Descripción original:

    buen libro

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    El documento describe diferentes métodos de ascensión de colinas para la resolución de problemas de búsqueda. El algoritmo de ascensión de colinas básico selecciona el primer movimiento que mejora el estado actual, mientras que la ascensión de colinas por máxima pendiente selecciona el mejor movimiento. El documento también presenta algoritmos formales e informales de ascensión de colinas y discute problemas como máximos locales y crestas, así como posibles soluciones.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    32 vistas7 páginas

    Inteligencia Artificial

    Cargado por

    Ferney Gustavo Gutierrez Sepulveda
    El documento describe diferentes métodos de ascensión de colinas para la resolución de problemas de búsqueda. El algoritmo de ascensión de colinas básico selecciona el primer movimiento que mejora el estado actual, mientras que la ascensión de colinas por máxima pendiente selecciona el mejor movimiento. El documento también presenta algoritmos formales e informales de ascensión de colinas y discute problemas como máximos locales y crestas, así como posibles soluciones.

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    Está en la página 1de 7

    Búsqueda de ascensión de

    colinas
    • Ascensión de colinas (AdC) simple:
    – Se busca una cualquier operación que
    suponga una mejora respecto al estado
    actual.
    • Ascensión de colinas por máxima
    pendiente (steepest-ascent hill
    climbing, gradient search):
    – Se selecciona el mejor movimiento (no el
    primero de ellos) que suponga mejora
    respecto al estado actual.
    Ascensión de colinas: algoritmo
    informal
    1. Set L to be a list of the initial nodes in the problem,
    sorted by their expected distance to the goal. Nodes
    expected to be close to the goal should precede those
    that are farther from it.
    2. Let n be the first node on L. If L is empty, fail.
    3. If n is a goal node, stop and return it and the path from
    the initial node to n.
    4. Otherwise, remove n from L. Sort n's children by their
    expected distance to the goal, label each child with its
    path from the initial node, and add the children to the
    front of L. Return to step 2.
    Ascensión de colinas: algoritmo
    formal
    Algoritmo Hill Climbing
    Actual= Estado_inicial
    fin = falso
    Mientras ¬fin hacer
    Hijos= generar_sucesores(Actual)
    Hijos= ordenar_y_eliminar_peores(Hijos, Actual)
    si ¬vacio?(hijos) entonces Actual= Escoger_mejor(Hijos)
    si no fin=cierto
    fMientras
    fAlgoritmo

    • Sólo se consideran los descendientes cuya


    función de estimación es mejor que la del padre
    (poda del espacio de búsqueda).
    • Se puede usar una pila y guardar los hijos
    mejores que el padre para poder volver atrás, pero
    en general el coste es prohibitivo.
    Ascensión de colinas
    • Las características de la función heurística
    determinan la calidad del resultado y la
    rapidez de la búsqueda.
    • Problemas:
    – Máximo local. Todos los vecinos tienen función
    heurística peor.
    – Meseta. Todos los vecinos tienen la misma
    función heurística que el nodo actual.
    – Crestas: Las crestas causan una secuencia de
    máximos locales que hace muy difícil la
    navegación para los algoritmos avaros. 8
    Ascensión de colinas
    • Soluciones:
    – Volver a un nodo anterior y seguir el proceso
    en otra dirección (prohibitivo en espacio).
    – Reiniciar la búsqueda en otro punto.
    – Aplicar dos o más operadores antes de
    decidir el camino.
    – Hacer AdC en paralelo.
    • Ejemplo: dividir el espacio de búsqueda en
    regiones y explorar las más prometedoras.

    9
    El problema de las 8-reinas
    • Los algoritmos de BL típicamente usan
    una formulación de estados completa.
    – Cada estado tiene a ocho reinas sobre el
    tablero, una por columna.
    • La función sucesor devuelve todos los
    estados posibles generados moviendo
    una reina a otro cuadrado en la misma
    columna.
    – Cada estado tiene 8 x 7 = 56 sucesores.
    10
    El problema de las 8-reinas
    • La función de costo heurística h es el
    número de pares de reinas que se atacan
    la una a la otra, directa o indirectamente.
    – Problema de minimización
    • El mínimo global de esta función es cero.
    – Ocurre sólo en soluciones perfectas.
    • Estado inicial: cualquiera.

    11

    También podría gustarte