Inteligência Artificial - Material de Apoio

Estratégias de busca sem informação

Busca em largura: Expandir em sequência até atingir o objetivo. Dependendo do nosso cenário é necessário avaliar se a busca é satisfatória.

Ela traz uma complexidade definida da seguinte forma: O quanto de Nós eu vou ter que expandir, e quanto será a profundidade, quanto eu gastaria e a memória que vou precisar.

Busca de custo uniforme: Expande o nó com o custo de caminho mais baixo, vai chegar no objetivo porém com um percurso diferente, onde o foco é o custo mais baixo.

Busca em profundidade: Sempre vai expandir o nó mais profundo na borda atual.

Não expande em sequência e sim quem está abaixo, ou seja, expande em nível.

É uma busca completa, mantém todos os passos e é ótima se todas as ações tiverem o mesmo custo.

Busca em profundidade limitada

Uma opção que pode melhorar esse tipo de busca é limitando o nível de busca, para evitar que você se aprofunde demais, principalmente em nó que não tenha fim, fazendo com que a busca demora para ir ao outro nível

Não é completa pois a solução pode estar além do limite.

Busca de aprofundamento interativo:

Ele irá fazer um aumento gradual até encontrar o objetivo. É uma busca completa e completa a solução do problema.

Busca bidirecional: A busca se inicia ao mesmo tempo a partir do estado inicial e do estado final

O ideal é ter um problema que você já tem uma solução, desta forma começo dos dois pontos. Do problema à solução e do solução até o problema, desmontando. Quando os dois pontos se encontrarem implica que o problema foi encontrado.

A tendência é que eu consiga encurtar o gasto e tempo em 50%.

Estado repetidos: O processo de busca pode perder muito tempo expandindo nós já explorados antes.

Podem levar a loops infinitos e transformar problema linear em problema exponencial caucionando mais tempo e mais custo.

Para tentar fugir o ideal é colocar uma regra para nunca voltar a um passo para trás e ao estado pai.

Não gerar qualquer estado que já tenha sido criado antes e requerer que todos os estados gerados permaneçam na memória, porém não é uma opção muito barato.

Estratégias de busca sem informação

Utiliza conhecimento especifico sobre o problema para encontrar solução de forma mais eficiente do que a busca cega.

É uma busca pela melhor escolha, expande o nó que tem a função mais baixa.

Busca gulosa de melhor escolha: Tenta abrir o nó que está mais próxima do objetivo. Ele faz a busca com os dados na mãos para encontrar o problema, e dessa forma encontrar a melhor solução.

Quer sempre o melhor (Gulosa). Não é uma busca completa porque pode acontecer dela ficar no lucro, pode encontra dois nível com o peso, ela vai ficar olhando para os dois que são igual e não vai