Buenos días, así que aquí está mi problema. Y lo siento de antemano si mi inglés no es perfecto. De todos modos, tengo una gran cantidad de relación entre los números formados así:

$relation1 = [1, 2];
$relation2 = [2, 3];
$relation3 = [4, 5];
$relation4 = [6, 7];
$relation5 = [7, 2];

Cada matriz representa una relación entre los 2 números. Lo que necesito hacer es fusionar las relaciones para obtener un resultado como:

$result1 = [1, 2, 3, 6, 7];
$result1 = [4, 5];

Ya desarrollé un algoritmo en PHP que hace exactamente eso, el problema es que para un total de más de 50000 relaciones, el programa tarda mucho tiempo en ejecutarse. Cuando termine de crear relaciones directas, que no requieren mucho tiempo:

$temporary_result1 = [1, 2, 3];
$temporary_result2 = [4, 5];
$temporary_result3 = [6, 7, 2];

Luego necesito fusionar los grupos 1 y 3, pero con alrededor de 20 000 grupos creados previamente, el proceso lleva mucho tiempo, porque necesito iterar 20 000 * 20 000 veces (400 000 000) que ya lleva alrededor de 30 minutos. Como se espera que el número de relaciones crezca en el tiempo extra, me preocupa que el tiempo de ejecución crezca exponencialmente ya que necesito ejecutar el programa todos los días.

Me preguntaba si existía un algoritmo existente que haga esto, a la vez que sea más eficiente, en cualquier lenguaje de programación que pueda intentar y recodificar en PHP.

1
Titouan Pautier 13 feb. 2020 a las 13:59

2 respuestas

La mejor respuesta

Puede ver estas relaciones como paquetes de Composer. Cada paquete tiene su propia dependencia.

Como por ejemplo,

$relation1 = [1, 2];
$relation2 = [2, 3];
  • En el ejemplo anterior, puede decir que el paquete 1 depende del paquete 2 y el paquete 2 depende del paquete 3.

  • Del mismo modo, tenemos que encontrar todos los componentes conectados. La relación entre 2 paquetes no necesariamente tiene que ser reflexiva, lo que significa que el paquete A depende del paquete B no necesariamente significa que el paquete B depende del paquete { {X3}}.

  • Pero para el alcance de este problema, podemos hacer que la relación sea reflexiva para obtener los componentes conectados a través de {{ X0}}. Si lo desea, puede adaptarse a una idea no reflexiva utilizando union find by path compression para fusionar valores con padres singulares, pero en mi respuesta, me quedaría con DFS.

Su entrada:

$relation1 = [1, 2];
$relation2 = [2, 3];
$relation3 = [4, 5];
$relation4 = [6, 7];
$relation5 = [7, 2];

Para la entrada anterior, la lista de adyacencia se vería así:

1 => 2
2 => 1,3,7
3 => 2
4 => 5
5 => 4
6 => 7
7 => 6,2

Fragmento:

function getConnectedComponents($relations,$total_nodes){
    $result = [];
    $nodes = [];
    $visited = [];

    for($i=1;$i<=$total_nodes;++$i){
        $nodes[$i] = [];
        $visited[$i] = false;
    }

    foreach($relations as $relation){
        $nodes[$relation[0]][] = $relation[1];
        $nodes[$relation[1]][] = $relation[0];
    }

    for($i=1;$i<=$total_nodes;++$i){
        if(!$visited[$i]){
            $temp = [];
            dfs($nodes,$i,$visited,$temp);
            $result[] = $temp;
        }
    }

    return $result;
}

function dfs($nodes,$node,&$visited,&$temp){
    if($visited[$node]) return;
    $visited[$node] = true;
    $temp[] = $node;
    foreach($nodes[$node] as $child_node){
        dfs($nodes,$child_node,$visited,$temp);
    }
}

Demostración: https://3v4l.org/JWAF6

En el algoritmo anterior, construimos la lista de adyacencia y hacemos una búsqueda profunda en primer lugar en cada nodo. Marcamos los nodos como visitados en el camino para asegurarnos de que no estamos visitando algo que ya procesamos.

1
vivek_23 13 feb. 2020 a las 12:52

Puede ver este problema como un problema de gráficos generales.
Sus relaciones son aristas y hay E de ellas.
Sus enteros son vértices, hay V de ellos.

Ahora necesita encontrar los componentes del gráfico, este es un problema bien conocido y hay muchas soluciones para ello.

Se describe una solución aquí, comienza de forma aleatoria nodo y haga un DFS hasta que encuentre todos los nodos en su componente. Que pasar a otro nodo no visitado hasta encontrar todos los nodos en el gráfico.
Presenta un código en muchos idiomas, pero no PHP, aquí hay una implementación php de DFS que puedes usar.

La complejidad temporal de esta solución es O(E + V) si se implementa correctamente, por lo que resolverá el problema del tiempo de ejecución.

La mejor de las suertes

0
Yonlif 13 feb. 2020 a las 11:56