Busca Exaustiva

Links Interessantes

  • Artificial Intelligence Search Techniques in Java by Mark Watson
  • Uninformed Search Applets created by Naomi Novik BFS, DFS, Depth-Limited Search and Iterative Deepening Search
  • Scramble Puzzle by Michael J. Quinn BFS and DFS applied to a scramble puzzle (applet)
  • Vladimir Kulyukin's Search Implementation A solution to the classic problem about missionaries and cannibals in Common Lisp (include IDS). Ajustes para funcionar com o problema do Vasilhame (Thiago Galves Moretto - Eng. Comp. - UCDB)

    Algoritmo Básico

    Fronteira <- { Estado Inicial }
    Enquanto True
        Se não tem o que expandir Então Retorna Falha
        No <- Retira_Um( Fronteira )
        Se chegou em Estado Meta Então Retorna Solução
        Senão  Fronteira <- Fronteira + Expande(No) 

    Conceitos Auxiliares

  • Detecção de Ciclos
  • Fator de Ramificação (Branching Factor).

    • Busca Exaustiva (Uninformed Search)

  • Não usa qualquer informação relacionada com a "distância" entre o estado corrente e o estado meta.


    		•  Largura Custo Uniforme
    (Dijkstra)    		 Profundidade Profundidade
    Limitada    		 Aprofundamento
    Iterativo

    		Breadth-First Uniform-Cost Depth-First Limited Depth-
    First    		 Iterative
    Deepening
    Tempo bd bd bm bl bd
    Espaço bd bd bm bl bd
    Melhor Solução sim sim nao nao sim
    Completude sim sim no sim, l >= d sim

    d  - Produndidade da solução encontrada
    m - Altura da árvore
    b  - Fator de Ramificação (Branching Factor)
    l   - Limite da Busca

    Exemplo Comparativo

    Profundidade Total de Nós Tempo Memória (Larg.) Memória (Prof.)
    0 1 1 ms 100 b 100 b
    2 111 .1 s 11 kb 2 kb
    4 11.111 11 s 1 Mb 4 kb
    6 10^6 18 min 111 Mb 6 kb
    8 10^8 31 h 11 Gb 8 kb
    10 10^10 128 dias 1 Tb 10 kb
    12 10^12 35 anos 111 Tb 12 kb
    14 10^14 3500 anos 11.111 Tb 14 kb

    Fator de Ramificação = 10
    Capacidade de Processamento: 1000 nós/segundo
    Tamanho do Nó = 100 bytes