# Prove consistency of maximum of two consistent heuristic functions?

Suppose we have two heuristic functions $h_1$ and $h_2$ which are both consistent, that is,

$$h_i(n) \leq c(n,a,n') + h_i(n')\qquad \ i\in\{1,2\}\,,$$

where $c(n,a,n')$ denotes cost of reaching the successor node $n'$ with action $a$. Can we conclude that the $h_3:=\max(h_1,h_2)$ is also consistent?

• What did you try? Where did you get stuck? We're happy to help with conceptual issues but just solving homework-style exercises for you is unlikely to really help you. – David Richerby Oct 21 '16 at 13:58

Proof (Show consistency property of $h_3$):
$$h_3(n) = \max(h_1(n), h_2(n)) \\ \leq max(h_1(n')+c(n,a,n'), \ h_2(n')+c(n,a,n')) \\ \leq \max(h_1(n'), \ h_2(n')) + c(n,a,n') = h_3(n') + c(n,a,n')$$