5

Gostaria de desenvolver um algoritmo que faz a busca por profundidade em uma árvore binária, mas não estou conseguindo.

Ao fazermos a árvore atribuímos a cada nó o custo (custo para transitar de um nó ao outro) e a heurística (valor heurístico de cada nó), para fazermos a busca por profundidade não levamos em consideração esses dois valores.

A classe que gera os nós da árvore é a seguinte:

public class BTreeNode {

    private String nome; // identificação do nó de árvore
    private BTreeNode sucessor1 = null; // filho 1
    private BTreeNode sucessor2 = null; // filho 2
    private int custo1; // custo para 1
    private int custo2; // custo para 2
    private int hInfo; // informação heurística

    /**
     * Construtor para o BTreeNode
     * 
     * @param s
     *            indica o nome para o BTreeNode que está sendo criado
     */
    public BTreeNode(String s) {
        this.nome = s;
    }

    /**
     * Construtor para o BTreeNode
     * 
     * @param s indica o nome para o BTreeNode que está sendo criado
     * @param h indica o valor heuristico para o BTreeNode que está sendo criado
     *            
     */
    public BTreeNode(String s, int h) {
        this.nome = s;
        this.hInfo = h;
    }

    /**
     * Insere os sucessores de um BTreeNode. Tenta inserir no sucessor1. Caso
     * não esteja nulo, insere no sucessor2
     * 
     * @param node
     *            BTreeNode a ser inserido
     * @param custo
     *            Custo de transição de um nó de árvore até o sucessor sendo
     *            inserido
     */
    public void setSucessor(BTreeNode node, int custo) {

        if (this.sucessor1 == null) {
            this.sucessor1 = node;
            this.custo1 = custo;
        } else if (this.sucessor2 == null) {
            this.sucessor2 = node;
            this.custo2 = custo;
        }

    }

    public int gethInfo() {
        return hInfo;
    }

    public void sethInfo(int hInfo) {
        this.hInfo = hInfo;
    }

    public String getNome() {
        return nome;
    }

    public BTreeNode getSucessor1() {
        return sucessor1;
    }

    public BTreeNode getSucessor2() {
        return sucessor2;
    }

    public int getCusto1() {
        return custo1;
    }

    public int getCusto2() {
        return custo2;
    }   
}

Após criarmos cada nó e definirmos seus filhos usamos essa classe para definir qual nó será a raiz da árvore:

public class BTree {

    private BTreeNode raiz;

    /**
     * Construtor de uma árvore BTree
     * 
     * @param r
     *            BTreeNode passado como raiz da árvore
     */
    public BTree(BTreeNode r) {
        this.raiz = r;
    }

    public BTreeNode getRaiz() {
        return raiz;
    }

    public void setRaiz(BTreeNode raiz) {
        this.raiz = raiz;
    }
}

Criamos então outra classe que deveremos varrer a árvore por busca de profundidade, o método da busca por profundidade recebe como parâmetro a árvore e o nó final que desejamos encontrar na varredura da arvore, quando encontrarmos esse nó o método retorna um array com todos os nós que se passaram até chegar no nó esperado.

public class DepthRule extends BTreeRule {

    @Override
    public ArrayList<BTreeNode> getPath(BTree tree, String goalName) {
        // Local que faz o código de busca profundidade
        return null; // o metodo de busca retorna um array com todos os elementos que o    //algoritmo passou na arvore

    }
}

Estou varrendo a árvore pelo lado esquerdo, mas não estou conseguindo voltar na árvore.

2 Respostas 2

5

Realmente, recursividade é a forma mais intuitiva de fazer a busca em profundidade porque é fácil perceber que cada subárvore pode ser considerada como uma nova árvore (e tratada da mesma forma). Assim, pra aprender, eu sugiro seguir a sugestão da resposta do colega @YuriCalistrato.

Porém, considerando que você cita na sua questão atributos como custo (custo de "navegar" de um nó a outro na árvore) e heurística (estimativa de quantos nós faltam até a solução/nó final de interesse), outra possibilidade interessante é não usar recursividade, substituindo ela por uma fila de nós a serem processados.

A ideia é simples:

  1. Ao navegar até um nó qualquer da árvore, você expande os seus nós filhos (acessa-os por algum método) e adiciona-os ao início de uma fila (pode ser um ArrayList, por exemplo).

  2. O próximo nó a ser navegado vai ser o primeiro disponível na fila. Você verifica se ele é a solução, e se não for repete o processo a partir do passo 1.

Essa abordagem é interessante simplesmente porque permite que você facilmente altere o seu algoritmo para implementar outros tipos de busca, já que é a ordem de inserção/remoção dos nós na fila que indica como o processamento ocorre:

  • Se os nós filhos são inseridos no início da fila, eles vão ser imediamente processados a seguir. Logo, o processamento progressivamente afunda na árvore, ou seja, está se implementando uma busca em profundidade.

  • Se os nós filhos são inseridos no final da fila, eles vão ser processados apenas após todos os que ali já estiverem. Logo, o processamento primeiro avalia todos os nós em um mesmo nível, para então aprofundar na árvore. Ou seja, está se implementando uma busca em largura.

  • Se os nós filhos são inseridos na fila de forma prioritária (isto é, a ordem da fila é calculada segundo alguma métrica numérica criada por você), o algoritmo vai processá-los segundo essa ordem. Assim, você pode construir uma fila prioritária usando um custo, uma heurística ou a soma desses valores para construir variações na busca como a Busca de Custo Uniforme (só custo), a Busca Subida do Morro (só heurística) e a Busca A* (custo + heurística).

A linguagem Java tem estruturas de dados que facilitam muitíssimo a implementação desse tipo de fila, entre elas as classes Stack, Queue, HashMap e TreeSet, que podem ser muito úteis. A classe TreeSet, por exemplo, permite fornecer em seu construtor um objeto "comparador", de forma a permitir que você construa a sua própria fila prioritária.

Observação: na literatura, essa fila prioritária é geralmente chamada de "fronteira" de busca (porque armazena os nós que são o limite da fronteira, que é continuamente expandida conforme a busca se desenrola).

4

A navegação encontrada na página da Wikipédia utiliza recursividade.

public void emOrdem(ArvoreNo no) {
  if(no != null) {
      emOrdem(no.getNoE());
      System.out.print(no.getInfo()+" ");
      emOrdem(no.getNoD());
  }
}

Exemplo:

arvore
(fonte: uol.com.br)

No caso, eles acessam o lado esquerdo continuamente até sua limitação. Ao atingir o limite do lado esquerdo, ele acessa o direito do nó.

No caso dos acessos:

A, B, D, H -> I -> E, J -> K...

H não possui nós filhos. Ele realiza a chamada "emOrdem(no.getNoE());", quando chamar e não tiver filhos, o método não realizaram mais nada, "if(no != null)", voltando ao pai e continuando o fluxo normal, passando por "System.out.print(no.getInfo()+" ");" e voltando para o acesso do lado direito "emOrdem(no.getNoD());".

O segredo está na recursividade. Espero que tenha esclarecido o funcionamento! Boa Sorte!

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .