02 - busca

Prévia do material em texto

Inteligência Artificial
Busca
Yuri Malheiros 

(yuri@dce.ufpb.br)
Introdução
• Dadas muitas opções, qual a escolha correta para solução de um 
problema? 
• Qual a melhor rota para chegar numa cidade?
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
Introdução
• Como ir de João Pessoa até Cajazeiras?
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
Introdução
• Solução: 
• Uma sequência de ações para sair de um estado inicial para um 
objetivo
Definição de um problema
• Estado inicial: o agente está na cidade de João Pessoa 
• Ações(s) -> {a1, a2, a3, ...}: dado o estado atual (s), quais cidades o 
agente pode ir em seguida 
• Resultado(s, a) -> s’: dado que o agente está em (s) e é escolhida a 
ação (a), então o estado do agente será estar (s’) 
• TesteDeObjetivo(s) -> True | False: testa se o estado (s) é o objetivo 
• Custo(s, a, s’) -> n: o custo para ir de (s) até (s’) usando a ação (a)
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo estado intermediário ações fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo estado intermediário ações fronteira
Explorado
Não 

Explorado
Tree Search
• Vamos definir uma função para resolver o problema de busca num 
espaço de estados 
• Transformaremos os estados numa árvore
def tree_search(self): 
 frontier = [self.initial] 
!
 while True: 
 if len(frontier) == 0: return False 
 new_state = self.remove_choice(frontier) 
 if new_state in self.goals: return new_state 
!
 for action in new_state.actions: 
 frontier.append(action) 
def tree_search(self): 
 frontier = [self.initial] 
!
 while True: 
 if len(frontier) == 0: return False 
 new_state = self.remove_choice(frontier) 
 if new_state in self.goals: return new_state 
!
 for action in new_state.actions: 
 frontier.append(action) 
Tree Search
• Qual a ação devemos escolher? 
• Existem diferentes algoritmos que fazem escolhas diferentes
Busca em largura
• Qual a ação devemos escolher? 
• Primeiro o caminho mais curto que estiver na fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo nó expandido açõescaminho escolhido
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo nó expandido açõescaminho escolhido
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo nó expandido açõescaminho escolhido
Busca em largura
• É redundante expandir o nó de João Pessoa novamente 
• Mas numa busca em árvore isso não é exatamente uma volta ao 
mesmo nó
João 
Pessoa
Campina 

Grande
Santa 

Rita Itabaiana
ItabaianaJoão 
Pessoa Coxixola SoledadeAreia
João 
Pessoa
Campina 

Grande
Santa 

Rita Itabaiana
ItabaianaJoão 
Pessoa Coxixola SoledadeAreia
Busca em largura
• Implementação…
Busca em largura
• Guardando os nós já explorados é possível evitar expansões 
desnecessárias
João 
Pessoa
Campina 

Grande
Santa 

Rita Itabaiana
ItabaianaJoão 
Pessoa Coxixola SoledadeAreia
João 
Pessoa
Campina 

Grande
Santa 

Rita Itabaiana
Coxixola SoledadeAreia
Graph Search
• Vamos modificar a função Tree Search 
• Caminhos repetidos devem ser evitados
def graph_search(self): 
 explored = set() 
 frontier = [initial] 
!
 while True: 
 if len(frontier) == 0: return False 
 new_state = self.remove_choice(frontier) 
!
 explored.add(new_state) 
 if new_state in self.goals: return new_state 
!
 for action in new_state.actions: 
 if not action.state in explored: 
 frontier.append(action) 
Busca em largura
• Vamos fazer o passo a passo do algoritmo de busca em largura 
usando o graph search
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areiaitabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
estado inicial objetivo explorado fronteira
Busca em largura
• A busca em largura encontrará o caminho com o menor número de 
passos 
• Mas não necessariamente o caminho de menor custo
monteiro
coxixola
soledade
campina 

grande
picuí
guarabira
areia
itabaiana
joão

pessoa
santa rita
mamanguape
patos
itaporanga
sousa
cajazeiras
catolé 

do rocha
pombal
o caminho verde é

mais curto que o azul
Busca em largura
• Próxima aula veremos como fazer isso