0

Currently I have found that there is an article in which a search problem is posed and to solve it a heuristic is proposed which, in essence, is the solution of the problem itself. I seem to remember that in search problems based on heuristics (e.g. A*) there was an impediment by which you should not pose too good heuristics, since you generated a kind of dependence on solving the problem before using the algorithm.

Does this phenomenon have any formal theory behind it, and does it have any specific name?

Angelo
  • 201
  • 2
  • 16
  • Which article are you referring to exactly? It would be great that you provide more context (e.g. quotes from articles where this is claimed). – nbro Dec 11 '22 at 12:58
  • @nbro It is a Google article called Data Valuation using Reinforcement Learning. They use the score of training data with the model trained on validation, which can be easily proved to be the target of the search problem itself. Anyway, do you know how can I get to some theorem/statement which explains this phenomenon? – Angelo Dec 14 '22 at 08:26
  • It's not fully clear to me what you mean by "you generated a kind of dependence on solving the problem". Can you clarify that? In A*, there are heuristics $h(n)$ that overestimate or underestimate the weight/length of the path from a node $n$ to the goal. A heuristic that never overestimates (so it underestimates or estimates correctly) the path from $n$ to the goal is called [_admissible_](https://en.wikipedia.org/wiki/Admissible_heuristic), and A* with admissible heuristics is guaranteed to find an optimal solution. I don't know if this is related to what you're asking or not. – nbro Dec 14 '22 at 09:25
  • @nbro By generating a dependency on solving the problem I mean that if your heuristic is directly the solution, it makes no sense to pose a search problem, and even if you pose it you would need to solve the problem to obtain the heuristic that would allow you to "solve" the problem with the search algorithm. I am indeed looking for a term like "admissible" as you comment, but just in the case where the heuristic is the perfect solution to the problem. – Angelo Dec 14 '22 at 11:05
  • Creating an admissible heuristic doesn't require you to solve the problem (e.g. you can just have an non-informed heuristic, i.e. $h(n) = 0$, for all $n$ - it's admissible). However, creating a perfect heuristic, i.e. the heuristic that tells you the exact length from $n$ to the goal, probably does. – nbro Dec 14 '22 at 12:34

0 Answers0