Suponha que eu queira alterar a lógica em A *, tentando encontrar o caminho mais útil (isto é, aquele com o maior ganho) em vez de encontrar o caminho mais curto (isto é, aquele com o menor custo).

No meu caso, uma meta não é fixada como um nó final exclusivo. Um nó é definido como qualquer nó que tenha distânciaB do ponto de partida.

Na versão baunilha ("encontrar o caminho mais curto"), é necessário não superestimar o custo (ou seja, encontrar uma heurística que seja menor ou igual ao custo real).

Na minha versão modificada ("encontrar o caminho mais útil"), bordas são marcadas com o utilitário e não com o custo, e eu quero maximizar o ganho final, dada a restrição de passar porum máximo de arestas B. Devo superestimar a utilidade (ou seja, encontrar uma heurística que seja maior ou igual à utilidade real) para que o A * funcione?

EDITAR: Mais formalizado, vamos

f(n) = g(n) + h(n)

ser o utilitário de um nó, composto por:

g(n): o que ganho ao passar do nó inicial paranh(n): a heurística, ou seja, uma estimativa do que ganho quando vou den para o objetivo (onde o objetivo é um nó cuja distância do ponto de partida éB)

Devemosh(n) ser superestimada ef(n) ser maximizado para identificar o melhor caminho?

Notar queB é um orçamento e, portanto, pode ser gasto completamente, ou seja, não é necessário encontrar um caminho menor queB passos.