A* search proof

---

(a) Prove that optimal heuristics (i.e. \(h^*(n)\)) are consistent

To show that optimal heuristics are consistent,

I need to show two things:

\[\begin{align} &h^*(G) = 0 &&\text {for goal node G} \tag 1\\ &h^*(n) \leq cost(n, n') + h(n') \tag 2\\ \end{align}\]

I am already at the goal state, so the cost to reach the goal from the goal is 0. This satisfies the first condition.

now I am considering \(h^*(n) \leq cost(n, n') + h^*(n')\)

If \(h^*(n) \gt cost(n, n') + h^*(n')\), then it implies that there is a path (n -> n’ -> G), which is less than \(h^*(n)\).

This contradicts the assumption that \(h^*(n)\) is the optimal heuristic.

---

(b) Prove: If \(h_1(n), ..., h_k(n)\) are admissible, so is \(h(n) = max(h_1(n), ..., h_k(n))\)

\(h(n) = max(h_1(n), ..., h_k(n))\) is admissible if the following condition is satisfied:

\[\forall n\ h(n) \leq h^*(n)\]

Because each of \(h_1(n), ..., h_k(n)\) is admissible, I can write:

\[\forall n\ h_i(n) \leq h^*(n)\ \text{where i} \in [1, k]\]

If this is true, I can write:

\[\forall n\ h(n) = max(h_1(n), ..., h_k(n)) \leq h^*(n)\]

Thus, the maximum of admissible heuristics is admissible.

---

(c) Prove: If \(h_1(n), ..., h_k(n)\) are consistent, so is \(h(n) = max(h_1(n), ..., h_k(n))\)

\(h(n) = max(h_1(n), ..., h_k(n))\) is consistent if the following condition is satisfied:

\[\forall n\ h(n) \leq cost(n, n') + h(n')\]

Because each of \(h_1(n), ..., h_k(n)\) is consistent, I can write:

\[\forall n\ h_i(n) \leq cost(n, n') + h_i(n')\ \text{where i} \in [1, k]\]

If this is true, I can write:

\[\forall n\ h(n) = max(h_1(n), ..., h_k(n)) \leq cost(n, n') + max(h_1(n'), ..., h_k(n'))\]

Because the maximum of consistent heuristics is consistent, I can write:

\[\forall n\ h(n) \leq cost(n, n') + h(n')\]

Thus, the maximum of consistent heuristics is consistent.

---

(d) Prove or disprove: If \(h_1(n), ..., h_k(n)\) are admissible, so is \(h(n) = h_1(n) + ... + h_k(n)\)

Because each of \(h_1(n), ..., h_k(n)\) is admissible, I can write:

\[\forall n\ h_i(n) \le h^*(n)\ \text{where i} \in [1, k]\]

Adding all admissible heuristics together, I can write:

\[\forall n\ h(n) = h_1(n) + ... + h_k(n) \le k \cdot h^*(n)\]

When \(k = 1\), \(h(n) = h_1(n)\), which is admissible.

When \(k \gt 1\), \(h(n) = h_1(n) + ... + h_k(n)\) is not necessarily admissible.

When \(k \gt 1\), \(h(n)\) can be greater than \(h^*(n)\).

I would have this equation:

\[h(n) = h_1(n) + ... + h_k(n) \le k \cdot h^*(n)\]

This shows that \(h(n) \le k \cdot h^*(n)\), but it does not show that \(h(n) \le h^*(n)\).

---

(e) Prove or disprove: If \(h_1(n), ..., h_k(n)\) are admissible, so is \(h(n) = \frac{(h_1(n) + ... + h_k(n))}{k}\)

Because each of \(h_1(n), ..., h_k(n)\) is admissible, I can write:

\[\forall n\ h_i(n) \le h^*(n)\ \text{where i} \in [1, k]\] \[\forall n\ \frac{(h_1(n) + ... + h_k(n))}{k} \le \frac{k \cdot h^*(n)}{k}\] \[\forall n\ \frac{(h_1(n) + ... + h_k(n))}{k} \le h^*(n)\]

Thus, \(h(n) = \frac{(h_1(n) + ... + h_k(n))}{k}\) is admissible.