Scribd Logo
Carregar

Bem-vindo(a) ao Scribd!

  • 22 visualizações

    Inteligência Artificial: Resolução de Problemas Através de Busca

    Enviado por

    Rogerio Alexander Macedo
    O documento descreve técnicas de busca para resolução de problemas usadas em inteligência artificial, incluindo busca em largura, profundidade e profundidade iterativa. Problemas como o aspirador de pó e rainhas são usados como exemplos para ilustrar os conceitos.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd

    Inteligência Artificial: Resolução de Problemas Através de Busca

    Enviado por

    Rogerio Alexander Macedo
    22 visualizações37 páginas
    O documento descreve técnicas de busca para resolução de problemas usadas em inteligência artificial, incluindo busca em largura, profundidade e profundidade iterativa. Problemas como o aspirador de pó e rainhas são usados como exemplos para ilustrar os conceitos.

    Título original

    Untitled

    Direitos autorais

    © © All Rights Reserved

    Formatos disponíveis

    PDF, TXT ou leia online no Scribd

    Você considera este documento útil?

    Este conteúdo é inapropriado?

    O documento descreve técnicas de busca para resolução de problemas usadas em inteligência artificial, incluindo busca em largura, profundidade e profundidade iterativa. Problemas como o aspirador de pó e rainhas são usados como exemplos para ilustrar os conceitos.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd
    Fazer download em pdf ou txt
    22 visualizações37 páginas

    Inteligência Artificial: Resolução de Problemas Através de Busca

    Enviado por

    Rogerio Alexander Macedo
    O documento descreve técnicas de busca para resolução de problemas usadas em inteligência artificial, incluindo busca em largura, profundidade e profundidade iterativa. Problemas como o aspirador de pó e rainhas são usados como exemplos para ilustrar os conceitos.

    Direitos autorais:

    © All Rights Reserved
    Baixe no formato PDF, TXT ou leia online no Scribd
    Fazer download em pdf ou txt
    Você está na página 1de 37

    INTELIGÊNCIA ARTIFICIAL

    Resolução de Problemas
    através de Busca
    PROBLEMA
    Estado Inicial

    Ações

    Teste de Objetivo

    Custo
    PROBLEMAS
    Solução: sequência de ações que levam
    de um estado inicial a um objetivo.

    Solução ótima: solução de custo mínimo


    ESPAÇO DE ESTADOS

    O conjunto de todos os estados


    acessíveis a partir de um estado
    inicial é chamado de espaço de
    estados.
    ESPAÇO DE ESTADOS
    O espaço de estados pode ser
    interpretado como um grafo em que
    os nós são estados e os arcos são
    ações.
    ESPAÇO DE ESTADOS
    Abstração do mundo real.

    Exemplo: Caminho de casa até o


    trabalho. Estados dados pela posição
    exata ou discretizados?
    EXEMPLO (Aspirador de Pó)
    EXEMPLO (Aspirador de Pó)
    • Estados: Posição do robô e sujeira (8)
    • Estado inicial: Qualquer um
    • Ações: esquerda (L), direita (R),
    aspirar(S)
    • Teste de objetivo: todas as posições
    estão limpas?
    • Custo do caminho: 1 cada passo
    EXEMPLO (8 rainhas)
    EXEMPLO (8 rainhas)
    • Estados: Qualquer disposição de 0 a 8
    rainhas
    • Estado inicial: Nenhuma rainha
    • Ações: colocar mais uma rainha
    • Teste de objetivo: 8 rainhas, 0 ataques
    64x63x...57 = 3x1014 possibilidades!
    EXEMPLO (8 rainhas)
    • Estados: n rainhas nas n primeiras
    colunas, sem ataque
    • Ações: colocar uma rainha na próxima
    coluna, sem ataque.
    2.057 estados possíveis
    BUSCA EM ÁRVORE
    Fronteira: nós a serem expandidos
    (começa com o estado inicial)
    A função Expande cria novos nós,
    usando as ações aplicáveis para gerar
    os estados correspondentes.
    BUSCA EM ÁRVORE
    1. Retira o primeiro nó da fronteira (falha
    se vazia)
    2. Testa se é um estado final (solução):
    se for, devolve nó, sucesso
    3. Expande nó;
    4. Insere os nós gerados na fronteira e
    volta para o passo 1
    ESTRATÉGIAS DE BUSCA
    A estratégia usada define a ordem
    em que os nós são expandidos, ou
    seja, retirados da fronteira.
    BUSCA CEGA (não informada)
    ● Em Largura
    ● Em Profundidade
    ● Profundidade Limitada
    ● Aprofundamento Iterativo
    BUSCA EM LARGURA

    Nós são expandidos na ordem em


    que foram criados.
    BUSCA EM LARGURA
    BUSCA EM LARGURA
    BUSCA EM LARGURA
    BUSCA EM LARGURA
    • Completa Se número de ações é finito
    • Ótima Se ações tem custo 1

    • Espaço mantém todos os nós na


    memória...
    BUSCA EM PROFUNDIDADE

    O último nó criado é o primeiro a


    ser expandido.
    BUSCA EM PROFUNDIDADE
    BUSCA EM PROFUNDIDADE
    BUSCA EM PROFUNDIDADE
    BUSCA EM PROFUNDIDADE
    BUSCA EM PROFUNDIDADE
    BUSCA EM PROFUNDIDADE
    BUSCA EM PROFUNDIDADE
    • Não é Completa (ramo pode ser
    infinito)
    • Não é ótima (encontra a primeira
    solução e não a de menor custo)

    Mas: só guarda nós do caminho atual!


    PROFUNDIDADE LIMITADA
    Coloca um limite l na busca em
    profundidade. Nós de profundidade
    l são considerados como terminais.
    PROFUNDIDADE ITERATIVA
    Repete a busca com profundidade
    limitada para valores de l cada vez
    maiores.
    Combina vantagens da busca em
    profundidade com a busca em
    largura!
    PROFUNDIDADE ITERATIVA
    PROFUNDIDADE ITERATIVA
    PROFUNDIDADE ITERATIVA
    PROFUNDIDADE ITERATIVA
    PROFUNDIDADE ITERATIVA
    • Completa Se número de ações é finito
    • Ótima Se ações tem custo 1

    • Espaço mantém apenas o caminho


    atual na memória!
    PROFUNDIDADE ITERATIVA
    Repete a busca com profundidade
    limitada para valores de l cada vez
    maiores.
    Combina vantagens da busca em
    profundidade com a busca em
    largura!
    INTELIGÊNCIA ARTIFICIAL

    Resolução de Problemas
    através de Busca

    Você também pode gostar