Supongamos que quiero cambiar la lógica en A *, intentando encontrar la ruta más útil (es decir, la que tiene la mayor ganancia) en lugar de encontrar la ruta más corta (es decir, la que tiene el costo más bajo).

En mi caso, un objetivo no se fija como un nodo final único. Un nodo se define como cualquier nodo que tenga distanciaB desde el punto de partida.

En la versión de vainilla ("encontrar el camino más corto") se me exige que no sobreestime el costo (es decir, que encuentre una heurística que sea menor o igual que el costo real).

En mi versión modificada ("encontrar la ruta más útil"), los bordes se etiquetan con la utilidad y no con el costo, y quiero maximizar la ganancia final, dada la restricción de pasar porun máximo de bordes B. ¿Debo sobrestimar la utilidad (es decir, encontrar una heurística que sea mayor o igual a la utilidad real) para hacer que A * funcione?

EDITAR: Mas formalizado, vamos

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

Ser la utilidad de un nodo, compuesta por:

g(n): lo que gano al pasar del nodo de inicio anh(n): la heurística, es decir, una estimación de lo que gano cuando voy den a la meta (donde la meta es un nodo cuya distancia desde el punto de inicio esB)

Deberíah(n) ser sobreestimado yf(n) ¿Ser maximizado para identificar el mejor camino?

Darse cuenta deB es un presupuesto, y por lo tanto se puede gastar completamente, es decir, no es necesario encontrar una ruta que sea más corta queB pasos.