Aula 04 Busca Com Informa O I

Páginas: 5 (1177 palavras) Publicado: 28 de maio de 2015
Inteligência Artificial
Aula 04 – Busca com informação ou
heurística

Métodos de busca
!  Busca Cega ou Exaustiva:
–  Não sabe qual o melhor nó da fronteira a ser expandido. Apenas
distingue o estado objetivo dos não objetivos.

•  Busca Heurística:
–  Estima qual o melhor nó da fronteira a ser expandido com base em
funções heurísticas.

•  Busca Local:
–  Operam em um único estado e movem-separa a vizinhança deste
estado.

Busca com informação
(ou heurística)
•  Utiliza conhecimento específico sobre o problema para
encontrar soluções de forma mais eficiente do que a
busca cega.
–  Conhecimento específico além da definição do problema.

•  Abordagem geral: busca pela melhor escolha.
–  Utiliza uma função de avaliação para cada nó.
–  Expande o nó que tem a função de avaliação maisbaixa.
–  Dependendo da função de avaliação, a estratégia de
busca muda.

Busca Heurística
•  Como encontrar um barco perdido?
–  Busca Cega -> Procura no oceano inteiro.
–  Busca Heurística -> Procura utilizando informações
relativas ao problema.
•  Exemplo: correntes marítimas, vento, etc.

Busca Heurística
•  Função Heurística (h)
–  Estima o custo do caminho mais barato do estado atual até oestado final mais próximo.
–  São específicas para cada problema.

•  Exemplo:
–  Encontrar a rota mais curta entre duas cidades:
•  h(n) = distância

Busca Heurística
•  Algoritmos de Busca Heurística:
–  Busca Gulosa (ou Busca Gulosa pela melhor escolha)
–  A*

Busca Gulosa
•  Estratégia:
–  Expande os nós que se encontram mais próximos do
objetivo (uma linha reta conectando os dois pontos nocaso de distancias), desta maneira é provável que a busca
encontre uma solução rapidamente.

•  A implementação do algoritmo se assemelha ao utilizado
na busca cega, entretanto utiliza-se uma função
heurística para decidir qual o nó deve ser expandido.
•  Função de avaliação f(n) = h(n) (heurística) = estimativa
do custo de n até o objetivo

Busca Gulosa
•  Exemplo:

Busca Gulosa

Arad

366Mehadia

241

Bucharest

0

Neamt

234

Craiova

160

Oradea

380

Arad

Drobeta

242

Pitesti

100

366

Eforie

161

Rimnicu
Vilcea

193

Fagaras

176

Sibiu

253

Giurgiu

77

Timisoara

329

Iasi

226

Vaslui

199

Lugoj

244

Zerind

374

Hirsova

151

Urziceni

80

•  Exemplo:

Arad
366

Sibiu

Timissoara

Zerind

253

329

374

Fagaras
176

Sibiu

Bucharest

263

0

Distância em linha reta paraBucareste

Oradea

Rimnicu Vilcea

380

193

Busca Gulosa
•  Custo de busca mínimo:
–  No exemplo, não expande nós fora do caminho.

•  Não é ótima:
–  No exemplo, escolhe o caminho que é mais econômico à primeira
vista, via Fagaras.
–  Porém, existe um caminho mais curto via Rimnicu Vilcea.

•  Não é completa:
–  Pode entrar em loop se não detectar a expansão de estados
repetidos.
–  Pode tentardesenvolver um caminho infinito.
–  Minimizar h(n) é suscetível a falsos inícios.
•  Ex. Ir de Iasi a Fagaras
•  Heurística sugerirá ir a Neamt, que é um beco sem saída.
•  Se repetições não forem detectadas a busca entrará em loop.

Busca Gulosa
•  Exemplo:

Busca A*
•  Estratégia:
–  Combina o custo do caminho g(n) com o valor da heurística
h(n)
–  g(n) = custo do caminho do nó inicial até onó n
–  h(n) = valor da heurística do nó n até um nó objetivo (distancia
em linha reta no caso de distancias espaciais)
–  f(n) = g(n) + h(n)

•  É a técnica de busca mais utilizada.

Busca A*
Arad
0+366=366

Sibiu
140+253=393

Arad

Timissoara
118+329=447

75+374=449

Oradea

Rimnicu Vilcea

Arad

366

Mehadia

241

291+380=671

220+193=413

Bucharest

0

Neamt

234

Craiova

160

Oradea

380Drobeta

242

Pitesti

100

Eforie

161

Rimnicu Vilcea

193

Fagaras

176

Sibiu

253

Giurgiu

77

Timisoara

329

Iasi

226

Vaslui

199

Lugoj

244

Zerind

374

Hirsova

151

Urziceni

80

Fagaras

280+366=646 239+176=415

Zerind

Sibiu

Bucharest

Craiova

338+253=591

450+0=450

366+160=526

Bucharest
418+0=418

Pitesti
317+100=417

Sibiu

300+253=553

Craiova

Rimnicu Vilcea

455+160=615...
Ler documento completo

Por favor, assinar para o acesso.

Estes textos também podem ser interessantes

  • Aula Atividade 04 Sistema De Informa O
  • DE I Aula 04 08 14
  • 04 Unidade I Aula 06 Adm
  • Aula 04 Transforma Es Geom Trocas I
  • Plano de Aula 04 Direito Constitucional I
  • Aula 04
  • Aula 04
  • Aula de 04

Seja um membro do Trabalhos Feitos

CADASTRE-SE AGORA!