Problem $3.$ Local Search

File Preview

An ant is searching for food. The intensity of the nectar's scent is given in the matrix

cells. Ant is at location $(1,1)$ and the nectar is at location $(4,4).$ The ant can move

horizontally, vertically and diagonally. There are obstructions in three cells where ant

can not go$.$ The cells are $(2,1),(3,3)$ and $(4,1).$ Draw the tree for possible movements,

and the best path taken by ant assuming that ant can sense the smell upto only one cell

beyond. For example, at $(1,1),$ she can sense the smell in $(1,2),(2,1),$ and $(2,2).$

$4$

$3$

$2$

$1$