CITS3011 - Lab 3 Informed Search

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.

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.

A* Search

A* search is a search algorithm that finds the shortest and cheapest path between a starting node and end node. It combines actual distance travelled with a smart guess of the distance remaining, known as a heuristic function.

$f(n)=g(n)+h(n)$

$f(n)$ is the total cost of the path from our current node to the end node. $g(n)$ is the exact cost from the start node to our current node. $h(n)$ is a heuristic estimate of the cost from the current node to the final goal.

By using this equation, A* search algorithms can lean towards the target making it faster and more accurate than other search algorithms.