¿Cómo puedo generar al azar árboles de altura limitada que abarquen árboles?

9

Para un proyecto en el que estoy trabajando, debería generar árboles de expansión aleatorios con altura acotada.

Básicamente hago lo siguiente: 1) Generar un árbol de expansión 2) Verificar la viabilidad, si es posible, mantenerlo.

1) Comenzando desde un árbol de expansión mínimo (Prim o Kruskal) agrego un borde no existente y esto crea un ciclo, detecto este ciclo y elimino uno de los bordes de este ciclo que me da un nuevo árbol de expansión y continúo con este árbol de expansión agregando un nuevo borde ...

2) Supongamos que hay un vértice especial . Para cada vértice v , la longitud de la ruta de v a V c e n t e r debería ser menor que δ , donde δ es un parámetro dado.vcentervvVcenterδδ

¿Hay alguna forma mejor (inteligente) de hacer esto?

PD: Olvidé especificar la otra restricción (mi error): el grado de los vértices también debería estar limitado.

Arman
fuente
No estoy seguro si hago esto bien. En el primer paso, ¿elimina el borde de forma aleatoria o para que la altura del árbol se reduzca (posiblemente)?
Sacha
Agrego y elimino bordes al azar.
Arman
¿Podrías probar un camino aleatorio más corto que abarque árboles? Simplifica las cosas
Yaroslav Bulatov
¿tienes algún costo en los bordes? ¿Está buscando un árbol de expansión con altura y costo mínimo? Como @pboothe escribió, puede usar BFS y eso es todo. El único problema es que BFS usa demasiada memoria. Si le importan los costos, puede probar el algoritmo en wikipedia para árboles de expansión mínima euclidiana ( en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree ). Tiene un tiempo de ejecución de O ( n log n ) con O ( n ) de espacio. δO(nlogn)O(n)
Marcos Villagra
Entonces su problema tiene tres cantidades limitadas: altura del árbol, grado de cada vértice y distancia desde v_center, ¿es así? Solo la restricción del grado limitado en sí mismo hace que el problema sea difícil de resolver, pero supongo que está buscando un método que probablemente produzca una solución rápidamente y no un algoritmo exacto.
Jagadish

Respuestas:

7

Estuve trabajando en árboles de expansión de profundidad limitada hace unos años, son realmente interesantes. A algunos de mis colegas se les ocurrieron algoritmos de paso de mensajes que hicieron un gran trabajo, pero no puedo encontrar ninguno de sus códigos disponibles. Lo escribimos en un estilo de física aquí: http://iopscience.iop.org/1742-5468/2009/12/P12010/ . Me han dicho que también funciona con límites de grado, aunque eso no llegó al papel.

El enfoque que propone, que yo llamaría Markov Chain Monte Carlo, es a menudo un competidor del enfoque de transmisión de mensajes. Si está interesado en muestrear de manera aproximadamente uniforme al azar del conjunto de árboles que abarcan grados limitados y profundidades delimitadas de un gráfico dado, sugiero alterar su enfoque para utilizar límites "suaves". Es decir, en lugar de rechazar un intercambio de borde que hace que el árbol viole el límite de profundidad, acéptelo, pero con menor probabilidad que un intercambio que no viole el límite. Si tiene un parámetro que controla qué tan baja es esta probabilidad, puede hacer que la restricción que viola las configuraciones sea cada vez menos probable hasta que llegue a una solución factible que sea casi aleatoria de manera uniforme.

La gran pregunta es cuánto tiempo necesita para ejecutar la cadena. Dado que un árbol de expansión con un grado máximo de 2 es un camino hamiltoniano, debe esperar que cualquier límite genérico sea exponencial en el tamaño del gráfico. Pero tal vez los gráficos que le interesan sean especiales de alguna manera.

Abraham Flaxman
fuente
2
Más detalles, más una película: healthyalgorithms.wordpress.com/2010/12/23/…
Abraham Flaxman
3

SShhh

Sin embargo, no estoy seguro de si el algoritmo que describió generará un árbol de expansión aleatorio. En su lugar, recomendaría buscar algoritmos estándar. Hay dos algoritmos: el algoritmo de Wilson y el algoritmo de Aldous-Broder. Puedes echar un vistazo aquí . Hay un algoritmo más nuevo (de aproximación) pero es bastante complicado.

Además, podría haber una manera de generar este árbol de expansión con altura limitada directamente. Pero nunca he oído hablar de tales algoritmos.

Danu
fuente
1

Utilice la búsqueda de amplitud primero! Haga un BFS desde cada vértice en el gráfico, elija el árbol resultante de menor altura. Un BFS siempre encuentra la ruta desde la raíz a cualquier otro vértice con la menor cantidad de saltos.

Peter Boothe
fuente
Definitivamente tienes razón. Comenzamos a hacer con BFS pero no funcionó debido a la restricción de grado en los vértices. Olvidé mencionar acerca de esta restricción (mi error): el grado de los vértices en el árbol generado también debería estar limitado. Su respuesta es correcta con la pregunta actual, pero creo que debería editar mi pregunta.
Arman
Entonces su problema es casi seguro que la APN por la reducción del grado restringida Spanning Tree - en.wikipedia.org/wiki/Degree-constrained_spanning_tree
Peter Boothe