¿Qué es un algoritmo rápido y estable para una ruta aleatoria en un gráfico de nodo?

Tengo un gráfico que consta de nodos y necesito un algoritmo rápido que genere una ruta aleatoria entre dos nodos. Diseñé varios algoritmos desde cero para esto pero parece que no puedo hacerlo bien.¿Qué es un algoritmo rápido y estable para una ruta aleatoria en un gráfico de nodo?

O bien el algoritmo se atasca en los bucles, o cuando guardo el registro de los nodos visitados a veces se queda atascado entre los nodos visitados. Otro problema que encontré es que mi algoritmo era demasiado inestable en rendimiento.

Así que mi pregunta es; ¿Alguien sabe un algoritmo rápido y estable para una ruta aleatoria entre dos nodos alcanzables en un gráfico no dirigido?

Fuente

2012-04-17 Marnix v. R.

¿Qué quieres decir con "al azar?"Podrías obtener distribuciones muy diferentes dependiendo de lo que quieras. ¿Quieres decir" muestras de manera uniforme de todos los caminos posibles entre los nodos? "O" un montón de caminos diferentes de un nodo a otro, incluso si no son estadísticamente al azar? " – templatetypedef

Deje que su gráfico sea G=(V,E). Cree un subconjunto U de V tal que U = { u | there is a path from u to the target }.

Tenga en cuenta que la búsqueda de este subconjunto U es fácil - y se puede hacer en tiempo lineal utilizando DFS o BFS en los bordes invertidos respecto al objetivo de .

El uso de este subconjunto, cree un gráfico G'=(U,E') donde U se define arriba y E' = E [intersection] UxU [los mismos bordes, pero aplicado sólo en vértices en U].

Ejecute al azar (eligiendo qué vértice explorar luego al azar) DFS en G' hasta llegar al objetivo.

Nota - la idea es encontrar un camino - no necesseraly simple, y por lo tanto no se debe mantener un conjunto visited.
Puede agregar una "regla de salto" que si alcanza una cierta profundidad, buscará el objetivo - no aleatorizado, para evitar bucles infinitos en círculos. Se espera
perofrmance ser variable, ya que es lineal en la longitud del camino se encuentran, lo que podría ser muy largo o muy corto ...

Fuente

2012-04-17 20:00:38 amit

que fue mi primera vez que se enseñó –

Esto no será muy uniforme. Si se dirige el gráfico, tal vez podría hacer alguna programación dinámica para contar el número de rutas disponibles como resultado de cada elección de dfs, y usar eso para incluso si fuera –

Depende de lo que entendemos por al azar. Si no te importa lo que significa, has probado monte-carlo method?

Mi puñalada en la oscuridad, pseudocódigo, suponiendo que el objetivo es alcanzable y que tienes un gráfico no dirigido.

1. s <- start node 
2. Choose a random neighbor of s, call that neighbor n. 
3. Add the edge from s to n to the path. 
4. Set s <- n. 
5. Go to 2, unless you've reached the target.

Las advertencias de amit mantienen aquí, también:

Es posible añadir una "regla de ruptura" que si se llega a cierta profundidad, se buscará el objetivo - sin asignación al azar, para evitar bucles infinitos en círculos. Se espera
perofrmance ser variable, ya que es lineal en la longitud del camino se encuentran, lo que podría ser muy largo o muy corto ...

Fuente

2012-04-17 20:02:27 nes1983

¿Qué pasa si en algún punto 'n' no tiene ninguna ruta al objetivo? se quedará atascado en un bucle infinito. – amit

Agregado de accesibilidad como condición previa. Es fácil de arreglar si la condición previa no se cumple. – nes1983

intenté este, pero el problema era que era demasiado inestable, a veces era muy lento. –

Si entiendo bien su pregunta, usted está tratando de generar un uniform spanning tree.

Fuente

2012-04-17 20:30:53

¿Qué es un algoritmo rápido y estable para una ruta aleatoria en un gráfico de nodo?

Respuesta

Cuestiones relacionadas