Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Solución a problemas de búsquedaEstrategias de búsqueda y Estructura de la solución
Hugo Franco, PhD
Inteligencia ArtificialIngeniería de Sistemas
15 de marzo de 2021
Hugo Franco, PhD Solución a problemas de búsqueda
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Repaso para análisis: Problema del agente viajero
Problema: determinar la mejor ruta que permita al agente visitar todas lasubicaciones una sola vez y regresar al lugar de partida
Estados: ubicaciones del viajero en cada instante incluyendo la lista deubicaciones previamente visitadas.Estado inicial: punto de partida y llegada del viajeroAcciones: viajar de la ubicación actual a alguna de las ciudades vecinasModelo de transiciones: el siguiente estado después de una evaluaciónactualiza la ubicación “actual” del viajero y la lista de ciudades visitadasPrueba de éxito: evaluar si la ubicación actual del viajero es igual a supunto de partida y la lista de ubicaciones visitadas contiene todas lasdemás ubicaciones (vértices) una única vez.Función de costo: determinada por los pesos de las aristas (costo de lostrayectos)
Hugo Franco, PhD Solución a problemas de búsqueda
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Formas de representación
En ciertos problemas de búsqueda, elespacio de estados se puede representarcomo un grafo que contiene lascaracterísticas del problema.
Diferentes tipos de recorridos permitenmodelar y dar solución a problemasasociados a rutas y caminos
En otros problemas, la exploración delespacio de estados se puede implementarcomo el proceso de expandir y recorrerun árbol.
Esto es necesario en problemas cuyoespacio de estados no se puederepresentar de forma exhaustiva
Hugo Franco, PhD Solución a problemas de búsqueda
Estructura de la solución a problemasde búsqueda
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Expansión de estados y frontera:
Expansión de estados
Aplicar cada acción válida (arista incidente) al estado actual, generandoun nuevo conjunto de estados.
FronteraConjunto de vértices del árbol disponibles para ser expandidos hasta unpunto dado (iteración) de la exploración del espacio de estados. Son lashojas del árbol hasta donde ha sido construido en la búsqueda.
Un estado repetido en el espacio de búsqueda conduce a laaparición de circuitos, que elevan la complejidad del algoritmo queimplementa la estrategia de búsqueda, lo que debería evitarse.La estrategia de búsqueda debería evitar rutas redundantes queconducen a soluciones de mayor costo (indeseadas)
Hugo Franco, PhD Solución a problemas de búsqueda
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Ejemplo: rutas de tren en España
Considérese el siguiente grafo. Encontrar la ruta de menor costo(distancia, precio, duración) desde Coruña hasta Valencia
Hugo Franco, PhD Solución a problemas de búsqueda
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Proceso de búsqueda general (ejemplo)
Hugo Franco, PhD Solución a problemas de búsqueda
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Ejemplo: Estado Inicial
El primer vértice corresponde al primer estado evaluado en el proceso debúsqueda de una solución, en este caso el lugar de partida.
Hugo Franco, PhD Solución a problemas de búsqueda
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Ejemplo: Después de expandir el primer vértice
Se evalúan los nodos contiguos a la raíz del árbol de búsqueda en elespacio de estados.
Hugo Franco, PhD Solución a problemas de búsqueda
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Ejemplo: tras expandir los hijos del nodo raíz.
Se expanden los nodos de la frontera del paso anterior, generando unanueva frontera y avanzando en la exploración del espacio de búsqueda.
“Valladolid” aparece nuevamente en la siguiente evaluación. Se viola ladefinición del árbol
Las rutas Coruña-Vigo-Valladolid y Coruña-Valladolid son redundantes.
Hugo Franco, PhD Solución a problemas de búsqueda
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Búsqueda general (sobre árboles)
El siguiente es un ejemplo de implementación general (abstracta) de unalgoritmo de solución a problemas de búsqueda.
función BUSQUEDA (problema) retorna una solución, o alerta de falloinicializar la frontera usando el estado inicial del problemahacer
si la frontera es vacía entoncesretornar alerta de fallo
escoger un vértice hoja y eliminarlo de la fronterasi el nodo contiene un estado objetivo (solución) entonces
retornar la solución encontrada
expandir el vértice seleccionado, agregando los nodos resultantes a lafrontera
* Nótese que la búsqueda general no permite evitar el problema de los estadosrepetidos
Hugo Franco, PhD Solución a problemas de búsqueda
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Búsqueda sin estados repetidos (árboles y grafos)
Para evitar los estados repetidos y sus consecuencias computacionales, esnecesario adaptar el algoritmo de búsqueda general para llevar un registro(lista) de los estados previamente explorados.
BÚSQUEDA (problema) retorna un estado solución, o alerta de falloinicializar la frontera usando el estado inicial del problemainicializar la lista de estados explorados a vacíohacer
si la frontera es vacía entoncesreturn alerta de fallo (no encontró la solución)
escoger un vértice hoja y eliminarlo de la fronterasi el vértice contiene un estado objetivo (solución) entonces
retornar la solución encontrada
agregar el vértice a la lista de estados exploradosexpandir el vértice, agregando los estados resultantes a la frontera,solo los vértices que no están ya en la frontera ni en la lista deestados explorados
Hugo Franco, PhD Solución a problemas de búsqueda
Estrategias de solución
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Ejemplo: puzzle de 8 casillas
Estado inicial: {(1,2,5),(3,4,X),(6,7,8)}(Ejemplo de representación seleccionada)Estados: todas las posibles configuraciones delpuzzleAcciones: mover espacio vacío arriba (Up),mover abajo (Down), mover a la izquierda (Left),mover a la derecho (Right).Restricciones: la casilla vacía no puede salirse delos bordes del tablero Prueba de éxito: evaluar silas piezas se encuentran en secuencia ordenadade arriba a abajo y de izquierda a derechoFunción de coste: todos los movimientos tienenel mismo coste (1). Este se acumula en cadapaso.
Hugo Franco, PhD Solución a problemas de búsqueda
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Ejemplo: solución primero en anchura (BFS)
Hugo Franco, PhD Solución a problemas de búsqueda
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Diseño del algoritmo de solución IEstructuras de Datos
De acuerdo con la representación de problemas de búsqueda, laestructura de datos en árbol que permite la implementación de lasdiferentes estrategias de solución debería contener los siguentes atributos:
Estado: identificador único del estadorepresentado por el vértice(árbol)
Padre: identificador o apuntador alvértice padre
Acción: descriptor del tipo de acciónque condujo a la generacióndel vértice
Costo_Ruta: costo acumulado hasta elestado actual
Hugo Franco, PhD Solución a problemas de búsqueda
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Diseño del algoritmo de solución IIEstructura de datos (ejemplo) y acceso
función VÉRTICE-HIJO(problema, padre, acción) retorna unvértice
retornar un vértice con:ESTADO = problema.RESULTADO (padre.ESTADO,
acción),PADRE= padre,ACCIÓN = acción,COSTO_RUTA= padre.COSTO_RUTA +
problema.COSTO_PASO(padre.ESTADO, acción)
Hugo Franco, PhD Solución a problemas de búsqueda
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Diseño del algoritmo de soluciónLista de estados visitados
Dado que es indispensable llevar un registro de los estados visitados hastaun punto dado de la exploración (iteración del algoritmo), se debeimplementar una lista que los contenga, en un orden determinado.
Dicho orden puede ser tipo FIFO, LIFO o lista de prioridad(ordenada según un parámetro de prioridad), de acuerdo con laestrategia de búsqueda empleada.
Esta implementación requiere de las siguientes funciones:Lista_vacía (lista): función booleana cuyo valor de retorno indicasi no hay ningún estado en la lista de visitas.Extraer (vértice, lista): (pop) retorna el primer vértice de la listade visitas y lo elimina de esta.Insertar (vértice, lista): inserta un nuevo vértice en la lista devisitas y retorna la lista completa.
Hugo Franco, PhD Solución a problemas de búsqueda
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Evaluación de desempeño
El diseño, evaluación y selección de los algoritmos que solucionanproblemas de búsqueda en espacios de estado asociados a rutasalternativas que conducen a un estado solución debe guiarse por criteriosde desempeño.
Algunos criterios de desempeño de los algoritmos de búsqueda empleadoscomúnmente son:
1 Completitud: ¿Garantiza el algoritmo de búsqueda que seencontrará una solución si esta existe?
2 Optimalidad: ¿La estrategia seleccionada lleva a la soluciónóptima? (esto es, la solución que implica menor costo)
3 Complejidad en tiempo (instrucciones): ¿Cuánto le lleva alalgoritmo encontrar un estado solución?
4 Complejidad en memoria: ¿Cuánta memoria requiere el algoritmopara llevar a cabo la búsqueda de forma exitosa?
Hugo Franco, PhD Solución a problemas de búsqueda
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Impacto del tamaño del espacio de estados
En problemas abstractos, el costo computacional se estima usando eltamaño del grafo del espacio de estados como parámetro .
La cardinalidad del conjunto de estados más la cardinalidad delconjunto de transiciones posibles.
En problemas reales, el tamaño del espacio de estados puede sermuy grande (incluso infinito), luego su representación es implícita yse requiere una estrategia de solución.
El tiempo se mide en función del número de nodos generados durantela búsqueda. La memoria se estima como el máximo número denodos expandidos en un momento dado de la ejecución del algoritmo.
Hugo Franco, PhD Solución a problemas de búsqueda
Estructura de la solución a problemas de búsquedaDiseño y evaluación de la estrategia de solución
Costo del proceso de búsqueda
Dado lo anterior, se requiere estimar la complejidad en función de variables dela representación del problema, como:
El factor de ramificación (b, número máximo de transiciones desde unestado). Puede dar lugar a la “explosión combinatoria”.
La profundidad de la solución más próxima al estado inicial (d).
La longitud de la ruta más larga dentro del espacio de estados (m,máximo número de transiciones entre dos estados).
La efectividad del método empleado se puede reportar, entonces, comoCosto de búsqueda: calculado a partir de la complejidad en tiempoy en memoria del algoritmo.El costo de la solución: en función del costo asociado a la ruta delestado inicial al estado solución.El costo total: estimado con base en el costo de búsqueda y elcosto de la solución obtenida.
Hugo Franco, PhD Solución a problemas de búsqueda
Top Related