algorithm - pragmatica - distancia social psicologia
Calcular la distancia social entre dos usuarios. (3)
Habría asumido que esto se haría aplicando un algoritmo de ruta más corta, como la BFS en una base de datos gráfica . Pero parecen almacenar todo su gráfico en la memoria, al menos de acuerdo con this .
Estoy seguro de que el algoritmo en última instancia se reduce a algún tipo de ruta más corta sobre una estructura gráfica (nodos y bordes).
Editar: Cambiado el algoritmo según los comentarios.
Cómo codificaría un algoritmo eficiente que puede devolver una ''distancia'' social entre dos usuarios.
Por ejemplo, cuando visita un perfil en LinkedIn, puede ver cuál es la distancia entre usted y el usuario.
-> el usuario A es amigo del usuario B - y B es amigo de C. cuando A visitará C (la distancia será 1)
El gráfico es enorme y me pregunto cómo se puede realizar tan rápido.
Sé que es probable que esta pregunta se cierre, pero realmente creo que es una pregunta de programación / algoritmo; no especificaría ningún idioma porque me interesa el concepto.
Primero el gráfico necesita ser poblado. No puedo decir acerca de cómo obtiene el gráfico vinculado, probablemente haciendo un BFS o DFS de los nodos, descubra los gráficos y establezca vínculos. Para encontrar la distancia entre cualquiera de los dos mejores es hacer un BFS desde el nodo de origen y detenerse cuando se encuentra el destino. Los enlaces no tienen pesos, creo, si no implican otra cosa.
En este caso, debe aplicar un BFS cada uno para encontrar la distancia entre cada par, cuando el nodo de origen es diferente. De lo contrario, puede implementar el algoritmo Flohd Warshall para obtener todas las rutas más cortas de origen y destino, y como cada enlace tiene el mismo peso, obtendrá lo que desea. En este caso, una vez hecha la estructura, para cualquier origen y destino se puede encontrar la distancia más corta. Un problema es que la red siempre está cambiando, por lo que se necesita un nuevo procesamiento. Por lo tanto BFS creo que será bueno.
Para que el procesamiento sea más rápido, puede implementar BFS para ejecutarse en paralelo. Eche un vistazo al diseño y análisis de un algoritmo de búsqueda no determinista, paralelo y de amplitud en primer lugar.
Suponiendo que no tenga ninguna función heurística sobre la distancia al objetivo, la mejor solución válida es BFS bi-directional :
Idea de algoritmo: realice una búsqueda BFS simultáneamente desde el origen y el destino: [BFS hasta la profundidad 1 en ambas, hasta la profundidad 2 en ambas, ...].
El algoritmo terminará cuando encuentres un vértice v, que está en el frente de BFS.
Comportamiento del algoritmo : el vértice v que termina la ejecución del algoritmo estará exactamente en el medio entre la fuente y el destino.
Este algoritmo producirá un resultado mucho mejor en la mayoría de los casos que BFS desde la fuente [explicación de por qué es mejor que BFS sigue], y seguramente proporcionará una respuesta, si la hay.
¿Por qué es mejor que BFS desde la fuente?
suponga que la distancia entre la fuente y el objetivo es k , y el factor de rama es B [cada vértice tiene bordes B].
BFS se abrirá: 1 + B + B^2 + ... + B^k vértices.
BFS bidireccional se abrirá: 2 + 2B + 2B^2 + 2B^3 + .. + 2B^(k/2) vértices.
para B yk grandes, el segundo es obviamente mucho mejor que el primero.
EDITAR:
NOTA, que esta solución NO requiere almacenar el gráfico completo en la memoria, solo requiere implementar una función: successor(v) que devuelve todos los sucesores de un vértice [todos los vértices a los que puede llegar, dentro de 1 paso desde v]. Con esto, solo deben almacenarse los nodos que abre [ 2 + 2B + ... + 2B^(k/2) como se explicó anteriormente]. Para ahorrar más memoria, puede usar DFS de profundización iterativa desde una dirección, en lugar de BFS, pero consumirá más tiempo.