algorithm - rectangulo - Buen algoritmo para encontrar el diámetro de un gráfico(disperso)
diagrama de flujo para calcular el area de un cuadrado (12)
Tengo un gráfico grande, conectado y disperso en forma de lista de adyacencia. Me gustaría encontrar dos vértices lo más separados posible, es decir, el diámetro del gráfico y dos vértices que lo logren.
Estoy interesado en este problema tanto en casos dirigidos como no dirigidos, para diferentes aplicaciones. En el caso dirigido, por supuesto me importa la distancia dirigida (la ruta más corta dirigida de un vértice a otro).
¿Hay un mejor enfoque que calcular las rutas más cortas de todos los pares?
Editar : por "lo más apartado posible", por supuesto, me refiero al "camino más corto más largo", es decir, el máximo en todos los pares de vértices de la distancia más corta entre uno y otro.
Aquí hay algunas ideas sobre cómo hacer mejor que todos los pares de caminos más cortos en un gráfico no dirigido, aunque no estoy seguro de cuán mejorable sería.
Aquí hay una subrutina que encontrará dos nodos de distancia D, si los hay. Elija un nodo x arbitrario y calcule M [x] = distancia máxima desde x a cualquier otro nodo (utilizando cualquier algoritmo de ruta más corta de origen único). Si M [x]> = D, entonces x es uno de nuestros nodos y el otro es fácil de encontrar. Sin embargo, si M [x] <D, entonces ninguno de los puntos finales que estamos buscando puede ser menor que la distancia D - M [x] desde x (porque hay caminos desde ese nodo a todos los otros nodos, a través de x, de distancia < RE). Así que encuentre todos los nodos de distancia menores a DM [x] de x y márquelos como malos. Elija una nueva x, esta vez asegurándose de evitar todos los nodos marcados como malos y repita. Con suerte, marcaremos muchos nodos como malos, así que tendremos que hacer muchos menos que | V | los cálculos de ruta más corta.
Ahora solo tenemos que configurar D = diam (G) y ejecutar el procedimiento anterior. No sabemos qué es diam (G), pero podemos obtener un rango bastante ajustado para él, como para cualquier x, M [x] <= diam (G) <= 2M [x]. Elija unas pocas x para comenzar, calcule M [x] para cada una y calcule los límites superiores e inferiores en diam (G) como resultado. Luego, podemos hacer una búsqueda binaria en el rango resultante, utilizando el procedimiento anterior para encontrar una ruta de la longitud adivinada, si corresponde.
Por supuesto, esto no está dirigido solo. Creo que podrías hacer un esquema similar con gráficos dirigidos. Los nodos malos son aquellos que pueden alcanzar x en menos de DM [x], y el límite superior en diam (G) no funciona, por lo que necesitaría un rango de búsqueda binaria más grande.
Bueno, he pensado un poco en el problema, y un poco de googlear, y lo siento, pero no puedo encontrar ningún algoritmo que no parezca ser "solo encontrar todos los pares del camino más corto" .
Sin embargo, si supone que Floyd-Warshall es el único algoritmo para computar tal cosa (Big-Theta of | V | ^ 3), entonces tengo un poco de buenas noticias para usted: Algoritmo de Johnson para Sparse Graphs (gracias, ¡CLRS confiable!) calcula todos los pares de caminos más cortos en (Big-Oh (| V | ^ 2 * lgV + VE)), que debe ser asintóticamente más rápido para gráficos dispersos.
Wikipedia dice que funciona para dirigido (no estoy seguro de que no sea dirigido, pero al menos no puedo pensar en una razón por la que no), aquí está el link .
¿Hay algo más sobre el gráfico que pueda ser útil? Si se puede mapear fácilmente en un plano 2D (por lo tanto, sus pesos planos y de borde obedecen a la desigualdad del triángulo [es posible que tenga que cumplir un requisito más estricto, no estoy seguro]), es posible que pueda desglosar algunos algoritmos geométricos (El casco convexo puede ejecutarse en nlogn, y encontrar el par más lejano de puntos es fácil desde allí).
¡Espero que esto ayude! - Agor
Editar: Espero que el enlace funcione ahora. Si no, solo busca en google. :)
Elija un vértice v y haga BFS (v), esto calculará la distancia de v para todos los vértices. Obtener la distancia más larga. Esto es O (V + E)
Ahora ejecute este algoritmo para todos los v vértices y elija el máximo de estas distancias más largas. Complejidad general: O (V * (V + E))
No conozco un método mejor para calcular el diámetro que no sean todas las rutas más cortas, pero Mathematica utiliza la siguiente aproximación para PseudoDiameter:
- Un gráfico geodésico es el camino más corto entre dos vértices de un gráfico. El diámetro del gráfico es la longitud más larga posible de todas las geodesias gráficas del gráfico. PseudoDiameter encuentra un diámetro de gráfico aproximado. Funciona comenzando desde un vértice u, y encuentra un vértice v que está más alejado de ti. Este proceso se repite tratando a v como el nuevo vértice inicial y termina cuando la distancia gráfica ya no aumenta. Se elige un vértice desde el último nivel establecido que tiene el grado más pequeño como el vértice de inicio final u, y se realiza un recorrido transversal para ver si se puede aumentar la distancia del gráfico. Esta distancia gráfica se toma como el pseudo-diámetro.
http://reference.wolfram.com/mathematica/GraphUtilities/ref/PseudoDiameter.html
No estoy seguro de si se ajusta a la factura, pero es interesante:
HADI: Estimación de diámetro rápido y minería en gráficos masivos con Hadoop
U. Kang, C. Tsourakakis, AP Appel, C. Faloutsos, J. Leskovec, "HADI: Estimación de diámetro rápido y extracción en gráficos masivos con Hadoop", CMU ML Tech Report CMU-ML-08-117, 2008.
Perdónenme si mi respuesta no es correcta en términos de sintaxis, pero mi curso de Algoritmo fue hace un tiempo (y no en inglés).
Si entiendo su problema correctamente, quiere saber cuál es el número más alto con el que puede contar comenzando desde el nodo A y llegando al nodo B sin "seguir" sus pasos. Si este es el caso, me imagino su gráfico como acíclico (la opción cíclica viene después).
En primer lugar, el límite superior es el número de bordes. La forma en que veo la cosa es: tome un nodo, cree un árbol donde el nodo esté en la raíz y cada nodo posterior al que pueda llegar esté en el siguiente nivel. La altura del árbol que construyes es el diámetro, y las hojas son los nodos que están a esa distancia. Si esa distancia = número de bordes, ya terminaste. Si no, elige otro nodo y repite.
Creo que es similar a la construcción de una búsqueda de amplitud. Sin saber mucho más sobre el gráfico, podría emplear algunas heurísticas para ver qué orientación de árbol (es decir, qué nodo debe seleccionarse primero) sería mejor, pero ese es otro tema.
En cuanto a la ciclicidad del gráfico, como han señalado otros, pueden conducir a bucles infinitos. Una forma de deshacerse de ellos podría ser "descartar" los nodos que pertenecen a un ciclo y agregar la ruta más larga entre ellos como el valor que obtendrá al ingresar al ciclo y salir de él, tocar cada nodo solo una vez .
Ahora, como dije, este método podría ser muy similar a hacer el camino más corto de todos los paíes. La peor complejidad de caso es sin duda la misma, y no podría ser de otra manera.
Realmente dudo que exista algún método para encontrar la ruta más corta más larga sin tener que usar algún tipo de algoritmo de ruta más corta para todos los pares (encontrar la ruta más corta de fuente única repetidamente es básicamente hacer todos los pares en el peor de los casos).
''Diámetro'' se vuelve difícil de definir en términos de la ''ruta más larga'' si el gráfico no es un árbol o un DAG. La ruta ''más larga'' puede ser infinita si hay ciclos en el gráfico. Por lo tanto, un recorrido simple del gráfico no puede producir la ruta más larga sobre todos los nodos. Como ya ha indicado que su gráfico no es necesariamente acíclico, y está interesado en el camino "más corto más largo", no parece haber ningún método que pueda evitar encontrar el camino más corto para todos los nodos. Usar el Algoritmo de Johnson, como sugirió Agor, es probablemente el mejor para hacer eso.
Por supuesto, puede seguir un enfoque basado en la heurística. El algoritmo que usa el vértice pseudo-periférico parece ser el enfoque más comúnmente utilizado.
Sí, hay un mejor método para encontrar el Diámetro del gráfico. Aquí hice una clase simple para demostrarlo. Los vértices serían los puntos en su gráfico.
public class MyTestClass
{
//Simple Point struct
struct Vertex
{
public float X, Y;
public Vertex(float pX, float pY)
{
X = pX;
Y = pY;
}
}
//For getting the bounds of your graph
struct BoundingBox
{
public float Left, Right, Bottom, Top;
public BoundingBox(float pLeft, float pRight, float pBottom, float pTop)
{
Left = pLeft;
Right = pRight;
Bottom = pBottom;
Top = pTop;
}
}
//Properties
Vertex[] vertices;
BoundingBox bound;
float diameter;
//Constructor
//Here is the fastest way to get the diameter >>
public MyTestClass()
{
//Init objects
vertices = new Vertex[100];
for(int i = 0; i != vertices.Length; ++i) vertices[i] = new Vertex(i, i);
bound = new BoundingBox(vertices[0].X, vertices[0].X, vertices[0].Y, vertices[0].Y);
//Calculate BoundingBox
for(int i = 0; i != vertices.Length; ++i)
{
bound.Left = (vertices[i].X <= bound.Left) ? vertices[i].X:bound.Left;
bound.Right = (vertices[i].X >= bound.Right) ? vertices[i].X:bound.Right;
bound.Bottom = (vertices[i].Y <= bound.Bottom) ? vertices[i].Y:bound.Bottom;//NOTE: If Y is faces down, then flip bottom & top comparison
bound.Top = (vertices[i].Y >= bound.Top) ? vertices[i].Y:bound.Top;
}
//Messure Size of the BoundingBox
float vecX = (bound.Right-bound.Left);
float vecY = (bound.Top-bound.Bottom);
diameter = (float)System.Math.Sqrt((vecX*vecX) + (vecY*vecY));
}
}
Un método sucio:
Sabemos que para un gráfico G (V, E) con | V | = ny | E | = m, el algoritmo Dijkstra se ejecuta en O(m+nlogn) y esto es para una sola fuente. Para el problema de todos los pares, debe ejecutar Dijkstra para cada nodo como punto de partida.
Sin embargo, si tiene muchas máquinas, puede hacer paralelo fácilmente a este proceso.
Este método es más fácil de implementar, definitivamente no es muy bueno.
Una forma de obtener una estimación de este número es comenzar en un punto aleatorio y hacer un algoritmo de "fuego de césped" primero, marcando la distancia más corta a cada nodo. La distancia más larga aquí es tu estimación.
Ejecutar este algoritmo extremadamente rápido varias veces con diferentes puntos de partida y luego tomar el máximo aumentará la precisión de la estimación y, por supuesto, le dará un límite inferior decente. Dependiendo de la distribución y la conectividad de su gráfico, ¡esta estimación puede ser incluso precisa!
Si su gráfica es lo suficientemente grande, el análisis asintótico de cómo cambia la estimación a medida que agrega más muestras podría permitirle proyectar a una conjetura aún mejor.
Si está interesado en una respuesta exacta, parece poco probable que pueda salirse con la suya cortando esquinas demasiado a menos que su gráfico sea fácil de dividir en componentes que estén débilmente conectados entre sí, en cuyo caso puede restringir su búsqueda al más corto camino entre todos los pares de vértices en diferentes componentes.
si el gráfico es un árbol (y no dirigido). simplemente puede ejecutar 2 dfs. Comience en un nodo aleatorio u y dfs para encontrar el nodo más lejano v. Luego comience en v y encuentre la longitud más lejana. Esa longitud es óptima
Editar Estoy recuperando de nuevo, simplemente para poder seguir comentando. Tengo algunos comentarios sobre el algoritmo de Johnson debajo de esta respuesta. - Aaron
Mi comentario original : Yo también tengo curiosidad sobre este problema, pero no tengo una respuesta. Parece estar relacionado con el Árbol de expansión mínimo , el subgráfico que conecta todos los vértices pero que tiene menos (o el menor peso) de los bordes. Ese es un viejo problema con una serie de algoritmos; algunos de los cuales parecen bastante fáciles de implementar.
Inicialmente había esperado que el diámetro fuera obvio una vez que se hubiera encontrado el MST, pero estoy perdiendo la esperanza ahora :-( Quizás el MST se puede usar para colocar un límite superior razonable en el diámetro, que puedes usar para acelerar su búsqueda del diámetro real?