Please enable JavaScript.
Coggle requires JavaScript to display documents.
Heuristica, Tirado da soma da reta euclidiana, Detalhes - Coggle Diagram
Heuristica
Função da h(.)
utilizando busca guiada
Usa a busca gulosa
Busca do melhor-primeiro (Best-First Search).
custo deve ser admissível
Cria um custo estimado
Calcular as coordenas e a distancia em linha reta dos vértices n até o vértice de solução
latitude e longitude - geodesia
Busca gulosa não é otima, e as vezes pode nem ter resposta. :warning:
caso a condição de não retorno a vértices visitados esteja habilitado.
custo real
se sub-estima o custo real :red_cross:
se super-estima o custo real :check:
Leva em consideração o custo aparente que falta para a solução
Qual a ideia?
:red_flag:
Associar alguma informação adicional para ajudar a expansão do próximo vértice
Funcionamento:
:warning:
visita o estado inicial
aplica a função de teste objetivo
verifica a ocorrencia de filhos
:red_flag:Não são considera os valores reais
Considera os valor da soma da reta
Soma os valores reais do menor caminho
do caminho do percurso tirado pela soma
Conceito
O que é h(.)
Estimar algo, para resolver um problema
Juntar sequências de passos
denotada pela h(.) a função de Heuristica
o h(n) não deve ser negativa
h(n) = 0, se n é a solução
Busca A*
Conceito:
Melhoria na h(.)
Estima o menor custo do real do problema
A busca A* é ótima se a heurística for admissível
nunca super-estimar o custo total , então o
procedimento é completo e ótima
A* é completo em grafos localmente finitos
Como funciona?
Custo já executado + o estimado
f (n) = g(n) + h(n)
Expande primeiro o vértice com o menor valor de f(·).
do calculo de f (n) = g(n) + h(n)
Funcionamento
:warning:
Usa a função de avaliaçao = f(n) = g(n) + h(n)
onde g(n) é o custo de chegada do no atual para o incial.
h(n) é o valor heuristico
ou o valor da soma da reta
verifica se e o estado objetivo (a chegada)
verifica a ocorrencia de filhos
aplica a função de avaliaçao dos filhos
repete, e quanta o custo dos caminhos
Combina a eficiência da busca gulosa com a completude da busca em largura.
Tirado da soma da reta euclidiana
Detalhes