No puedo decir cuál es el mejor algoritmo absoluto, pero su búsqueda puede acelerarse si tiene la capacidad de cambiar la forma en que almacena su gráfico no dirigido. La forma en que elija hacer esto depende del tamaño del gráfico y de la frecuencia con la que desee realizar la función de búsqueda que está solicitando.
Si los gráficos nunca se vuelven muy grandes, uno podría representar cada nodo como una matriz binaria con un 1 que representa un enlace a un nodo adyacente y un 0 para ningún enlace (por ejemplo, si el tamaño máximo del gráfico fuera 8, entonces si el nodo 0 representaba fácilmente como 01001100 esto indicaría un enlace entre el nodo 1 y los nodos 1, 4 y 5). Con este tipo de representación de datos, para realizar su búsqueda, crearía una representación de nodo exuivalente para cada una de las 2 listas. Cuando tiene este valor, realiza una función AND lógica del primer valor contra cada nodo en la segunda lista … Y luego hace lo mismo para el segundo valor contra la primera lista. Todos estos resultados deben verificarse para asegurarse de que son resultados distintos de cero (cualquier resultado cero indica falta de adyacencia). Este conjunto de operaciones es O (n + m) pero puede o no ser eficiente en la memoria dependiendo del tamaño de su gráfico y el número promedio de conexión nodal conectada. Si su implementación actual usa matrices con índices de 64 bits y un promedio de, digamos, 8 conexiones por nodo … Entonces su gráfica está usando actualmente un promedio de 512 bits por nodo. En este caso, la eficiencia de utilización de la memoria cambia si el tamaño máximo del gráfico es menor o mayor que 512 nodos.
Si desea almacenar los gráficos como indicios, aún puede acelerar sus búsquedas almacenando la lista de adyacencia como un árbol b equilibrado o una tabla hash para hacer que el tiempo de su algoritmo sea O (n • ln (m)).
- ¿Qué son los problemas NP-completos? ¿Cómo podemos resolverlos?
- ¿Cómo funciona el algoritmo iPod shuffle?
- Soy un desarrollador de fuerza bruta, ¿cómo puedo mejorar mis habilidades de algoritmos?
- ¿Cómo funcionan los algoritmos de Google en los motores de búsqueda?
- ¿Cuál es la complejidad Big-O de una búsqueda lineal?
