LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

El algoritmo Christofides es un algoritmo para encontrar soluciones aproximadas al problema del vendedor ambulante , en los casos en que las distancias forman un espacio métrico (son simétricas y obedecen a la desigualdad del triángulo ). ^[1] Es un algoritmo de aproximación que garantiza que sus soluciones estarán dentro de un factor de 3/2 de la longitud óptima de la solución, y lleva el nombre de Nicos Christofides , quien lo publicó en 1976. ^[2] A partir de 2019 , esto es la mejor relación de aproximación esto se ha demostrado para el problema del vendedor ambulante en espacios métricos generales, aunque se conocen mejores aproximaciones para algunos casos especiales.

Algoritmo [ editar ]

Sea G = ( V , w ) una instancia del problema del vendedor ambulante. Es decir, G es un grafo completo en el conjunto V de vértices, y la función w asigna un peso real no negativo a cada borde de G . De acuerdo con la desigualdad del triángulo, por cada tres vértices u , v y x , debería ser el caso de que w ( uv ) + w ( vx ) ≥ w ( ux ) .

Entonces el algoritmo se puede describir en pseudocódigo de la siguiente manera. ^[1]

1. Crear un árbol de expansión mínima T de G .
2. Deje O el conjunto de vértices con impar grado en T . Por el lema de apretón de manos , O tiene un número par de vértices.
3. Encontrar un mínimo peso perfecta coincidencia de M en el subgrafo inducido dado por los vértices de O .
4. Combina los bordes de M y T para formar un H multigráfico conectado en el que cada vértice tiene un grado uniforme.
5. Formar un circuito euleriano en H .
6. Convierta el circuito encontrado en el paso anterior en un circuito hamiltoniano omitiendo los vértices repetidos ( atajos ).

Relación de aproximación [ editar ]

El costo de la solución producida por el algoritmo está dentro de 3/2 del óptimo. Para probar esto, deje que C sea ​​el recorrido óptimo del vendedor ambulante. La eliminación de un borde de C produce un árbol de expansión, que debe tener un peso de al menos el del árbol de expansión mínimo, lo que implica que w ( T ) ≤ w ( C ) . Luego, numere los vértices de O en orden cíclico alrededor de C , y divida C en dos conjuntos de caminos: aquellos en los que el primer vértice del camino en orden cíclico tiene un número impar y aquellos en los que el primer vértice del camino tiene un número par . Cada conjunto de caminos corresponde a una combinación perfecta de Oque coincide con los dos puntos finales de cada ruta, y el peso de esta coincidencia es como máximo igual al peso de las rutas. Dado que estos dos conjuntos de trayectorias de partición de los bordes de C , uno de los dos conjuntos tiene a lo sumo la mitad del peso de C , y gracias a la desigualdad triangular su correspondiente juego tiene un peso que es también a lo sumo la mitad del peso de C . La combinación perfecta de peso mínimo no puede tener un peso mayor, por lo que w ( M ) ≤ w ( C ) / 2 . Agregar los pesos de T y M da el peso del recorrido de Euler, como máximo 3 w ( C ) / 2. Gracias a la desigualdad del triángulo, el acceso directo no aumenta el peso, por lo que el peso de la salida también es como máximo 3 w ( C ) / 2 . ^[1]

Límites inferiores [ editar ]

Existen entradas al problema del vendedor ambulante que hacen que el algoritmo Christofides encuentre una solución cuya relación de aproximación sea arbitrariamente cercana a 3/2. Una de estas clases de entradas está formada por una ruta de n vértices, con los bordes de la ruta teniendo un peso 1 , junto con un conjunto de bordes que conectan vértices separados dos pasos en la ruta con un peso 1 + ε para un número ε elegido cerca de cero pero positivo. Todos los bordes restantes del gráfico completo tienen distancias dadas por los caminos más cortos en este subgrafo. Entonces el árbol de expansión mínimo estará dado por la ruta, de longitud n - 1, y los únicos dos vértices impares serán los puntos finales de la ruta, cuya coincidencia perfecta consiste en un solo borde con un peso de aproximadamente n / 2 . La unión del árbol y la coincidencia es un ciclo, sin atajos posibles, y con un peso aproximado de 3 n / 2 . Sin embargo, la solución óptima utiliza los bordes de peso 1 + ε junto con dos bordes de peso- 1 incidentes a los puntos finales de la ruta, y tiene un peso total (1 + ε ) ( n - 2) + 2 , cerca de n para pequeños valores de ε . Por lo tanto, obtenemos una relación de aproximación de 3/2. ^[3]

Ejemplo [ editar ]

	Dado: gráfico completo cuyos pesos de borde obedecen a la desigualdad del triángulo
	Calcule el árbol de expansión mínimo T
	Calcule el conjunto de vértices O con grado impar en T
	Forme el subgrafo de G usando solo los vértices de O
	Construya una coincidencia perfecta de peso mínimo M en este subgrafo
	Une el árbol coincidente y de expansión T ∪ M para formar un multigrafo euleriano
	Calcular el recorrido de Euler
	Eliminar vértices repetidos, dando la salida del algoritmo

cierre transitivo de una relación binaria R en un conjunto X es la relación más pequeña en X que contiene R y es transitiva .

Por ejemplo, si X es un conjunto de aeropuertos y xRy significa "hay un vuelo directo desde el aeropuerto x al aeropuerto y " (para x e y en X ), entonces el cierre transitivo de R en X es la relación R ⁺ tal que x R ⁺ y significa "que es posible volar desde x a y en uno o más vuelos". Informalmente, el cierre transitivo le brinda el conjunto de todos los lugares a los que puede llegar desde cualquier lugar inicial.

Más formalmente, el cierre transitivo de una relación binaria R en un conjunto X es la relación transitiva R ⁺ en el conjunto X de manera que R ⁺ contiene R y R ⁺ es mínimo Lidl & Pilz (1998 , p. 337). Si la relación binaria en sí misma es transitiva, entonces el cierre transitivo es esa misma relación binaria; de lo contrario, el cierre transitivo es una relación diferente.

Relaciones transitivas y ejemplos [ editar ]

Una relación R en un conjunto X es transitiva si, para todos x , y , z en X , siempre que x R y y y R z entonces x R z . Los ejemplos de relaciones transitivas incluyen la relación de igualdad en cualquier conjunto, la relación "menor o igual" en cualquier conjunto ordenado linealmente y la relación " x nació antes que y " en el conjunto de todas las personas. Simbólicamente, esto se puede denotar como: si x < y e y < z entonces x < z .

Un ejemplo de una relación no transitiva es " se puede llegar a la ciudad x a través de un vuelo directo desde la ciudad y " en el conjunto de todas las ciudades. Simplemente porque hay un vuelo directo de una ciudad a una segunda ciudad, y un vuelo directo de la segunda ciudad a la tercera, no implica que haya un vuelo directo de la primera ciudad a la tercera. El cierre transitivo de esta relación es una relación diferente, a saber, "hay una secuencia de vuelos directos que comienza en la ciudad x y termina en la ciudad y ". Toda relación puede extenderse de manera similar a una relación transitiva.

Un ejemplo de una relación no transitiva con un cierre transitivo menos significativo es " x es el día de la semana después de y ". El cierre transitivo de esta relación es "algún día x viene después de un día y en el calendario", lo cual es trivialmente cierto para todos los días de la semana x e y (y por lo tanto equivalente al cuadrado cartesiano , que es " x e y son los dos días de la semana ").

Existencia y descripción [ editar ]

Para cualquier relación R , el cierre transitivo de R siempre existe. Para ver esto, tenga en cuenta que la intersección de cualquier familia de relaciones transitivas es nuevamente transitiva. Además, existe al menos una relación transitiva que contiene R , a saber, el trivial uno: X × X . El cierre transitivo de R viene dada entonces por la intersección de todas las relaciones transitivos que contienen R .

Para conjuntos finitos, podemos construir el cierre transitivo paso a paso, comenzando desde R y agregando bordes transitivos. Esto da la intuición para una construcción general. Para cualquier conjunto X , podemos demostrar que el cierre transitivo viene dado por la siguiente expresión

$${\ displaystyle R ^ {+} = \ bigcup _ {i \ in \ {1,2,3, \ ldots \}} R ^ {i}.}

dónde $${\ displaystyle R ^ {i}}es la i -ésima potencia de R , definida inductivamente por

$${\ displaystyle R ^ {1} = R}

y para {\ displaystyle i> 0},

$${\ displaystyle R ^ {i + 1} = R \ circ R ^ {i}}

dónde $${\ displaystyle \ circ}denota composición de las relaciones .

Para mostrar que la definición anterior de R ⁺ es la relación menos transitiva que contiene R , mostramos que contiene R , que es transitivo y que es el conjunto más pequeño con ambas características.

• $${\ displaystyle R \ subseteq R ^ {+}}: $${\ displaystyle \ displaystyle R ^ {+}} contiene todos los $${\ displaystyle \ displaystyle R ^ {i}}, en particular $${\ displaystyle \ displaystyle R ^ {+}} contiene $${\ displaystyle \ displaystyle R}.
• $${\ displaystyle \ displaystyle R ^ {+}} es transitivo: cada elemento de $${\ displaystyle \ displaystyle R ^ {+}} está en uno de los $${\ displaystyle \ displaystyle R ^ {i}}, asi que $${\ displaystyle \ displaystyle R ^ {+}} debe ser transitivo por el siguiente razonamiento: si $${\ displaystyle (s_ {1}, s_ {2}) \ en R ^ {j}} y $${\ displaystyle (s_ {2}, s_ {3}) \ en R ^ {k}}, luego de la asociatividad de la composición, $${\ displaystyle (s_ {1}, s_ {3}) \ en R ^ {j + k}} (y así en $${\ displaystyle \ displaystyle R ^ {+}}) debido a la definición de $${\ displaystyle \ displaystyle R ^ {i}}.
• $${\ displaystyle \ displaystyle R ^ {+}} es mínimo: Let $${\ displaystyle \ displaystyle G} ser cualquier relación transitiva que contenga $${\ displaystyle \ displaystyle R}, queremos mostrar que $${\ displaystyle R ^ {+} \ subseteq G}. Es suficiente demostrar que por cada{\ displaystyle i> 0}, $${\ displaystyle R ^ {i} \ subseteq G}. Bueno desde$${\ displaystyle \ displaystyle G} contiene $${\ displaystyle \ displaystyle R}, $${\ displaystyle R ^ {1} \ subseteq G}. Y desde$${\ displaystyle \ displaystyle G} es transitivo, siempre que $${\ displaystyle R ^ {i} \ subseteq G}, $${\ displaystyle R ^ {i + 1} \ subseteq G} de acuerdo con la construcción de $${\ displaystyle R ^ {i}}y lo que significa ser transitivo. Por lo tanto, por inducción,$${\ displaystyle \ displaystyle G} contiene cada $${\ displaystyle R ^ {i}}, y por lo tanto también $${\ displaystyle \ displaystyle R ^ {+}}.

Propiedades [ editar ]

La intersección de dos relaciones transitivas es transitiva.

La unión de dos relaciones transitivas no necesita ser transitiva. Para preservar la transitividad, uno debe tomar el cierre transitivo. Esto ocurre, por ejemplo, al tomar la unión de dos relaciones de equivalencia o dos pedidos anticipados . Para obtener una nueva relación de equivalencia o preordenar, se debe tomar el cierre transitivo (la reflexividad y la simetría, en el caso de las relaciones de equivalencia, son automáticas).

En teoría de grafos [ editar ]

El cierre transitivo construye el gráfico de salida a partir del gráfico de entrada.

En informática , el concepto de cierre transitivo puede considerarse como la construcción de una estructura de datos que hace posible responder preguntas de accesibilidad . Es decir, ¿se puede pasar del nodo a al nodo d en uno o más saltos? Una relación binaria solo le dice que el nodo a está conectado al nodo b , y que el nodo b está conectado al nodo c , etc. Después de que se construye el cierre transitivo, como se muestra en la figura siguiente, en una operación O (1) se puede determinar que el nodo d es accesible desde el nodo a. La estructura de datos generalmente se almacena como una matriz, por lo que si la matriz [1] [4] = 1, entonces el nodo 1 puede alcanzar el nodo 4 a través de uno o más saltos.

El cierre transitivo de la relación de adyacencia de un gráfico acíclico dirigido (DAG) es la relación de accesibilidad del DAG y un orden parcial estricto .

En lógica y complejidad computacional [ editar ]

El cierre transitivo de una relación binaria no puede, en general, expresarse en lógica de primer orden (FO). Esto significa que no se puede escribir una fórmula usando predicado símbolos R y T que será satisfecho en cualquier modelo si y sólo si T es el cierre transitivo de R . En la teoría de modelos finitos , la lógica de primer orden (FO) extendida con un operador de cierre transitivo generalmente se denomina lógica de cierre transitivo y abreviada FO (TC) o simplemente TC. TC es un subtipo de lógica de punto fijo . El hecho de que FO (TC) es estrictamente más expresivo que FO fue descubierto por Ronald Fagin en 1974; el resultado fue redescubierto porAlfred Aho y Jeffrey Ullman en 1979, quienes propusieron utilizar la lógica de punto fijo como lenguaje de consulta de base de datos (Libkin 2004: vii). Con conceptos más recientes de la teoría de modelos finitos, la prueba de que FO (TC) es estrictamente más expresiva que FO se deduce inmediatamente del hecho de que FO (TC) no es Gaifman-local (Libkin 2004: 49).

En la teoría de la complejidad computacional , la clase de complejidad NL corresponde precisamente al conjunto de oraciones lógicas expresables en TC. Esto se debe a que la propiedad de cierre transitivo tiene una estrecha relación con el problema STCON de NL completo para encontrar rutas dirigidas en un gráfico. De manera similar, la clase L es lógica de primer orden con el cierre conmutativo y transitivo. Cuando se agrega el cierre transitivo a la lógica de segundo orden , obtenemos PSPACE .

En los idiomas de consulta de la base de datos [ editar ]

Más información: consultas jerárquicas y recursivas en SQL

Desde la década de 1980, Oracle Database ha implementado una extensión SQL patentada CONNECT BY ... START WITH que permite el cálculo de un cierre transitivo como parte de una consulta declarativa. El estándar SQL 3 (1999) agregó una construcción WITH RECURSIVE más general que también permite el cálculo de cierres transitivos dentro del procesador de consultas; a partir de 2011, este último se implementó en IBM DB2 , Microsoft SQL Server , Oracle y PostgreSQL , aunque no en MySQL (Benedikt y Senellart 2011: 189).

Datalog también implementa cálculos de cierre transitivo (Silberschatz et al. 2010: C.3.6).

Algoritmos [ editar ]

Se pueden encontrar algoritmos eficientes para calcular el cierre transitivo de la relación de adyacencia de un gráfico en Nuutila (1995). Los métodos más rápidos para el peor de los casos, que no son prácticos, reducen el problema a la multiplicación de matrices . El problema también puede resolverse mediante el algoritmo de Floyd-Warshall , o mediante la búsqueda repetida de amplitud o búsqueda de profundidad a partir de cada nodo del gráfico.

Investigaciones más recientes han explorado formas eficientes de calcular el cierre transitivo en sistemas distribuidos basados ​​en el paradigma MapReduce (Afrati et al. 2011).