Heuristica

Disponível somente no TrabalhosFeitos
  • Páginas : 6 (1417 palavras )
  • Download(s) : 0
  • Publicado : 1 de outubro de 2012
Ler documento completo
Amostra do texto
Busca com Informação

Função Heurística

Métodos de busca sem informação podem
ser (são) bem ineficientes
Se houver algum conhecimento maior sobre
o problema que possa ser utilizado, a busca
pode ser muito mais eficiente
“Best”-First search

De forma geral, a função heurística fornece
uma indicação do melhor caminho para a
solução
h(n) é o custo estimado do melhor caminho
de umnodo n até o gol
h(gol) = 0

Exemplos

o nodo a ser expandido e escolhido de acordo
com uma função de avaliação f(n)
Expande-se o nodo com menor f(n)
Em geral, f(n) usa alguma heurística
Agentes Inteligentes

Romênia: distância direta entre cidades
8-Puzzle: número de quadrados fora de posição

Prof. Luiz Chaimowicz

Agentes Inteligentes

Busca Gulosa (Greedy)

Busca Gulosa –Exemplo

Expande o nodo que está mais próximo do
gol de acordo com a função heurística

Viagem na Romênia
Queremos achar um caminho (o melhor
caminho) entre Arad e Bucarest

f(n) = h(n)

O termo “gulosa” significa que o método
procura reduzir o custo imediato para
alcançar o objetivo na expansão de cada nó,
porém sem se preocupar com o custo total
do caminho

Agentes InteligentesBusca Gulosa – Exemplo

Prof. Luiz Chaimowicz

A heurística usada é a distância em linha
reta entre as cidades

Prof. Luiz Chaimowicz

Arad
Bucharest

Agentes Inteligentes

366

Prof. Luiz Chaimowicz

Busca Gulosa – Exemplo

Arad
Bucharest

0

366
0

Craiova

160

Craiova

160

Dobreta

242

Dobreta

242

Eforie

161

Fagaras

176

Eforie

161Fagaras

176

Giurgiu

77

Hirsova

151

Arad
366

Giurgiu

77

Hirsova

151

Iasi

226

Iasi

226

Lugoj

244

Lugoj

244

Mehadia

241

Mehadia

241

Neamt

234

Neamt

234

Oradea

380

Oradea

380

Pitesti

100

Pitesti

100

Rimnicu V.

193

Rimnicu V.

193

Sibiu

Sibiu

253

329

Timisoara

329Urziceni

80

Urziceni

80

Vaslui

199

Vaslui

199

Zerind

Agentes Inteligentes

253

Timisoara

374

Zerind

374

Prof. Luiz Chaimowicz

Agentes Inteligentes

Prof. Luiz Chaimowicz

1

Busca Gulosa – Exemplo

Arad
Bucharest

366

Busca Gulosa – Exemplo

0

Arad
Bucharest

366
0

Craiova

160

Craiova

160

Dobreta

242

Dobreta242

Eforie

161

Fagaras

176

Eforie

161

Fagaras

176

Giurgiu

77

Giurgiu

77

Hirsova

Arad

151

Hirsova

151

Arad

329

253

374

Iasi

226

Iasi

226

244

Lugoj

244

241

Mehadia

241

Neamt

234

Neamt

234

380
100

Rimnicu V.

Zerind

Lugoj

Pitesti

Timisoara

Mehadia

Oradea

Sibiu

193Sibiu

Timisoara

Zerind

Arad

Fagaras

Oradea

Rimnicu V.

Oradea

380

Pitesti

100

366

176

380

193

Rimnicu V.

193

Sibiu

Sibiu

253

329

Timisoara

329

Urziceni

80

Urziceni

80

Vaslui

199

Vaslui

199

Zerind

Agentes Inteligentes

253

Timisoara

374

Zerind

374

Prof. Luiz Chaimowicz

Busca Gulosa –Exemplo

Arad
Bucharest

Agentes Inteligentes

366

Busca Gulosa – Exemplo

160

Dobreta

242

Eforie

161

Fagaras

Arad
Bucharest

0

Craiova

Arad

Prof. Luiz Chaimowicz

176

366
0

Craiova

160

Dobreta

242

Eforie

161

Fagaras

176

Giurgiu

Sibiu

Timisoara

Zerind

77

Giurgiu

77

Hirsova

151

Hirsova

151Iasi

226

Iasi

226

Fagaras

Oradea

Rimnicu V.

244

Lugoj

244

241

Mehadia

241

Neamt

Arad

Lugoj
Mehadia

234

Neamt

234

Oradea

380

Oradea

380

Sibiu

Bucharest

253

0

Pitesti

100

Pitesti

100

Rimnicu V.

193

Rimnicu V.

193

Sibiu

253

Sibiu

253

Timisoara

329

Timisoara

329

80...
tracking img