Example: Consider the $8-$puzzle problem, where the initial state is

and the goal state is

Explore the problem by considering the followings.

$($a$)$ brute force search

$($b$)$ "Tiles out of place" heuristic

$($c$)$ "Sum of distances out of place" heuristic

$($d$)"2x$ number of direct tile reversal" heuristic

$($e$)$ "Sum of distances out of place and $2x$ number of direct tile reversal" heuristic

Example: We are given $5$ cities $A,B,C,D,$ and $E.$ We are also given the distance between two cities

$($please see the graph below$).$ A salesman is in city A and wants to visit all cities and then come back to

the original city A$.$ The problem is to find the path that has least distance. Explore the problem by

considering the followings.

$($a$)$ brute$-$force search

$($b$)$ nearest neighbor.

$($Note that the nearest neighbor heuristic is an example of hill climbing strategy$).$