Heuristica
1417 palavras
6 páginas
Busca com InformaçãoFunçã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 um nodo 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 Inteligentes
Busca 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
161
Fagaras
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
329