- Es una representación gráfica del conocimiento en la que existe una jerarquía de Nodos.
- Es un conjunto de Nodos y Arcos.
Donde un objeto puede ser representado por:
- Personas.
- Animales.
- Eventos.
- Acciones.
- Conceptos.
- Atributos o características que identifican a un objeto.
- Colección de atributos que describen a una clase o a una entidad miembro de esa clase del mundo real. Los Frames son usados para representar de manera estructurada el estereotipo de una situación.
- Son una estructura del conocimiento que describen un objeto específico y contiene múltiples ranuras o slots, las cuales contienen hechos, características o especificaciones acerca del objeto.
Grafos de Búsqueda
Muchos problemas pueden ser planteados como problemas de búsqueda en grafo, en un problema de búsqueda interesa encontrar como es posible llegar desde un Nodo fuente s, hasta un Nodo destino que cumpla con una propiedad P.
Existen varios métodos de búsqueda:
Búsqueda en Anchura (BFS): Es un algoritmo para recorrer o buscar elementos en un grafo, Se comienza en cualquier vértice y en cada paso se avanza a un nuevo vértice adyacente siempre que se pueda. Cuando todos los adyacentes a X hayan sido visitados, se retrocede al vértice desde el que se alcanzó X y se prosigue. Así se consigue visitar todos los vértices de la componente conexa en que se encuentre el vértice inicial.
Esta técnica se utiliza cuando necesitamos encontrar respuesta a un problema sobre un grafo sin condiciones de optimización.
Búsqueda en Profundidad (DFS): A diferencia con la BFS ahora se visitan todos los vecinos de un vértice antes de pasar al siguiente. Por tanto no hay necesidad de retroceder. Una vez etiquetados todos los vecinos de un vértice X, se continúa con el primer vértice alcanzado después de X en la búsqueda.
Esta técnica se utiliza para resolver problemas en los que se pide hallar una solución óptima entre varias.
No hay comentarios:
Publicar un comentario