Monografias.com > Computación > Programación
Descargar Imprimir Comentar Ver trabajos relacionados

Resolución de problemas mediante búsqueda




Enviado por Pablo Turmero



Partes: 1, 2

    Monografias.com

    Introducción
    Agentes basados en el objetivo de resolución de problemas.
    Necesaria una formulación de objetivos.
    Estados y posibles acciones.
    Ejemplo de mapa de carreteras.
    Un agente simple de resolución de problemas:

    La función RECOMMENDATION devuelve la primera acción en la secuencia.
    La función REMAINDER devuelve el resto.

    Monografias.com

    Formulación de problemas, I
    Problema de aspiradora:
    8 posibles estados
    Los estados están contenidos en esta figura:

    Dos tipos de problemas:
    Problemas de estados únicos.
    Aparecen en entornos accesibles (la percepción determina completamente el estado) y deterministas.
    Problemas de estados múltiples.
    Aparecen por ejemplo en entornos no accesibles o no deterministas.
    Ejemplo (sin sensores; determinista, pero no accesible):

    Monografias.com

    Formulación de problemas, II
    Si el entorno es no determinista (por ejemplo, “La absorción deposita algunas veces suciedad, pero sólo cuando previamente no hay suciedad”):
    Si el entorno es accesible, para cada estado inicial, hay una secuencia fija de operadores que llevan al objetivo.
    Si el entorno es semiaccesible (por ejemplo, si tenemos un sensor de posición y un sensor local del estado de suciedad):
    entonces, no hay una secuencia fija que garantice una solución a partir de cualquier estado:
    Estados (A=aspiradora, S=suciedad):
    (1, AS, S), (2, S, AS), (3, AS, )
    (4, S, A), (5, A, S), (6, , AS)
    (7, A, ), (8, , A)

    Monografias.com

    Formulación de problemas, III

    {1,3} –(absorción)–>{5,7}–(derecha)–> {6,8}–(absorción)–>{6,8}
    La solución sería: absorción, derecha, absorción, “absorción si sucio”. Es un árbol de posibles acciones (problema con contingencias).
    Posibles operadores para el estado inicial {1,3}:

    {1,3}
    {5,7}
    {2,4}
    {6,8}
    {5,1,7,3}
    S
    L
    S
    R
    L
    R
    S
    L
    R
    L
    R
    S
    {………}

    Monografias.com

    Problemas bien definidos
    Consideramos los problemas más sencillos (problema de estado único):
    Estado inicial
    Espacio de estados.
    Posibles acciones (operadores) sobre cada estado.
    Cada operador obtiene un estado a partir de otro estado.
    Función objetivo (estados objetivo).
    Función de coste de aplicación de los operadores.
    Un problema de estados múltiples es un caso particular del caso de un problema de estado único, en donde cada estado es un multiestado:
    Estado inicial: multiestado
    Cada operador obtiene un multiestado a partir de otro multiestado.

    Monografias.com

    Ejemplos, I
    Los objetivos de la resolución de un problema mediante búsqueda son:
    Encontrar una solución
    La solución debe tener coste total mínimo:
    Coste de búsqueda:
    Tiempo y memoria necesarios.
    Coste del camino solución.
    Ejemplos:
    Problema del 8-puzle.
    Coste operadores: 1
    Problema de las 8 reinas (en general de las N reinas/damas):
    Coste operadores: 1 (el camino solución siempre tiene coste 8).
    Posible representación (1):
    estado: n reinas en el tablero
    operadores: añadir una reina a una posición vacía.

    Monografias.com

    Ejemplos, II
    Posible representación (2):
    estado: n reinas en el tablero (no atacándose).
    Operadores: añadir una reina en la columna vacía más a la izquierda tal que no sea atacada por ninguna de las ya existentes.
    Menos operadores que en la representación 1.
    Criptoaritmética.

    Estados: algunas letras sustituidas por dígitos.
    Operadores: sustituir una letra por un dígito que no aparece ya dentro del estado.
    La solución se encuentra a profundidad conocida.

    FORTY
    + TEN
    TEN
    ——
    SIXTY

    29786
    + 850
    850
    ——
    31486

    Monografias.com

    Ejemplos, III
    Ejemplo de aspiradora.
    Entorno accesible y determinista.
    Estados: 8.
    Operadores: L, R, S
    Estados objetivo: 7, 8
    Coste: 1

    Agente sin sensores (entorno no accesible, pero determinista)
    Estados: subconjuntos de los 8
    Coste: 1
    Estados objetivo: estados formados por una combinación de 7,8.

    Monografias.com

    Ejemplos, IV
    Misioneros y caníbales.
    Hay 3 misioneros y 3 caníbales en la orilla izquierda de un río. Un bote puede transportar a 1 o 2 personas de una orilla a otra. Objetivo: pasar a todos a la otra orilla.
    Condición: “No puede ocurrir nunca que si en una orilla hay algún misionero, haya a la vez un número mayor de caníbales (se los comerían).”
    Estados:
    Parámetros: número misioneros lado izquierdo, número caníbales lado izquierdo, posición bote (izquierda o derecha).
    Se debe verificar la Condición.
    Operadores:
    Transportar 1 misionero.
    Transportar 1 canibal.
    Transportar 2 misioneros.
    Transportar 2 caníbales.
    Transportar 1 misionero y 1 caníbal.
    Coste operador: 1.

    Monografias.com

    Ejemplos, V
    Otros ejemplos (más reales):
    Problema de mapa de carreteras.
    Viajar de una ciudad a otra recorriendo la menor distancia posible.
    Problema del viajante de comercio.
    Un viajante debe viajar recorriendo un conjunto de ciudades. Debe partir de una ciudad inicial y, tras recorrer todas las ciudades, volver a la ciudad de inicio.
    Problema clásico: debe visitar exactamente 1 vez todas las ciudades (excepto la de inicio que la visita 2 veces).
    Diseño de circuitos.
    Navegación de robots.
    Montaje mecánico de robots.
    Planificación de toma de imágenes (telescopio Hubble).

    Monografias.com

    Algoritmo general de búsqueda, I
    Problema del mapa de carreteras:
    Espacio de estados (finito).
    Árbol de nodos (infinito), generable.

    Un nodo:
    Un estado (del espacio de estados).
    Su nodo padre.
    Operador que lo generó.
    Profundidad en el árbol de búsqueda.
    Coste desde nodo inicial.

    Monografias.com

    Algoritmo general de búsqueda, II
    Algoritmo general de búsqueda (pseudo-C):
    funcion búsqueda-general
    (problema, estrategia)
    returns una solución o fallo {
    “inicializa árbol de búsqueda con
    estado inicial”
    loop {
    if “no es posible expandir ninguna hoja”,
    return fallo
    “elige un nodo hoja a expandir,
    según la estrategia”
    if “el nodo es objetivo”,
    return “la solución”
    else “expande nodo y añade los nodos
    resultantes al árbol de búsqueda”
    }
    }
    Con más detalle:

    Partes: 1, 2

    Página siguiente 

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter