<p>Yes, in both cases. Below I give two very simple proofs that directly follow from the definitions of admissible and consistent heuristics. However, in a nutshell, the idea of the proofs is that <span class="math-container">$h_{\max}(n)$</span> and <span class="math-container">$h_{\min}(n)$</span> are, <strong>by definition</strong> (of <span class="math-container">$h_{\max}$</span> and <span class="math-container">$h_{\min}$</span>), equal to one of the given admissible (or consistent) heuristics, for all nodes <span class="math-container">$n$</span>, so <span class="math-container">$h_{\max}(n)$</span> and <span class="math-container">$h_{\min}(n)$</span> are consequently admissible (or consistent).</p>

<h2>Definitions</h2>

<p>Consider the graph <span class="math-container">$G=(V, E, \mathcal{G})$</span> representing the search space, where <span class="math-container">$V$</span>, <span class="math-container">$E$</span> and <span class="math-container">$\mathcal{G} \subseteq V$</span> are respectively the set of nodes, edges and goal nodes, and the function <span class="math-container">$w\colon E \times E \rightarrow \mathbb{R}$</span>, which gives you the cost of each edge <span class="math-container">$e = (u, v) \in E$</span>, where <span class="math-container">$u, v \in V$</span>, that is, <span class="math-container">$w(e) = w(u, v) \in \mathbb{R}$</span> is the cost of the edge <span class="math-container">$e$</span>.</p>

<p>A heuristic <span class="math-container">$h$</span> is admissible if <span class="math-container">$$h(n) \leq h^*(n), \forall n \in V,$$</span>
where <span class="math-container">$h^*(n)$</span> is the optimal cost to reach a goal from node <span class="math-container">$n$</span> (that is, it is the optimal heuristic).</p>

<p>On the other hand, a heuristic <span class="math-container">$h$</span> is consistent if</p>

<p><span class="math-container">\begin{align}
h(n) &amp;\leq w(n, s) + h(s), \forall n \in V \setminus \mathcal{G}, \text{ and} \\
h(n) &amp;= 0, \forall n \in \mathcal{G},
\end{align}</span>
where <span class="math-container">$s$</span> is a successor of <span class="math-container">$n$</span>.</p>

<h2>Theorem 1</h2>

<p>Given a set of admissible heuristics <span class="math-container">$H = \{ h_1, \dots, h_N \}$</span>, then, for every <span class="math-container">$n \in V$</span>, the heuristics <span class="math-container">$h_{\max}(n) = \max(h_1(n), \dots, h_N(n))$</span> and <span class="math-container">$h_{\min}(n) = \min(h_1(n), \dots, h_N(n))$</span> are also admissible.</p>

<h3>Proof</h3>

<p>Given that, <span class="math-container">$h_i(n) \leq h^*(n), \forall n \in V$</span> and <span class="math-container">$\forall i \in \{ 1, \dots N \}$</span>, then <span class="math-container">$h_{\max}(n) = h_j(n) \leq h^*(n)$</span> (for some <span class="math-container">$j \in \{ 1, \dots N \}$</span>)  and <span class="math-container">$h_{\min}(n) = h_k(n) \leq h^*(n)$</span> (for some <span class="math-container">$k \in \{ 1, \dots N \}$</span>), so <span class="math-container">$h_{\max}$</span> and <span class="math-container">$h_{\min}$</span> are also admissible.</p>

<p><span class="math-container">$\tag*{$\blacksquare$}$</span></p>

<h2>Theorem 2</h2>

<p>Given a set of consistent heuristics <span class="math-container">$H = \{ h_1, \dots, h_N \}$</span>, then, for every <span class="math-container">$n \in V$</span>, the heuristics <span class="math-container">$h_{\max}(n) = \max(h_1(n), \dots, h_N(n))$</span> and <span class="math-container">$h_{\min}(n) = \min(h_1(n), \dots, h_N(n))$</span> are also consistent.</p>

<h3>Proof</h3>

<p>Given that, for every <span class="math-container">$i \in \{ 1, \dots, N \}$</span>, </p>

<p><span class="math-container">\begin{align}
\begin{cases}
h_i(n) \leq w(n, s) + h_i(s), &amp; \text{ if }  n \in V \setminus \mathcal{G}\\
h_i(n) = 0, &amp; \text{ if }  n \in \mathcal{G}
\end{cases}
\end{align}</span></p>

<p>then, if <span class="math-container">$n \in V \setminus \mathcal{G}$</span>, <span class="math-container">$h_{\max}(n) = h_j(n) \leq w(n, s) + h_j(s)$</span>, for some <span class="math-container">$j \in \{1, \dots, N \}$</span>, and, similarly, <span class="math-container">$h_{\min}(n) = h_k(n) \leq w(n, s) + h_{k}(s)$</span>, for some <span class="math-container">$k \in \{1, \dots, N \}$</span>. Similarly, if <span class="math-container">$n \in \mathcal{G}$</span>, <span class="math-container">$h_{\max}(n) = h_{\min}(n) = h_i(n) = 0, \forall i \in \{1, \dots, N \} $</span>. Thus, <span class="math-container">$h_{\max}$</span> and <span class="math-container">$h_{\min}$</span> are also consistent.</p>

<p><span class="math-container">$\tag*{$\blacksquare$}$</span></p>

<h2>Notes</h2>

<p><span class="math-container">$h_{\max}$</span> and <span class="math-container">$h_{\min}$</span> have been defined in the only possible reasonable way, because, given two (admissible or consistent) heuristics, <a href="https://ai.stackexchange.com/q/15701/2444">one may not always dominate the other (or vice-versa)</a>, even if both are admissible and consistent.</p>

CC BY-SA 4.0
2021-10-21T01:10:56.670Z
When you say "hmax(n)=hj(n)≤w(n,s)+hj(s), for some j∈{1,…,N}", aren't you implicity assuming nodes n and s both using ith heuristic, but this may not be the case. What you need to show is "hmax(n) = hi(n) ≤ w(n, s) + hj(s), for some i,j ∈{1,…,N}" or am I mistaken?
unlut
CC BY-SA 4.0
2019-11-11T15:07:38.460Z
2019-11-11T17:03:57.083Z
2019-11-11T17:03:57.083Z
nbro
<p>Let's suppose I have a set of heuristics <span class="math-container">$H$</span> = {<span class="math-container">$h_1, h_2, ..., h_N$</span>}.</p>

<ol>
<li><p>If all heuristics in <span class="math-container">$H$</span> are <strong>admissible</strong>, does that mean that a heuristic that takes the <span class="math-container">$\min(H)$</span> (or <span class="math-container">$\max(H)$</span> for that matter) is also admissible?</p></li>
<li><p>If all heuristics in <span class="math-container">$H$</span> are <strong>consistent</strong>, does that mean that a heuristic that takes the <span class="math-container">$\min(H)$</span> (or <span class="math-container">$max(H)$</span> for that matter) is also consistent?</p></li>
</ol>

<p>I'm thinking about a search problem in a bi-dimensional grid that every iteration of an algorithm, the agent will have to find a different goal. Therefore, depending on the goal node, a certain heuristic can possibly better guide the agent than the others (hence the use of <span class="math-container">$\min$</span> and <span class="math-container">$\max$</span>).</p>

<search><proofs><heuristics><admissible-heuristic><consistent-heuristic>
Is the minimum and maximum of a set of admissible and consistent heuristics also consistent and admissible?
ihavenoidea
# Is the minimum and maximum of a set of admissible and consistent heuristics also consistent and admissible?

(Asked by: username_0 on 2019-04-10)

Let's suppose I have a set of heuristics $H$ = {$h\_1, h\_2, ..., h\_N$}.

1. If all heuristics in $H$ are **admissible**, does that mean that a heuristic that takes the $\min(H)$ (or $\max(H)$ for that matter) is also admissible?
2. If all heuristics in $H$ are **consistent**, does that mean that a heuristic that takes the $\min(H)$ (or $max(H)$ for that matter) is also consistent?

I'm thinking about a search problem in a bi-dimensional grid that every iteration of an algorithm, the agent will have to find a different goal. Therefore, depending on the goal node, a certain heuristic can possibly better guide the agent than the others (hence the use of $\min$ and $\max$).

**Tags:** search, proofs, heuristics, admissible-heuristic, consistent-heuristic


---

## 1 answers

### Answer by username_1 on 2019-11-11. Score: 2 | Accepted answer

Yes, in both cases. Below I give two very simple proofs that directly follow from the definitions of admissible and consistent heuristics. However, in a nutshell, the idea of the proofs is that $h\_{\max}(n)$ and $h\_{\min}(n)$ are, **by definition** (of $h\_{\max}$ and $h\_{\min}$), equal to one of the given admissible (or consistent) heuristics, for all nodes $n$, so $h\_{\max}(n)$ and $h\_{\min}(n)$ are consequently admissible (or consistent).

## Definitions

Consider the graph $G=(V, E, \mathcal{G})$ representing the search space, where $V$, $E$ and $\mathcal{G} \subseteq V$ are respectively the set of nodes, edges and goal nodes, and the function $w\colon E \times E \rightarrow \mathbb{R}$, which gives you the cost of each edge $e = (u, v) \in E$, where $u, v \in V$, that is, $w(e) = w(u, v) \in \mathbb{R}$ is the cost of the edge $e$.

A heuristic $h$ is admissible if $$h(n) \leq h^\*(n), \forall n \in V,$$
where $h^\*(n)$ is the optimal cost to reach a goal from node $n$ (that is, it is the optimal heuristic).

On the other hand, a heuristic $h$ is consistent if

\begin{align}
h(n) &\leq w(n, s) + h(s), \forall n \in V \setminus \mathcal{G}, \text{ and} \\
h(n) &= 0, \forall n \in \mathcal{G},
\end{align}
where $s$ is a successor of $n$.

## Theorem 1

Given a set of admissible heuristics $H = \{ h\_1, \dots, h\_N \}$, then, for every $n \in V$, the heuristics $h\_{\max}(n) = \max(h\_1(n), \dots, h\_N(n))$ and $h\_{\min}(n) = \min(h\_1(n), \dots, h\_N(n))$ are also admissible.

### Proof

Given that, $h\_i(n) \leq h^\*(n), \forall n \in V$ and $\forall i \in \{ 1, \dots N \}$, then $h\_{\max}(n) = h\_j(n) \leq h^\*(n)$ (for some $j \in \{ 1, \dots N \}$) and $h\_{\min}(n) = h\_k(n) \leq h^\*(n)$ (for some $k \in \{ 1, \dots N \}$), so $h\_{\max}$ and $h\_{\min}$ are also admissible.

$\tag\*{$\blacksquare$}$

## Theorem 2

Given a set of consistent heuristics $H = \{ h\_1, \dots, h\_N \}$, then, for every $n \in V$, the heuristics $h\_{\max}(n) = \max(h\_1(n), \dots, h\_N(n))$ and $h\_{\min}(n) = \min(h\_1(n), \dots, h\_N(n))$ are also consistent.

### Proof

Given that, for every $i \in \{ 1, \dots, N \}$,

\begin{align}
\begin{cases}
h\_i(n) \leq w(n, s) + h\_i(s), & \text{ if } n \in V \setminus \mathcal{G}\\
h\_i(n) = 0, & \text{ if } n \in \mathcal{G}
\end{cases}
\end{align}

then, if $n \in V \setminus \mathcal{G}$, $h\_{\max}(n) = h\_j(n) \leq w(n, s) + h\_j(s)$, for some $j \in \{1, \dots, N \}$, and, similarly, $h\_{\min}(n) = h\_k(n) \leq w(n, s) + h\_{k}(s)$, for some $k \in \{1, \dots, N \}$. Similarly, if $n \in \mathcal{G}$, $h\_{\max}(n) = h\_{\min}(n) = h\_i(n) = 0, \forall i \in \{1, \dots, N \} $. Thus, $h\_{\max}$ and $h\_{\min}$ are also consistent.

$\tag\*{$\blacksquare$}$

## Notes

$h\_{\max}$ and $h\_{\min}$ have been defined in the only possible reasonable way, because, given two (admissible or consistent) heuristics, [one may not always dominate the other (or vice-versa)](https://ai.stackexchange.com/q/15701/2444), even if both are admissible and consistent.

> **Comments:**
> **username_2**: When you say "hmax(n)=hj(n)≤w(n,s)+hj(s), for some j∈{1,…,N}", aren't you implicity assuming nodes n and s both using ith heuristic, but this may not be the case. What you need to show is "hmax(n) = hi(n) ≤ w(n, s) + hj(s), for some i,j ∈{1,…,N}" or am I mistaken?  

---

