Heuristic Function

A heuristic function estimates the remaining cost/distance/effort needed to reach a final goal from any node. It allows software to make fast decisions by making an educated guess on which paths are likely to be more efficient.
$h(n)=\text{estimated cost from n to goal}$

$h(n)$ is also known as forward cost.

A heuristic function is specific for any given problem and will require you needing to design it. For example, a heuristic function for a word ladder problem where, given a start word, find the smallest amount of changes to reach an end word using words from a given dictionary, would look like:

def heuristic(word, end_word):
    count = 0
    for i in range(len(word)):
        if word[i] != end_word[i]:
            count += 1
    return count

From any node (i.e. any given word we are examining), we can calculate the minimum number of letter changes needed to reach the end word. This would be equal to the number of letters that are different between our current word and end word.

---

Manhattan Distances

Manhattan distance is a metric that measures the distance between two points by summing the absolute differences between their coordinates.

Distance is calculated by moving only horizontally and vertically.

---

Admissible vs Consistent Heuristics

Admissible: $h(n)\le h^{\ast }(n)$ where $h^{\ast }(n)$ is actual cost from $n$ to goal -> $h(n)$ never overestimates for all $n$.

Consistent (monotonic): $h(n)\le c(n,a,n^{\prime })+h(n^{\prime })$, where $n’$ is a successor to $n$ by action $a$ -> estimated cost between nodes never decreases by more than actual step cost between them.

Every consistent heuristic is admissible, but not vice versa

---

Deriving Heuristics

There are two general strategies for determining a heuristic:

1. Relaxed problem — remove constraints
2. Sub-problems — solve part of the problem and cache costs

A relaxed problem is a simplification of your initial problem with lowered constraints. There can be multiple relaxed problems which can all give different heuristics.

For example, using the 8-puzzle above, we could allow tiles to be picked up and placed anywhere on the grid ($h_1=$ number of misplaced tiles) -> $h_1=8$.

Alternatively, we could allow tiles to be overlayed on top of each other when being moved ($h_2$ = the sum of Manhattan distances of tiles from goals) -> $h_2=18$.

These simplified problems will give us an underestimate (therefore admissible) heuristic. The closer a heuristic estimate is to the true cost, the more effective the A* search.

Sub-Problems

Sub-problems involve breaking down a larger problem, finding the exact cost of solving a smaller sub-problem, and then caching the cost.

For example, using the 8-puzzle above, the sub-problem could be trying to only move 1, 2, 3, 4 to the goal positions.

---

Assessing Heuristics

Quality of a heuristic can be expressed as its effective branching factor $b^{\ast }$, which can be determined empirically. The closer $b^{\ast }$ is to $1$, the better the heuristic.

Assuming A* visits $N$ nodes and finds solution at depth $d$:
$N=1+b^{\ast }+(b^{\ast }{)}^2+\dots +(b^{\ast }{)}^d=\frac{(b^{\ast }{)}^{d+1}-1}{b^{\ast }-1}$

We can approximate the effective branching factor for larger values of $b^{\ast }$:
$b^{\ast }\approx N^{1/d}$

Dominant Heuristics

A heuristic $h_2$ dominates a heuristic $h_1$ if, for every state $n$:

$h_2(n)\ge h_1(n)$

• Provided both heuristic are admissible.

$h_2$ is a strictly better heuristic than $h_1$.

If you have two admissible heuristic, but neither dominates the other, you can use both instead (at the cost of more computational power used):
$h(n)=\max (h_1(n),h_2(n))$

---

await dv.view("Scripts/topic-backlinks");