Sobre Traversals...

Definición formal de Traversals sobre Esquemas de Grafos:

Sea \(S(S_V,S_E)\) un grafo dirigido que llamaremos Esquema, a sus vértices les llamaremos tipos, y a sus aristas, relaciones. Un grafo dirigido \(G(V,E)\) (con conjunto de nodos \(V\) y conjunto de aristas \(E\)), decimos que se ajusta al esquema \(S\) si existen aplicaciones \(tipo_V: V \rightarrow S_V\) (resp. \(tipo_E:E\rightarrow S_E\)) verificando que para toda arista, \(e\), que conecta los nodos \(v_1\) con \(v_2\) en \(G\), se tiene que \(tipo_E(e)\) conecta los nodos \(tipo_V(v_1)\) y \(tipo_V(v_2)\) en \(S\).

Habitualmente, para cada \(t \in S_V\) y \(r\in S_E\) notaremos por:

$$V_t=\{v\in V:\ tipo_V(v)=t\}$$

$$E_t=\{e\in V:\ tipo_E(e)=t\}$$

Un traversal sobre \(S\), \(P\), es un camino en \(S\), es decir, una sucesión \((t_1 r_1 t_2 r_2\dots r_n t_{n+1})\), donde \(t_i\in S_V\) y \(r_i\in S_E\) es una relación que conecta el tipo \(v_i\) con el tipo \(t_{i+1}\)).

Aplicación de un traversal sobre un grafo:

En las condiciones anteriores, podemos definir la aplicación de un traversal sobre un grafo de la siguiente forma:

Si \(P\) es un traversal sobre \(S\) (en las condiciones anteriores) y \(Q\) una subsucesión ordenada, \(t_{i_1}\dots t_{i_k}\), de los tipos que aparecen en \(P\). La acción del par \(<P,Q>\) sobre \(G\), que notaremos \(<P,Q>(G)\) es el hipergrafo ponderado \(H(V_H,E_H)\) dado por:

$$V_H\subseteq V_{t_{i_1}} \cup\dots\cup V_{t_{i_k}}$$

\((a_1,\dots,a_k)\in E_H\) si y sólo si existe un camino en \(G\), \((v_1 e_1 v_2 e_2\dots e_n v_{n+1})\), verificando:

  1. \(\forall 1\leq i\leq n+1\ (tipo_V(v_i)=t_i)\).
  2. \(\forall 1\leq i\leq n\ (tipo_E(e_i)=r_i)\) (se deduce de las condición anterior y de que \(G\) se ajusta a \(S\)).
  3. \(\forall 1\leq j\leq k\ (v_{i_j}=a_j)\).

Normalmente, se tomará como \(V_H\) el conjunto de nodos de \(V\) que intervienen en alguna de las hiperaristas anteriores.

El peso de una hiperarista \(h\in E_H\) se define como:

$$w( h )=\#\{\mbox{caminos que verifican las 3 propiedades anteriores}\}$$

Consultas Traversals sobre Grafos ajustados a Esquemas:

En las condiciones anteriores, podemos definir las operaciones siguientes entre traversals:

Visión general de etiquetas para: 'inteligencia_artificial'

Entradas en este sitio con 'inteligencia_artificial'

  • Fundamentos Matemáticos del Aprendizaje (I)
    El objetivo de la serie de entradas que comienza aquí es el de hacer un repaso por los fundamentos matemáticos que hay detrás del concepto de aprendizaje que nos encontram
  • Seminario (I+A)A ... Nueva Temporada
    Da comienzo la segunda temporada del Seminario (I+A)A ( Inteligencia Artificial  +  Aprendizaje Automático ) del  Dpto. de Ciencias de la Computación e Inteligencia Artifi
  • Bibliografía Comentada de ML
    Título: Metaheuristics: From Design to Implementation Descripción: This book provides a complete background on metaheuristics and shows readers how to design and implement
  • Entrenamiento de Redes Neuronales: mejorando el Gradiente Descendiente
    El procedimiento utilizado para llevar a cabo el proceso de aprendizaje en una red neuronal se denomina  entrenamiento . Aunque hay uno, el del Gradiente Descendiente , qu
  • Calificaciones IAIC 2016-2017
    Estas son las calificaciones finales correspondientes a la 1ª Convocatoria Oficial del curso 2016-2017. Los alumnos sin nota se consideran como "No Presentados". Si hay al
  • Problemas de Satisfacción de Restricciones
    La resolución de Problemas de Satisfacción de Restricciones ( PSR , por sus siglas en español, o CSP por sus siglas en inglés) es un conjunto de técnicas utilizadas para l
  • Self Organizing Maps (SOM) in NetLogo
    In this post we present how to implement Self Organizing Maps (Kohonen, 1992) in NetLogo. Specifically, we will implement two versions, a first introduction example to pro
  • Artificial Neural Networks in NetLogo
    As a way to continue with AI algorithms implemented in  NetLogo , in this post we will see how we can make a simple model to investigate about Artificial Neural Networks (
  • Local Search Algorithms in NetLogo
    In this post we will see implementations of a couple of methods that, starting from initial states, will search in the state space by local moves that take us closer to th
  • A General A* Solver in NetLogo
    Among the different search algorithms that make use of partial information by using heuristics, the most famous is the A* algorithm, and in this post we will present sever
  • A general BFS Solver in NetLogo
    In this post we will provide an agent based model that solves BFS in a generic way (as generic as it can be done with a standard  NetLogo  programming style). For that, we
  • Curso acelerado de Lógica Proposicional
    En esta entrada vamos a intentar dar un curso acelerado (aceleradísimo) acerca de qué es la  Lógica Proposicional  y de qué forma se pueden automatizar algunos de los prob
  • Ejercicios de Algoritmos Genéticos
    Aplica adecuadamente un procedimiento basado en Algoritmos Genéticos para resolver el problema del viajante. Resuelve el problema de las 8 reinas con un Algoritmo Genético
  • Aprendizaje por refuerzo: algoritmo Q Learning
    En entradas anteriores destacábamos dos tipos principales de aprendizaje automático: por una parte, el Aprendizaje Supervisado , y por otra el Aprendizaje no Supervisado .
  • Minimax: Juegos con adversario
    En entradas anteriores hemos visto estrategias de búsqueda para encontrar soluciones a problemas que se pueden expresar por medio de un espacio de búsqueda con estructura
  • Métodos combinados de aprendizaje
    En el campo del aprendizaje automático, los métodos combinados ( métodos de ensemble ) utilizan múltiples algoritmos de aprendizaje para obtener un rendimiento predictivo
  • Aprendizaje Inductivo: Árboles de Decisión
    Entre los diversos tipos de aprendizaje que podemos diferenciar, destaca el  aprendizaje inductivo , que se basa en el descubrimiento de patrones a partir de ejemplos. Ent
  • Sistemas Basados en Reglas
    Hay muchos casos en los que podemos resolver situaciones complejas haciendo uso de reglas deterministas, hasta el punto de su uso consigue sistemas automáticos que se comp
  • Ejercicios Inteligencia Colectiva
    Modifica el modelo de Hormigas que se ha visto en el tema para hacer que el usuario pueda decidir el número de fuentes de comida y se coloquen aleatoriamente en el mundo.
  • Introducción a la Lógica Difusa
    La forma en que la gente piensa es, inherentemente, difusa. La forma en que percibimos el mundo está cambiando continuamente y no siempre se puede definir en términos de s
  • Búsquedas No Informadas
    Los algoritmos de búsqueda ciega o no informada no dependen de información propia del problema a la hora de resolverlo. Por lo que son algoritmos generales y se pueden apl
  • El modelado de problemas
    En numerosas ciencias se hace necesario el estudio y análisis de fenómenos del mundo real, y por ello se hace necesaria la aplicación del método científico a este estudio.
  • Análisis Formal de Conceptos
    El análisis formal de conceptos proporciona una metodología para derivar una jerarquía de conceptos (como una ontología) a partir de una colección de objetos y las propied
  • Clasificación Supervisada y No Supervisada
    Los sistemas de clasificación supervisados son aquellos en los que, a partir de un conjunto de ejemplos clasificados ( conjunto de entrenamiento ), intentamos asignar una
  • Mapas Auto-Organizados
    Los  Self Organizing Maps  ( Mapas Auto-Organizados ), o  SOM , fueron inventados en 1982 por Teuvo Kohonen, profesor de la Academia de Finlandia, y proporcionan una forma
  • Introducción al Aprendizaje Automático
    Grosso modo, el  Aprendizaje Automático  (AA, o  Machine Learning,  por su nombre en inglés) es la rama de la Inteligencia Artificial que tiene como objetivo desarrollar t
  • Optimización en el espacio de parámetros de un modelo
    Uno de los problemas más habituales cuando se construye un modelo para simular un proceso es que, tras haber definido un buen número de parámetros para darle más flexibili
  • Redes Neuronales: una visión superficial
    Una Red Neuronal Artificial ( RNA ) es un modelo matemático inspirado en el comportamiento biológico de las neuronas y en cómo se organizan formando la estructura del cere
  • Algoritmos de hormigas y el problema del viajante
    Los Algoritmos de Hormigas son  una metodología inspirada en el  comportamiento colectivo  de las hormigas en su búsqueda de alimentos. Se debe recordar que las hormigas s
  • PSO: Optimización por enjambres de partículas
    La  Optimización por Enjambres de Partículas  (conocida como  PSO , por sus siglas en inglés,  Particle swarm optimization ) es una técnica de optimización/búsqueda en el
  • Sistemas Colectivos. Inteligencia Colectiva
    En esta entrada se describen fenómenos que sólo aparecen en sistemas compuestos por dos o más individuos . En particular, estamos interesados en los fenómenos colectivos q
  • Autómatas Celulares
    Los autómatas celulares (AC) surgen en la década de 1940 con  John Von Neumann , que intentaba modelar una maquina que fuera capaz de autoreplicarse, llegando así a un mod
  • Algoritmos Genéticos y Computación Evolutiva
    Los primeros ejemplos de lo que hoy podríamos llamar algoritmos genéticos aparecieron a finales de los 50 y principios de los 60, programados en computadoras por biólogos
  • Sistemas Complejos, Sistemas Dinámicos y Redes Complejas
    Un  sistema   es un conjunto de elementos o partes que interaccionan entre sí a fin de alcanzar un objetivo concreto.  En consecuencia, para que el comportamiento de un si
  • Ejercicios de búsquedas locales
    Escribe modelos de NetLogo que sean capaces de aplicar adecuadamente los algoritmos de búsqueda local vistos en el tema. Aplica adecuadamente un procedimiento basado en Al
  • Búsquedas Informadas
    Es evidente que los  algoritmos de búsqueda ciega  (o  no informada ) serán incapaces de encontrar soluciones en problemas en los que el tamaño del espacio de búsqueda es
  • Ejercicios de Búsqueda Informada
    Realiza los mismos ejercicios que se propusieron para búsquedas ciegas pero aplicando el algoritmo A* visto en clase. Intenta utilizar diferentes funciones de heurística p
  • Ejercicios de Lógica de Primer Orden
    1.- Accede desde aquí a los ejercicios que se proponen en el curso de  Lógica Informática del grado de Tecnologías Informáticas  de la Universidad de Sevilla. 2.– Escribir
  • Ejercicios de Lógica Proposicional
    Recordad que podéis usar la página Gateway to Logic para calcular las formas normales conjuntivas de las fórmulas que vayáis usando. Ejercicios de implementación 1.- Imple
  • Sistemas Multiagente y Simulación
    Pretendemos analizar aquí la intersección entre dos campos de investigación: (1) Los Sistemas Multi-Agente (MAS) y (2) la simulación por ordenador. Por un lado, los MAS se
  • Sobre la Inteligencia Artificial...
    El campo de la Inteligencia Artificial (IA) clásica aparece en los años 50 como resultado de la comprensión del cerebro por medio de la neurociencia, las nuevas teorías ma
  • Teoría Algorítmica de la Información y el juego del GO
    Un estudio en el que se mezclan el juego del Go , la Teoría Algorítmica de la Información y los algoritmos de Compresión de Imágenes para comparar la complejidad de las pa
  • Mapas semánticos: clasificación y representación
    El problema de la clasificación de objetos es, a grandes rasgos, uno de los problemas centrales de la investigación y donde, quizás de forma más clara, podemos observar la
  • Clustering por K-medias
     El  algoritmo de las K-medias  (presentado por MacQueen en 1967) es uno de los algoritmos de aprendizaje no supervisado más simples para resolver el problema de la  clust
  • Algoritmo A*
    El algoritmo de búsqueda A* se clasifica dentro de estos algoritmos de búsqueda informada. Fue presentado por primera vez en 1968 por Peter E. Hart, Nils J. Nilsson y Bert
  • Sobre Traversals...
    Topics Navigator  is a prototype model to experiment with some uses of graphs and hypergraphs for storing, recovering and analyzing connected information. Topics Navigator
  • Self Organizing Maps
    Los Self Organizing Feature Maps (Mapas de Características Auto-organizativos), o SOM, fueron inventados por Teuvo Kohonen, profesor de la Academia de Finlandia, y proporc
  • Algoritmo ID3
    Los algoritmos de árboles de decisión construyen modelos de regresión o clasificación en forma de estructura de árbol. Habitualmente, dividen el conjunto de datos en conju
  • Ejercicios de Búsqueda no Informada
    Muchos de los ejercicios que se plantean a continuación se pueden (y deben) resolver por diversos procedimientos de búsqueda, por lo que se propone que, a medida que se va
  • Sobre los espacios de estado y las búsquedas...
    Sin lugar a dudas, una de las principales características de la inteligencia es su capacidad para resolver problemas. Si consideramos una inteligencia como la humana, adem
  • Ejercicios NetLogo II
    Para comprobar que la realización de los siguientes ejericios es correcta se debe tener algún grafo creado en NetLogo, por ello se recomienda hacer todos en el mismo model
  • Ejercicios NetLogo I
    1.- Propagación de fuego por un tereno : En este modelo haremos uso únicamente de los patches. La idea es analizar cómo influye la densidad de madera seca en el terreno pa

Etiquetas relacionadas

algoritmos, netlogo