Inteligência Artificial - Resolução de problemas através de busca

[Música] o [Música] bem vindos a segunda aula do nosso curso de inteligência artificial na aula de hoje a gente vai falar de uso de busca técnicas de busca para a resolução de problemas estão na aula passada a gente viu que pra definir o que é um problema eu preciso dizer qual o estado inicial quais são as ações qual o teste de objetivo então como que eu sei que eu resolvi o problema e definir qual custo que eu quero minimizar na hora de resolver esse problema então o que é uma solução é o a solução dá

pra resolver o problema é a seqüência de ações que eu tenho que fazer para chegar do estado inicial até o estado final ou um estado o que é o estado final é um estado objetivo estado que satisfaz o teste de objetivo que a gente definiu então o exemplo que eu dei uma passada de ida do trabalho para casa o que eu vou fazer é pensar que o teste objetivo é se era do trabalho para casa o teste objetivo é eu chegar em casa ou se é dona de casa para o trabalho o objetivo é chegar

no trabalho e uma solução ótima é uma solução de menor custo eu estou falando de estado inicial estado final estado o objetivo que é esse o que são esses estados a gente tem um espaço de estados que são todos os estados que eu consigo acessar a partir do inicial cada estado uma representação do que eu tenho como se fosse uma representação do mundo que eu estou tratando naquele instante esses estados eles vão mudando conforme eu aplico ações neles então a gente pode pensar nisso como sendo um grafo neste gráfico a gente tem em cada estado

representado por nós e os arcos são ações então eu aplico mação a por exemplo de pegar um ônibus da minha casa até o trabalho e eu me movo de um estado inicial e estou em casa até um estado do trabalho era o que eu posso ter várias acções passando por vários estados então essa idéia de ter um espaço de estados representados ea gente tem que pensar que esses estados são alterações do mundo real então eu não vou e colocar cada detalhe do mundo nesse exemplo do caminho de casa até o trabalho que eu vou representar

no estado a posição em que eu tô posso representar a posição de forma discreta o a posição exata dada por um gps tudo isso eu vou ter que definir é depende do trabalho que eu vou fazer eu vou querer minimizar a distância pode ser que queira saber a distância exata se eu quero só pensar em tempo talvez eu não preciso de tantos detalhes sobre a a a minha posição então vamos ver aqui um exemplo é o exemplo que que tem no livro que eu vou deixar mais detalhes pra vocês a gente tem aqui um exemplo

muito simples que é um problema de um aspirador de pó e ele pode estar em duas posições diferentes então se a gente olhar um estado aqui é dado por as duas posições e o fato de se tem sujeira né então esse daqui a sujeira se eu tenho sujeira ou não nessas posições e além disso é preciso saber se o aspirador está na posição na primeira posição ou na outra posição o que são as ações possíveis o aspirador ele pode se mover de um lado para o outro então se a gente olhar que a gente está

num estado se o aspirador se move para a direita então essa é a sanção r ela move para a direita no próximo estado o inspirado por a sujeira continua no mesmo lugar e o aspirador se moveu desse estado se eu morrer pra esquerda como ele já está na posição mais à esquerda ele fica no mesmo estado que é dado por esse laço aqui ea outra a terceira ação possível é aspirar então eu estou nesse estado e faço ação de expirar o que acontece a posição onde o robô estava agora tá limpa onde tinha sujeira não

tem mais então se a gente pensar nessa representação de estados a gente tem oito estados possíveis então seriam quatro estados possíveis de sujeira ou não sujeira na posição imposição 2 e isso x 2 porque o robô pode tar à direita ou à esquerda ea gente consegue fazer esse grafo que eu gravo doné do meu espaço de estados mostrando como cada ação muda leva de um estado no outro nesse caso como é que a gente fez a representação do problema a gente tem os estados são dados pela posição do robô e pelo fato de ter ou

não sujeira a gente tem como estado inicial qualquer um eu posso começar de qualquer situação as ações são e pela esquerda pra direita e aspirar e o meu objetivo é ter as duas posições limpas então como é que vai ser o meu teste e verificam se as duas posições estão limpas custo aqui a gente não tá muito preocupado então a gente pode dizer que o custo é um a cada passo que isso significa significa que cada ação tem um custo então a melhor solução é o que faz a limpeza e menor é menor número de

passos então não vale a pena ficar indo e voltando para o mesmo lugar sem aspirar porque eu só vou aumentar o custo sem chegar mais perto do objetivo a gente pode pensar em vários exemplos então por exemplo o problema das oito rainhas que é muito abordado em computação para um problema complexo consiste em colocar oito rainhas num tabuleiro de xadrez sem que um ataque a outra a rainha ela ataca todo mundo que está na mesma coluna na mesma linha e na diagonal então não é trivial encontrar uma configuração para as rainhas no tabuleiro a questão

aqui é o meu objetivo é ter 8 rainhas colocado no tabuleiro de modo que elas não se ataquem essa daqui não é uma solução que a gente tem aqui uma imposição de ataque então a gente pode pensar como é que a gente vai formular esse problema a gente pode pensar nos estados cada estado é um tabuleiro com um certo número de rainhas colocado em posições quaisquer o estado inicial o tabuleiro está em branco e a gente tem como ação colocar mais uma rainha nesse tabuleiro qual é o objetivo é eu tenho oito rainhas 0 ataques

entre elas nesse caso o que a gente tem aqui de possibilidades para colocar a primeira rainha tenho 64 posições possíveis no tabuleiro para colocar a segunda tenho 63 é que eu vou diminuindo porque não posso colocar na mesma posição que estava outra e assim por diante que no final eu tenho 3 10 a 14 possibilidades de estados para examiná mas a gente é isso é com essa formulação do problema a gente pode pensar em um jeito os mais inteligentes de representar o problema então uma outra formulação é que um estado não é um qualquer número

de rainhas em qualquer posição do tabuleiro o estado é dado por um certo número de rainhas nas primeiras colunas do tabuleiro porquê porque eu sei que aqui entre o conhecimento do problema não posso ter duas rainhas na mesma coluna então se eu já tenho uma rainha naquela coluna eu vou passar para próxima então a gente vai colocando as rainhas coluna por coluna vai preenchendo e nesse caso é as ações possíveis são colocar uma rainha na próxima coluna vazia ou seja eu tenho só que escolher a linha então em vez de 64 possibilidade eu tenho oito

cada ação e vou ter oito possibilita e na verdade menos do que oito porque eu quero que não tem ataque então já elimina algumas posições algumas linhas onde já tem uma rainha nesse caso em vez de 10 a 14 estados possíveis eu posso ter dois mil estágios possíveis então é usar um pouco do conhecimento que a gente tem sobre o problema para formular melhor o espaço de estados reduzir reduz bastante o que eu vou ter que fazer o esforço que eu vou ter que fazer para encontrar uma posição uma uma solução para esse problema ea

gente vai ver agora como procurar soluções a gente vai procurar soluções baseado na idéia de busca em árvore que é a busca do jeito que é feita na na disciplina de estrutura de dados a gente tem uma árvore com todas as possibilidades então no caso do aspirador a gente pensa é o comércio no estado inicial é a raiz da árvore e eu vou desenvolvendo de acordo com as ações possíveis os ramos então no caso do aspirador eu tenho um estado possível é o aspirador aksu já que isso joaquim e aí eu tenho sempre três ações

possíveis que é e para a direita e para a esquerda e aspirar e com isso a gente vai construindo a nossa árvore de busca o que a gente vai trabalhar a gente tem na área de busca a gente vai sempre ter uma idéia de uma fronteira que são os nós que a gente ainda tem que expandir nossa que ainda não foram explorados e no início esse é o nó inicial o estado inicial do problema ea gente tem uma função que vai criando novos nós na árvore que vai expandir indo então para cada estado vai aplicar

as ações que são possíveis para chegarem novos estados e com isso a gente vai criando novos nós na árvore a ideia geral de busca ganhar queria que a gente pega a gente tem sempre a fronteira aguardando quais os nós para serem expandidos a gente tira o primeiro nova fronteira se ela tiver vazia kaboul não encontrem uma solução quando a gente tirou nota fronteira gente testa se ele é uma solução se lhes satisfaz o teste de objetivo a gente já encontrou uma solução se ele não satisfaz eu vou expandir esse nó então a expansão vai gerar

todos os nossos sucessores aplicando a vacina homens e aí esses novos nós eles são inseridos na fronteira ea gente volta para o passo 1 essa idéia o algoritmo básico de busca em árvore o que varia suas estratégias de busca que a gente vai usar para percorrer essa árvore de busca ea estratégia depende da ordem que a gente expande os nós ou da ordem que a gente coloca na fronteira pra eles serem retirados não vou falar sobre a busca em largura em profundidade ea gente tem duas variações da busca em profundidade que são profundidade limitada eo

aprofundamento interativo a busca lá na busca de largura né em todas elas é na busca e orgulho que a gente tem aqui é a avaliação da estratégia então os nós eles vão ser expandidos na ordem em que eles são criados então se eu tiver aqui meu espaço e minha árvore é o comércio no estado inicial e aí a gente vai expandiu 0 os dois nós b e c o primeiro nó que eu vou expandir é o bebê que foi o primeiro foi criado eu vou gerar odeio então os nós que tão brancos aqui o cd

e eles são os nós que estão na fronteira e da fronteira eu não vou agora desenvolveu d ou e mas eu vou olhar para o séc foi expandido foi colocado na fronteira antes do que odeio é quais são as características do uso da busca de largura para resolver um problema essa busca é completa então se eu tenho um número finito de ações eu sempre vou encontrar a solução ela é ótima 'nesse se cadastram tem custo um ela sempre vai encontrar o menor o caminho mais curto para a solução mas ela tem um problema que é

para implementar essa busca a gente tem que manter todos os nós na memória e isso é fica inviável conforme o problema cresce a busca em profundidade e muda a estratégia em vez de expandir o primeiro nokia foi criado a gente expande o último nó que foi criado que a idéia de armazenar essa fronteira como se fosse uma pilha então a gente tem a busca em largura usa uma fila então o primeiro que entra é o primeiro que sai a busca em profundidade uma pilha último que entrou na fronteira é o primeiro a ser expandido então

no caso da busca em profundidade o que acontece no início eu expandido o noir votei aqui o beijos e aí eu vou expandir b e agora em vez de prosseguir como eu estava indo na busca em largura a gente vai expandir aqui o de e aí vai continuar expandindo aqui pelo h então a gente vai percorrendo um ramo da árvore ao invés de ir seguindo em níveis e só depois que eu chego no fim que não tem uma ação é que eu vou para os outros ramos o que acontece com a música em profundidade é

que ela não é completa mesmo que o espaço de estado seja finito um ramo pode ser infinito se a gente pensar naquele espaço pequeno do aspirador de pó ele ficava ele podia ficar indo de um lado para o outro e isso causa um laço infinito então um ramo infinito ele vai para a direita vai para a esquerda ou para a direita vai para a esquerda e eu não saio nunca daquele ramo então esse é um problema sério da busca em profundidade e claro mesmo que encontre uma solução não é ótima não necessariamente a gente vai

encontrar o caminho menor custo que a gente vai você vai ser o primeiro caminho que ia para o primeiro estado objetivo que aparecer na no desenvolvimento da árvore não necessariamente o menos profundo mais uma grande vantagem é que a gente não precisa armazenar e memória todos os nós e sim só os nós do caminho que está sendo seguido e isso faz muita diferença em termos de de implementação então surgiram algumas com a busca em largura ela tem a vantagem de ser completa isso é ótima mas ela tem o problema de que é o o conforme

o problema cresce há há há ela começa a ficar inviável por causa de memória então surgiram algumas idéias para melhorar a busca em profundidade tenta usar o fato de que ela usa menos memória e uma idéia é colocar um limite na busca em profundidade então vou descendo pelos ramos até um certo nível se eu chegar naquele limite não tiver uma solução eu acho como é que se não tivesse um nosso sucessor como se eu não tivesse como continuar descendo eu paro ali não não posso aplicar nenhuma ação e volta e vou investigar outro ramo então

isso faz com que não seja mas não tenha mais problema de ramos infinitos mais claro eu posso é perder uma solução porque eu vou descendo pela vida chega uma hora eu paro vou para outro ramo e podia ser que a solução tivesse lá embaixo a outra possibilidade que aí vai usar a idéia da profundidade limitada mas melhorando um pouco é a repetir essa busca limitada só que aumentando o valor do l então a gente vai combinar vantagens da busca em profundidade com a busca em largura como eu vou aumentando a profundidade aos poucos eu tenho

essa idéia da busca em largura que se eu tiver uma solução se eu tiver um duelo igual a 3 existe uma solução de custo 3 vou encontrar se eu tiver não é igual a quatro não tiver custo 4 vou encontrar só que de cada vez eu só vou fazer uma busca em profundidade e isso faz com que eu não tenha é o problema da memória que tem a busca em largura então só para ter uma idéia a gente começa pensando no limite zero então eu tenho meu nosso país e eu vou olhar se ele é

um objetivo depois eu tenho limite um então eu tenho um nível de profundidade aqui e eu vou fazer buscas só até ali eu não achei a solução que eu faço aumentou para o limite dois estão no limite 2 eu faço toda uma busca em profundidade só que parando no nível 2 e assim por diante o juiz pode fazer no nível 3 e vai aumentando que a gente tem aqui com essa busca de profundidade interativa ou aprofundamento interativo essa busca é completa então da mesma forma que a busca em largura se existe um número finito de

ações eu vou sempre encontrar a solução para algum ele não sei qual sim as ações têm custo ou seja qualquer ação tem o mesmo custo eu vou sempre encontrar a melhor solução porque como a gente vai fazendo o aprofundamento interativo é como a busca em largura vai investigar cada vez um nível da árvore então sempre vai encontrar a solução mais próxima da raiz ea vantagem é que na verdade a cada passo a cada para cada valor gelli a gente está fazendo uma busca em profundidade então não tem o problema de guardar todos os nós a

gente guarda só o caminho atual na próxima aula eu vou continuar falando de busca para como método de resolução de problemas mas a gente vai acrescentar a questão de é que a gente fala de heurística de conhecimento sobre o problema para melhorar essa busca para não fazer o que a gente viu nessa aula é chamado de busca cega eu vou procurando todas as possibilidades na próxima aula a gente vai prosseguir com a busca com heurísticas em que a gente usa a informação sobre o problema pra diminuir o número de estados expandidos então até lá [Música]

o [Música] [Música]