1
$\begingroup$

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?

$\endgroup$
1
  • 1
    $\begingroup$ 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. $\endgroup$ Oct 21 '16 at 13:58
3
$\begingroup$

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') $$

$\endgroup$
2
  • 1
    $\begingroup$ This seems to be correct but please consider that you might have just done somebody's homework for them. $\endgroup$ Oct 21 '16 at 13:59
  • $\begingroup$ @DavidRicherby Based on your assumption we shouldn't answer any question here:( We should answer any question here because we couldn't find out if a question is a homework or not. Anyone is responsible for his duty:) $\endgroup$
    – milad
    Jul 28 at 5:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.