• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

pedrosorio

Dúvida sobre procura em grafos:Breadth-first vs Iterative Deepening Depth-first

14 mensagens neste tópico

Digam-me lá se estou a pensar bem:

Ao fazer bfs em grafos guarda-se os nós já processados para garantir que não voltamos a processá-los numa profundidade superior, certo?

Já em idfs não fazemos isso porque poderíamos fechar nós que na realidade podem ser encontrados a profundidades inferiores.

A ideia com que tinha ficado era que, se bem implementados, bfs e idfs deveriam dar exactamente a mesma solução (óptima), isto porque em termos cumulativos os nós são visitados pela mesma ordem. A grande diferença é que bfs tem que guardar todos os nós (complexidade espacial elevada) enquanto idfs tem que percorrer todos os nós com profundidade inferior à solução mais do que uma vez (complexidade temporal superior).

Em particular estava à espera que o número de nós percorridos na última iteração de idfs fosse exactamente o mesmo que é percorrido por bfs. No entanto parece-me que isso só acontece em árvores e não em grafos já que o bfs tem informação prévia que lhe permite expandir muito menos nós a profundidades superiores.

Elucidem-me  :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

- Em dfs (e idfs é só uma versão que limita a profundidade) guardas os nós já visitados na mesma, senão basta o grafo ter ciclos e o programa já não termina, a menos, claro, no caso do idfs. Assim, podes optar por memorizar ou não os nós já visitados em cada dfs, mas se não o fizeres o programa vai processar várias vezes os mesmos nós, possivelmente entrando em ciclo, que só pára quando se atinge o limite de profundidade. Parece-me muito melhor opção memorizar os nós visitados e evitar, assim, voltar a processá-los no dfs com o mesmo limite de profundidade; claro que terás que limpar esta lista quando incrementas a profundidade máxima e voltas a chamar o dfs.

- Em bfs também guardas os nós já visitados para evitar visitá-los novamente, tal como no dfs, mas o espaço adicional de que falas deve-se à fila que é necessária para assegurar que os nós são visitados na ordem certa, e que pode crescer muito depressa.

Já em idfs não fazemos isso porque poderíamos fechar nós que na realidade podem ser encontrados a profundidades inferiores.

Não percebi.

A ideia com que tinha ficado era que, se bem implementados, bfs e idfs deveriam dar exactamente a mesma solução (óptima), isto porque em termos cumulativos os nós são visitados pela mesma ordem. A grande diferença é que bfs tem que guardar todos os nós (complexidade espacial elevada) enquanto idfs tem que percorrer todos os nós com profundidade inferior à solução mais do que uma vez (complexidade temporal superior).

Certo, com o pormenor do espaço usado pelo bfs ser maior devido à fila usada.

Em particular estava à espera que o número de nós percorridos na última iteração de idfs fosse exactamente o mesmo que é percorrido por bfs. No entanto parece-me que isso só acontece em árvores e não em grafos já que o bfs tem informação prévia que lhe permite expandir muito menos nós a profundidades superiores.

Se guardares os nós já visitados nos dois, número de nós visitados é igual, mesmo se o grafo não for uma árvore. Cada nó é visitado uma vez.

Não sei se percebi bem o que querias dizer, mas se percebi, penso que isto deve esclarecer :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites
Não percebi.

Se guardares todos os nós ao fazer dfs com profundidade limitada e não os visitares novamente, corres o risco de não encontrar a solução óptima porque, podes fechar um nó a uma profundidade maior que poderia ser encontrado posteriormente a uma profundidade menor (porque estamos a percorrer em profundidade e não em largura).

Certo, com o pormenor do espaço usado pelo bfs ser maior devido à fila usada.

Em teoria o espaço usado pelo bfs seria muito superior porque podia descartar os nós já percorridos em dfs mas se estou a guardar os nós todos em dfs com profundidade limitada, acabo por gastar praticamente o mesmo espaço, certo?

Se guardares os nós já visitados nos dois, número de nós visitados é igual, mesmo se o grafo não for uma árvore. Cada nó é visitado uma vez.

Mas pelo que disse acima, em bfs podes guardar todos os nós que vais encontrando e tens a garantia que já não precisas de os explorar. Em dfs com profundidade limitada (num grafo) o percurso teoricamente não deve ser o mesmo porque, quando estou a expandir um nó a profundidade 3 ainda não tenho informação sobre uma série de nós de profundidade 1 e 2 e portanto também os expando se forem sucessores deste (coisa que não aconteceria em bfs).

Estás a perceber o meu problema? Da forma como estou a colocar as coisas não parece haver vantagem nenhuma em usar idfs até porque expande mais nós, ou o meu raciocínio está a falhar nalgum ponto?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Se guardares todos os nós ao fazer dfs com profundidade limitada e não os visitares novamente, corres o risco de não encontrar a solução óptima porque, podes fechar um nó a uma profundidade maior que poderia ser encontrado posteriormente a uma profundidade menor (porque estamos a percorrer em profundidade e não em largura).

Em teoria o espaço usado pelo bfs seria muito superior porque podia descartar os nós já percorridos em dfs mas se estou a guardar os nós todos em dfs com profundidade limitada, acabo por gastar praticamente o mesmo espaço, certo?

Não.

Estás a perceber o meu problema? Da forma como estou a colocar as coisas não parece haver vantagem nenhuma em usar idfs até porque expande mais nós, ou o meu raciocínio está a falhar nalgum ponto?

Está a falhar na memória utilizada.

3250020202016.png

Considera que tens uma árvore binária completa (caso particular de um grafo) com 20 níveis (esta da figura tem 5 níveis -> (25 - 1) nós). Assim, a árvore tem cerca de 1 milhão de nós.

Imagina que queres o caminho mais curto desde a raíz até uma das folhas, ou seja, o caminho mais curto vale 19 (numa árvore só existe um único caminho entre 2 nós).

Se fizeres uma BFS, vais expandir a árvore por níveis. Após visitares os nós do nível 19, possuis 219 nós na fila (os nós do último nível, onde está o destino -- cerca de 500.000).

Em comparação, uma dfsid testa as profundidades 1,2,...19, sendo mais lento que uma BFS. Mas por outro lado, só possuis no máximo 19 nós em memória (na stack de recursividade).

Com 1 milhão de nós, a BFS ainda é suportável, mas se o número de nós crescer, rapidamente ficamos sem memória  :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Se guardares todos os nós ao fazer dfs com profundidade limitada e não os visitares novamente, corres o risco de não encontrar a solução óptima porque, podes fechar um nó a uma profundidade maior que poderia ser encontrado posteriormente a uma profundidade menor (porque estamos a percorrer em profundidade e não em largura).

Daí teres que limpar a lista de nós visitados de cada vez que incrementas o limite de profundidade e chamas o dfs de novo. Assim isso já não acontece.

Em teoria o espaço usado pelo bfs seria muito superior porque podia descartar os nós já percorridos em dfs mas se estou a guardar os nós todos em dfs com profundidade limitada, acabo por gastar praticamente o mesmo espaço, certo?

Penso que sim. Claro que depende do grafo, e se for uma árvore não precisas de guardar os nós visitados no dfs.

Mas pelo que disse acima, em bfs podes guardar todos os nós que vais encontrando e tens a garantia que já não precisas de os explorar. Em dfs com profundidade limitada (num grafo) o percurso teoricamente não deve ser o mesmo porque, quando estou a expandir um nó a profundidade 3 ainda não tenho informação sobre uma série de nós de profundidade 1 e 2 e portanto também os expando se forem sucessores deste (coisa que não aconteceria em bfs).

O percurso não é o mesmo, a ordem de visita dos nós é diferente, mas acabam por ser todos visitados apenas uma vez se memorizares os nós já visitados e não voltares a processá-los. Nesse exemplo, se estás a expandir para profundidade 3, supõe-se que já chamaste dfs com profundidades 1 e 2 e que já visitaste esses nós. Ao expandires para a profundidade 3, se os nós de profundidade 1 e 2 forem filhos do nó que estás a expandir, acabas por visitá-los, sim, mas se os memorizares não voltas a processá-los nesse dfs.

Estás a perceber o meu problema? Da forma como estou a colocar as coisas não parece haver vantagem nenhuma em usar idfs até porque expande mais nós, ou o meu raciocínio está a falhar nalgum ponto?

Sim, também me parece que a grande vantagem do idfs é mesmo a aplicação em árvores.

@mogers, para o que postaste entretanto: esse caso é uma árvore. O pedrosorio está a questionar a performance a nível de memória do idfs para outro tipo de grafos, onde é preciso armazenar uma lista de nós já visitados.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

A árvore é o caso particular de um grafo em que isso funciona tudo perfeitinho, ou seja, idfs não gasta memória praticamente nenhuma e não é preciso guardar nós exactamente porque é uma árvore.

Se leres os meus posts mogers, vais ver que todo o meu problema se situa no processamento de grafos em geral pela idfs. Como é:

-> Guardo nós para não os revisitar e fico com espaço ocupado igual (na realidade superior) a bfs porque em idfs não tenho informação sobre muitos nós que estão a baixa profundidade e portanto acabo por expandir mais

OU

-> Não guardo nós, fico com espaço ocupado mínimo mas expando MUITO MAIS nós.

Repito: O meu problema não tem nada a ver com árvores, percebo completamente os conceitos de procura em largura, profundidade limitada, profundidade limitada iterativa, em termos de memória, de nós visitados em cada caso e da necessidade de processar várias vezes os nós a baixa profundidade em árvores.

Quando digo que idfs processa mais nós em grafos estou a referir-me se quiserem à última iteração, aquela em que o limite se situa na profundidade da solução óptima. E tal acontece quer guarde os nós já processados (fazendo com que o espaço ocupado seja igual a bfs) e acontece ainda mais marcadamente se não os guardar (com uma idfs "clássica" se quisermos).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Daí teres que limpar a lista de nós visitados de cada vez que incrementas o limite de profundidade e chamas o dfs de novo. Assim isso já não acontece.

O problema não é esse, se estou em limite de profundidade 4 e visito um nó a profundidade 4 que está a 1 movimento da solução, se o guardar, continuo a fazer pesquisa dfs limitada a profundidade 4 e posso encontrar esse mesmo nó a profundidade 3 sendo que a solução está a profundidade 4 mas não o vou visitar porque guardei o nó.

Exemplo:

X->A; X->B; A->C; C->D; D->S; B->C 

X é o nó inicial, S é a solução. Se for por A primeiro em dfs com limite 4 faço X->A->C->D parou, fecho D.

Continuo com limite 4 faço X->C->D parou porque D está fechado -> não encontro a solução óptima em 4 movimentos.

O percurso não é o mesmo, a ordem de visita dos nós é diferente, mas acabam por ser todos visitados apenas uma vez se memorizares os nós já visitados e não voltares a processá-los. Nesse exemplo, se estás a expandir para profundidade 3, supõe-se que já chamaste dfs com profundidades 1 e 2 e que já visitaste esses nós. Ao expandires para a profundidade 3, se os nós de profundidade 1 e 2 forem filhos do nó que estás a expandir, acabas por visitá-los, sim, mas se os memorizares não voltas a processá-los nesse dfs.

Se tenho que apagar a lista de memorizados cada vez que actualizo o limite então volto a processá-los.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

O problema não é esse, se estou em limite de profundidade 4 e visito um nó a profundidade 4 que está a 1 movimento da solução, se o guardar, continuo a fazer pesquisa dfs limitada a profundidade 4 e posso encontrar esse mesmo nó a profundidade 3 sendo que a solução está a profundidade 4 mas não o vou visitar porque guardei o nó.

Exemplo:

X->A; X->B; A->C; C->D; D->S; B->C 

X é o nó inicial, S é a solução. Se for por A primeiro em dfs com limite 4 faço X->A->C->D parou, fecho D.

Continuo com limite 4 faço X->C->D parou porque D está fechado -> não encontro a solução óptima em 4 movimentos.

Ok, tens razão. dfsid é para árvores :) Esquece lá o que eu disse uns posts acima :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pois isso é que me está a chatear porque tudo o que li até agora refere árvores e é o que parece fazer sentido... A última parte de um projecto que tenho numa cadeira consiste em comparar um algoritmo de procura informada com bfs e idfs mas ao nível de grafos está a fazer-me confusão como vou abordar a questão. Obrigado pelas respostas de qualquer forma :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pois isso é que me está a chatear porque tudo o que li até agora refere árvores e é o que parece fazer sentido... A última parte de um projecto que tenho numa cadeira consiste em comparar um algoritmo de procura informada com bfs e idfs mas ao nível de grafos está a fazer-me confusão como vou abordar a questão. Obrigado pelas respostas de qualquer forma :)

Podes sempre considerar uma implementação alternativa (mas muito estúpida, vs bfs) do idfs, que seria guardar não só os nós já visitados mas também a profundidade a que foram visitados. Se atinges um nó já visitado mas estás numa profundidade inferior àquela a que o nó foi visitado, visitas na mesma :)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Acho que não tás a perceber como uma dfsid (ou idfs como preferem chamar) funciona.

Eu dei um exemplo de uma árvore como grafo para ser mais fácil de se perceber. Todas as propriedades que referi se mantêm em grafos genéricos. Numa árvore apenas é mais fácil de se ver.

Ou seja, numa dfsid só tens no máximo N nós em memória em que N é a profundidade máxima imposta.

No grafo que referiste, a pesquisa processa-se assim:

- Profundidade 1

X não é solução

- Profundidade 2

X -> A : A não é solução

X -> B : B não é solução

- Profundidade 3

X -> A -> C

X -> B -> C

- Produndidade 4

X -> A -> C -> B

X -> A -> C -> D

X -> B -> C -> A

X -> B -> C -> D

- Profundidade 5

X -> A -> C -> B -> (C|X) já foram visitados, ignora

X -> B -> C -> A -> (C|X) já foram visitados, ignora

X -> A -> C -> D -> S : Cheguei à solução. A resposta é 5.

Em cada passo é uma dfs normal. Podes guardar os visitados num array de booleanos marcando como visitado quando entras num nó e desmarcando quando terminas a função.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Eu percebo como funciona idfs só me fazia confusão a sua implementação em grafos (exactamente por não ser claro como se deve lidar com nós já visitados).

Estás a dizer-me que a única alteração face a um dfs em árvore é guardar a informação sobre se um nó está na pilha de recursão? Isso faz sentido (porque assim os requisitos de memória são os típicos de uma idfs), mas é como referi, ao contrário do que acontece numa árvore, nessa abordagem o número de nós explorados (contando apenas a última iteração de idfs) é muitíssimo superior a uma bfs (pelo raciocínio que já expliquei anteriormente).

Um detalhe de implementação é que não posso simplesmente usar um array para saber se está na pilha de recursão porque os nós são configurações de um tabuleiro de jogo e gero-as dinamicamente à medida que exploro o grafo (mas tenho uma tabela de hash implementada para isso mesmo).

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Em comparação, uma dfsid testa as profundidades 1,2,...19, sendo mais lento que uma BFS.

Yah, eu tinha dito isso :) Perdes mais tempo, ganhas memória.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Yah, eu tinha dito isso :) Perdes mais tempo, ganhas memória.

Lol, a minha dúvida nunca foi sobre idfs, devia ter exposto isso de forma mais clara. Tenho a perfeita noção da razão pela qual é mais lento em árvores do que a bfs. Em grafos essa desvantagem temporal é muitíssimo acentuada porque o número de nós a visitar em cada iteração é superior ao número de nós que a bfs visita. Para teres uma ideia, com o problema que estou a considerar e a solução a profundidade 40, já na iteração 20 (i.e. com limite de profundidade 20) o idfs visita mais nós do que a toda a bfs.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora