Is Harmonic Mean of admissible heuristics an admissible heuristic?

Question

Given a family of admissible heuristic functions h1, h2, .. hn.  Is the Harmonic Mean, H = n / (1/h1 + 1/h2 + ... 1/hn) an admissible function?  How would you define this function if one of the h functions is zero?

Answer 1

Hi Professor Arora,

I think it is. Firstly, when we talk about Harmonic Mean, we have assumed that all heuristic functions are not equal to 0, otherwise they can't be denominators. Then, after we have this assumption, Harmonic Mean is obviously admissible. 

Proof:

1. For all h_i in {h₁, ... , h_n}, h_i <= C^*, where C^* is the fact cost (this is the definition of admissibility).
2. Since h_i <= C^*, we have 1 / h_i >= 1 / C^* for all h_i not equal to 0.
3. By 2, we get 1 / h₁ + ... + 1 / h_n >= n / C^*.
4. Multiply C^* / (1 / h₁ + ... + 1 / h_n) on both sizes, we have C^* >= n / (1 / h₁ + ... + 1 / h_n), i.e. H <= C^*.

Q.E.D.