LISTAS RELACIONADAS CON LAS MATEMÁTICAS - ALGORITMOS

El algoritmo MaxCliqueDyn es un algoritmo para encontrar una camarilla máxima en un gráfico no dirigido. Se basa en un algoritmo básico (algoritmo MaxClique) que encuentra una camarilla máxima de tamaño acotado. El límite se encuentra utilizando un algoritmo de coloración mejorado. MaxCliqueDyn extiende el algoritmo MaxClique para incluir límites dinámicamente variables. Este algoritmo fue diseñado por Janez Konc y la descripción se publicó en 2007. En comparación con los algoritmos anteriores descritos en el artículo publicado ^[1], el algoritmo MaxCliqueDyn se mejora mediante un algoritmo de coloración aproximado mejorado ( algoritmo ColorSort) y aplicando límites superiores más estrictos y más costosos computacionalmente en una fracción del espacio de búsqueda. Ambas mejoras reducen el tiempo para encontrar la máxima camarilla. Además de reducir el tiempo, el algoritmo de coloración mejorado también reduce el número de pasos necesarios para encontrar una camarilla máxima.

Algoritmo MaxClique [ editar ]

El algoritmo MaxClique ^[2] es el algoritmo básico del algoritmo MaxCliqueDyn. El pseudocódigo del algoritmo es:

   Procedimiento MaxClique (R, C)
       Q = Ø; Q max = Ø;
       mientras que R ≠ Ø do
           elija un vértice p con un color máximo C (p) del conjunto R;
           R: = R \ {p};
           si | Q | + C (p)> | Q max | entonces
               Q: = Q ⋃ {p};
               si R ⋂ Γ (p) ≠ Ø entonces
                   obtener una coloración de vértice C 'de G (R ⋂ Γ (p));
                   MaxClique (R ⋂ Γ (p), C ');
               más si | Q |> | Q max | entonces Q max : = Q;
                   Q: = Q \ {p};
           de lo contrario volver
       terminar mientras

donde Q es un conjunto de vértices de la camarilla en crecimiento actual, Q _max es un conjunto de vértices de la camarilla más grande que se encuentra actualmente, R es un conjunto de vértices candidatos y C su conjunto correspondiente de clases de color. El algoritmo MaxClique busca recursivamente para la máxima camarilla mediante la adición y la eliminación de los vértices a y desde  Q .

Algoritmo de coloración (ColorSort) [ editar ]

En el algoritmo MaxClique el algoritmo del colorante aproximado ^[2] se utiliza para obtener un conjunto de clases de color  C . El algoritmo ColorSort es un algoritmo mejorado del algoritmo de coloración aproximado. En el algoritmo de coloración aproximado, los vértices se colorean uno por uno en el mismo orden en que aparecen en un conjunto de vértices candidatos R, de modo que si el próximo vértice p no es adyacente a todos los vértices en alguna clase de color, se agrega a esta clase y si p es adyacente a al menos un vértice en cada una de las clases de color existentes, se coloca en una nueva clase de color.

El algoritmo MaxClique devuelve vértices R ordenados por sus colores. Al observar el algoritmo MaxClique, queda claro que los vértices v  ∈  R con los colores C ( v ) <| Q _max | - | Q | + 1 no se añadirá a la camarilla actual  Q . Por lo tanto, ordenar esos vértices por color no sirve para el algoritmo MaxClique.

El color mejorado con el algoritmo ColorSort toma en consideración la observación anterior. Cada vértice se asigna a una clase de color C _k . Si k  <| Q _max | - | Q | + 1 el vértice se mueve a R (detrás del último vértice en  R ). Si k  ≥ | Q _max | - | Q | + 1 que el vértice se queda en la clase de color C _k y no se copia en el conjunto  R . Al final, todos los vértices en las clases de color C _k donde k  ≥ | Q _max | - | QEl | + 1 se agregan al reverso del conjunto R a medida que aparecen en cada clase de color C _k y en orden creciente con respecto al índice  k . En el algoritmo de clasificación de color, solo a estos vértices se les asignan colores C ( v ) =  k .

Algoritmo ColorSort ^[1]

   Procedimiento ColorSort (R, C)
       max_no: = 1;
       k min  : = | Q max | - | Q | + 1;
       si k min ≤ 0, entonces k min  : = 1;
       j: = 0;
       C 1  : = Ø; C 2  : = Ø;
       para i: = 0 a | R | - 1 do
           p: = R [i]; {el i-ésimo vértice en R}
           k: = 1;
           mientras que C k ⋂ Γ (p) ≠ Ø do
               k: = k + 1;
           si k> max_no entonces
               max_no: = k;
               C max_no + 1  : = Ø;
           terminara si
           C k  : = C k ⋃ {p};
           si k min entonces
               R [j]: = R [i];
               j: = j + 1;
           terminara si
       fin de
       C [j − 1]: = 0;
       para k: = k min a max_no do
           para i: = 1 a | C k | hacer
               R [j]: = Ck [i];
               C [j]: = k;
               j: = j + 1;
           fin de
       fin de

Ejemplo

El gráfico anterior se puede describir como un conjunto candidato de vértices R  = {7 ⁽⁵⁾ , 1 ⁽⁴⁾ , 4 ⁽⁴⁾ , 2 ⁽³⁾ , 3 ⁽³⁾ , 6 ⁽³⁾ , 5 ⁽²⁾ , 8 ⁽²⁾ }. El conjunto de vértices R ahora se puede usar como entrada para el algoritmo de coloración aproximado y el algoritmo ColorSort. Usando cualquiera de los dos algoritmos, se construye una tabla a continuación.

k	C k
1	7 (5) , 5 (2)
2	1 (4) , 6 (3) , 8 (2)
3	4 (4) , 2 (3) , 3 (3)

El algoritmo de coloración aproximado devuelve un conjunto de vértices R = {7 ⁽⁵⁾ , 5 ⁽²⁾ , 1 ⁽⁴⁾ , 6 ⁽³⁾ , 8 ⁽²⁾ , 4 ⁽⁴⁾ , 2 ⁽³⁾ , 3 ⁽³⁾ } y su conjunto correspondiente de clases de color C  = {1,1,2,2,2,3,3,3}. El algoritmo ColorSort devuelve un conjunto de vértices R  = {7 ⁽⁵⁾ , 1 ⁽⁴⁾ , 6 ⁽³⁾ , 5 ⁽²⁾ , 8 ⁽²⁾ , 4 ⁽⁴⁾ , 2 ⁽³⁾ , 3 ⁽³⁾ } y su conjunto correspondiente de clases de color C = {-, -, -, -, -, 3,3,3}, donde - representa una clase de color desconocida con  k  <3 .="" font="">

Algoritmo MaxCliqueDyn [ editar ]

El algoritmo MaxCliqueDyn está en el algoritmo MaxClique básico que utiliza el algoritmo ColorSort en lugar del algoritmo de coloración aproximado para determinar las clases de color. En cada paso del algoritmo MaxClique, el algoritmo también recalcula los grados de vértices en R con respecto al vértice en el que se encuentra actualmente el algoritmo. Estos vértices se ordenan por orden decreciente con respecto a sus grados en el gráfico G (R). Luego, el algoritmo ColorSort considera los vértices en R ordenados por sus grados en el gráfico inducido G (R) en lugar de en G. Al hacerlo, el número de pasos necesarios para encontrar la camarilla máxima se reduce al mínimo. Aun así, el tiempo de ejecución general del algoritmo MaxClique no mejora, porque el gasto computacional O (| R | ² ) de la determinación de los grados y la clasificación de los vértices en R permanece igual.

Algoritmo MaxCliqueDyn ^[1]

   Procedimiento MaxCliqueDyn (R, C, nivel)
       S [nivel]: = S [nivel] + S [nivel − 1] - S antiguo [nivel];
       S antiguo [nivel]: = S [nivel − 1];
       mientras que R ≠ Ø do
           elija un vértice p con C (p) máximo (último vértice) de R;
           R: = R \ {p};
           si | Q | + C [índice de p en R]> | Q max | entonces
               Q: = Q ⋃ {p};
               si R ⋂ Γ (p) ≠ Ø entonces
                   si S [nivel] / TODOS LOS PASOS límite entonces
                       calcular los grados de vértices en G (R ⋂ Γ (p));
                       ordenar vértices en R ⋂ Γ (p) en orden descendente
                       con respecto a sus grados;
                   terminara si
                   ColorSort (R ⋂ Γ (p), C ')
                   S [nivel]: = S [nivel] + 1;
                   TODOS LOS PASOS: = TODOS LOS PASOS + 1;
                   MaxCliqueDyn (R ⋂ Γ (p), C ', nivel + 1);
               más si | Q | > | Q max | entonces Q max  : = Q;
               Q: = Q \ {p};
           de lo contrario volver
       terminar mientras

El _{límite del} valor T puede determinarse experimentando en gráficos aleatorios. En el artículo original se determinó que el algoritmo funciona mejor para el _límite T  = 0.025.

En la teoría de gráficos , los componentes fuertemente conectados de un gráfico dirigido se pueden encontrar usando un algoritmo que utiliza la búsqueda de profundidad primero en combinación con dos pilas , una para realizar un seguimiento de los vértices en el componente actual y la segunda para realizar un seguimiento de la corriente ruta de búsqueda ^[1] Las versiones de este algoritmo han sido propuestas por Purdom (1970) , Munro (1971) , Dijkstra (1976) , Cheriyan y Mehlhorn (1996) y Gabow (2000) ; De estos, la versión de Dijkstra fue la primera en alcanzar el tiempo lineal . 

Descripción [ editar ]

El algoritmo realiza una búsqueda en profundidad del gráfico G dado , manteniendo como lo hace dos pilas S y P (además de la pila normal de llamadas para una función recursiva). La pila S contiene todos los vértices que aún no se han asignado a un componente fuertemente conectado, en el orden en que la búsqueda de profundidad llega a los vértices. La pila P contiene vértices que aún no se ha determinado que pertenecen a diferentes componentes fuertemente conectados entre sí. También usa un contador C del número de vértices alcanzados hasta ahora, que usa para calcular los números de preorden de los vértices.

Cuando la búsqueda de profundidad primero alcanza un vértice v , el algoritmo realiza los siguientes pasos:

1. Establecer el número de orden previo V a C , y el incremento C .
2. Empuje v en S y también sobre P .
3. Para cada arista desde v hasta un vértice vecino w :
   • Si aún no se ha asignado el número de preorden de w , busque recursivamente w ;
   • De lo contrario, si w aún no se ha asignado a un componente fuertemente conectado:
     • Haga estallar repetidamente vértices desde P hasta que el elemento superior de P tenga un número de preorden menor o igual al número de preorden de w .
4. Si v es el elemento superior de P :
   • Haga estallar los vértices desde S hasta que v se haya reventado y asigne los vértices reventados a un nuevo componente.
   • Pop v de P .

El algoritmo general consiste en un bucle a través de los vértices del gráfico, llamando a esta búsqueda recursiva en cada vértice que aún no tiene asignado un número de pedido.

Algoritmos relacionados [ editar ]

Al igual que este algoritmo, el algoritmo de componentes fuertemente conectados de Tarjan también utiliza primero la búsqueda en profundidad junto con una pila para realizar un seguimiento de los vértices que aún no se han asignado a un componente, y mueve estos vértices a un nuevo componente cuando termina de expandir el vértice final de su componente. Sin embargo, en lugar de la pila P , el algoritmo de Tarjan utiliza una matriz indexada de vértices de números de preorden, asignados en el orden en que los vértices se visitan por primera vez en la búsqueda de profundidad . La matriz de preorden se utiliza para realizar un seguimiento de cuándo formar un nuevo componente.

el algoritmo de Kosaraju (también conocido como algoritmo Kosaraju-Sharir ) es un algoritmo de tiempo lineal para encontrar los componentes fuertemente conectados de un gráfico dirigido . Aho , Hopcroft y Ullman lo atribuyen a S. Rao Kosaraju y Micha Sharir . Kosaraju lo sugirió en 1978 pero no lo publicó, mientras que Sharir lo descubrió independientemente y lo publicó en 1981. Utiliza el hecho de que el gráfico de transposición (el mismo gráfico con la dirección de cada borde invertido) tiene exactamente los mismos componentes fuertemente conectados que el gráfico original.

El algoritmo [ editar ]

Las operaciones gráficas primitivas que utiliza el algoritmo son enumerar los vértices del gráfico, almacenar datos por vértice (si no está en la estructura de datos del gráfico en sí, luego en alguna tabla que puede usar vértices como índices), enumerar los vecinos externos. de un vértice (bordes transversales en la dirección hacia adelante), y enumerar los vecinos de un vértice (bordes transversales en la dirección hacia atrás); sin embargo, lo último se puede hacer sin, al precio de construir una representación del gráfico de transposición durante la fase de avance transversal. La única estructura de datos adicional que necesita el algoritmo es una lista ordenada L de vértices de gráfico, que crecerá para contener cada vértice una vez.

Si los componentes fuertes deben representarse designando un vértice raíz separado para cada componente y asignando a cada vértice el vértice raíz de su componente, entonces el algoritmo de Kosaraju puede establecerse de la siguiente manera.

1. Para cada vértice u de la gráfica, marcar u como no visitado. Deje L estar vacío.
2. Para cada vértice u del gráfico, visite Visit ( u ), donde Visit ( u ) es la subrutina recursiva:

   Si u es no visitado a continuación:

   1. Marca u como visitado.
   2. Para cada vecino externo v de u , visite Visit ( v ).
   3. Anteponer u a l .

   De lo contrario no hagas nada.

3. Para cada elemento u de L en orden, haga Assign ( u , u ) donde Assign ( u , root ) es la subrutina recursiva:

   Si u no se ha asignado a un componente a continuación:

   1. Asigne u como perteneciente al componente cuya raíz es root .
   2. Para cada v vecino de u , asigne ( v , root ).

   De lo contrario no hagas nada.

Las variaciones triviales son, en cambio, asignar un número de componente a cada vértice, o construir listas por componente de los vértices que le pertenecen. La indicación no visitada / visitada puede compartir la ubicación de almacenamiento con la asignación final de raíz para un vértice.

El punto clave del algoritmo es que durante el primer recorrido (hacia adelante) de los bordes del gráfico, los vértices se anteponen a la lista L en orden posterior en relación con el árbol de búsqueda que se está explorando. Esto significa que no importa si un vértice v se visitó por primera vez porque apareció en la enumeración de todos los vértices o porque fue el vecino externo de otro vértice u el que se visitó; De cualquier manera v se antepondrá a L antes de u es, así que si hay un camino a seguir a partir de u a v a continuación, u aparecerá antes de v en la lista final L (a menosu y v pertenecen al mismo componente fuerte, en cuyo caso su orden relativo en L es arbitrario). Como se indicó anteriormente, el algoritmo de simplicidad emplea la búsqueda por profundidad , pero también podría usar la búsqueda por amplitud siempre que se conserve la propiedad de orden posterior.

El algoritmo puede entenderse como la identificación del componente fuerte de un vértice u como el conjunto de vértices a los que se puede acceder desde u tanto hacia atrás como hacia adelante. Escritura$${\ displaystyle F (u)} para el conjunto de vértices alcanzables desde $${\ displaystyle u} por avance transversal, $${\ displaystyle B (u)} para el conjunto de vértices alcanzables desde $${\ displaystyle u} por recorrido hacia atrás, y $${\ displaystyle P (u)} para el conjunto de vértices que aparecen estrictamente antes $${\ displaystyle u}en la lista L después de la fase 2 del algoritmo, el componente fuerte que contiene un vértice$${\ displaystyle u} designado como raíz es

$${\ displaystyle B (u) \ cap F (u) = B (u) \ setminus (B (u) \ setminus F (u)) = B (u) \ setminus P (u)}.

La intersección de conjuntos es computacionalmente costosa, pero es lógicamente equivalente a una diferencia de conjunto doble , y dado que$${\ displaystyle B (u) \ setminus F (u) \ subseteq P (u)} se vuelve suficiente para probar si un elemento recién encontrado de $${\ displaystyle B (u)} ya ha sido asignado a un componente o no.

Complejidad [ editar ]

Siempre que el gráfico se describa usando una lista de adyacencia , el algoritmo de Kosaraju realiza dos recorridos completos del gráfico y, por lo tanto, se ejecuta en tiempo linear (V + E) (lineal), que es asintóticamente óptimo porque hay un límite inferior coincidente (cualquier algoritmo debe examinar todos los vértices y aristas). Es el algoritmo eficiente conceptualmente más simple, pero no es tan eficiente en la práctica como el algoritmo de componentes fuertemente conectados de Tarjan y el algoritmo de componentes fuertes basado en la ruta , que realizan solo un recorrido del gráfico.

Si el gráfico se representa como una matriz de adyacencia , el algoritmo requiere un tiempo Ο (V ² ) .