Como gerar aleatoriamente árvores delimitadoras de altura delimitada?

Para um projeto em que estou trabalhando, devo gerar árvores de abrangência aleatórias com altura delimitada.

Basicamente, faço o seguinte: 1) Gere uma árvore de abrangência 2) Verifique a viabilidade, se possível, mantenha-a.

1) Partindo de uma árvore de abrangência mínima (da Prim ou Kruskal), adiciono uma aresta inexistente e isso cria um ciclo, eu detecto esse ciclo e removo uma das arestas deste ciclo que me fornece uma nova árvore de ampliação e continuo com essa árvore de abrangência adicionando uma nova borda ...

2) Suponha que exista um vértice especial . Para cada vértice , o comprimento do caminho de a deve ser menor que , onde é um parâmetro especificado. $v_{center}$ $v$ $v$ $V_{center}$ $\delta$ $\delta$

Existe alguma maneira melhor (inteligente) de fazer isso?

PS Esqueci de especificar a outra restrição (meu erro): o grau dos vértices também deve ser delimitado.

ds.algorithms graph-algorithms random-walks Arman
fonte

Não sei se entendi direito. Na primeira etapa, você remove a borda aleatoriamente ou para que a altura da árvore seja (possivelmente) reduzida?

Sacha

Eu adiciono e removo aleatoriamente bordas.

Arman

Você poderia experimentar o caminho mais curto aleatório, abrangendo árvores? Ele simplifica as coisas

Yaroslav Bulatov

você tem algum custo nas bordas? você está procurando uma árvore de abrangência com altura

e custo mínimo? Como o @pboothe escreveu, você pode usar o BFS e é isso. O único problema é que o BFS usa muita memória. Se você se preocupa com os custos, pode tentar o algoritmo na wikipedia para árvores de abrangência mínima euclidiana ( en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree ). Tem um tempo de execução de

com

de espaço.

δ

$\delta$

O (n \log n)

$O(n\log n)$

O (n)

$O(n)$

Marcos Villagra

Portanto, seu problema tem três quantidades delimitadas: altura da árvore, grau de cada vértice e distância de v_center, certo? Apenas a restrição de grau limitado torna o problema difícil para NP, mas suponho que você esteja procurando um método que provavelmente produza uma solução rapidamente e não um algoritmo exato.

Jagadish

Respostas:

Eu estava trabalhando em árvores de profundidade delimitada há alguns anos, elas são realmente interessantes. Alguns de meus colegas criaram algoritmos de passagem de mensagens que fizeram um ótimo trabalho, mas não consigo encontrar nenhum código disponível. Escrevemos em estilo físico aqui: http://iopscience.iop.org/1742-5468/2009/12/P12010/ . Eles me disseram que também funciona com limites de graus, embora isso não tenha sido incluído no jornal.

A abordagem que você propõe, que eu chamaria de Markov Chain Monte Carlo, geralmente é um concorrente da abordagem de transmissão de mensagens. Se você estiver interessado em amostrar aproximadamente uniformemente aleatoriamente a partir do conjunto de árvores abrangidas de grau delimitado e profundidade delimitada de um determinado gráfico, sugiro que você altere sua abordagem para usar limites "suaves". Ou seja, em vez de rejeitar uma troca de aresta que faz a árvore violar a profundidade limite, aceite-a, mas com menor probabilidade do que uma troca que não viole o limite. Se você possui um parâmetro que controla quanto menor é essa probabilidade, pode tornar cada vez menos provável a restrição de violar as configurações até chegar a uma solução viável que seja quase uniformemente aleatória.

A grande questão é quanto tempo você precisa para executar a cadeia. Como uma árvore de abrangência com grau no máximo 2 é um caminho hamiltoniano, você deve esperar que qualquer limite genérico seja exponencial no tamanho do gráfico. Mas talvez os gráficos nos quais você esteja interessado sejam especiais de alguma forma.

Abraham Flaxman
fonte

Mais detalhes, além de um filme: healthyalgorithms.wordpress.com/2010/12/23/…

Abraham Flaxman

$S$ $S$ $h$ $h$ $h$

No entanto, não tenho certeza se o algoritmo que você descreveu irá gerar uma árvore de abrangência aleatória. Eu recomendaria olhar algoritmos padrão. Existem dois algoritmos: o algoritmo de Wilson e o algoritmo de Aldous-Broder. Você pode dar uma olhada aqui . Existe um algoritmo mais novo (de aproximação) , mas é bastante complicado.

Além disso, pode haver uma maneira de gerar essa árvore de abrangência com altura limitada diretamente. Mas nunca ouvi falar de tais algoritmos.

Danu
fonte

Use a pesquisa pela primeira vez! Faça um BFS de todos os vértices do gráfico, escolha a árvore resultante da menor altura. Um BFS sempre encontra o caminho da raiz para todos os outros vértices com o menor número de saltos.

Peter Boothe
fonte

Você está definitivamente certo. Começamos a trabalhar com o BFS, mas ele não funcionou devido à restrição de grau nos vértices. Esqueci de mencionar essa restrição (meu erro): o grau dos vértices na árvore gerada também deve ser limitado. Sua resposta está correta com a pergunta atual, mas acho que devo editar minha pergunta.

Arman

Então o problema é quase certamente NPC por redução de Grau Constrained Spanning Tree - en.wikipedia.org/wiki/Degree-constrained_spanning_tree

Peter Boothe