fig hill climbing search of maze the maze we can employ the manhattan distance as heuristic to guide us towards the goal we don' know the length of the path that will lead to the solution since we don' know all the details of the mazebut we can estimate the distance from where we are to the goal if we know the location of the goal and our current location the manhattan distance is measure of the number of rows and columns that separate any two locations on maze or map in fig the manhattan distance from the start to the goal is we have to go down one rowthen right columnsand down rows this distance is called the manhattan distance because it would be like walking between buildings in manhattan or city blocks in any city the manhattan distance would be either exact or an under-estimate of the total distance to the goal in fig it is an exact estimatebut in general direct route to the goal may not be possible in which case the manhattan distance would be an under-estimate this is important because over-estimating the distance will mean that hill climbing will end up working like depth first search again the heuristic would not affect the performance of the algorithm for instanceif we took the easy approach and said that our distance was always from the goalhill climbing would not really occur the example in fig shows that the algorithm chooses to go down first if possible then it goes right the goal location is known and the minimum manhattan distance orders the choices to be explored going left or up is not an option unless nothing else is available so the algorithm proceeds down and to the right until it reaches step where it has no choice on this path but to go up hill climbing performs like depth first search in that it won' give up on path until it reaches dead end while hill climbing does not find the optimal solution in fig it does find solution and examines far fewer locations in this case than breadth first or depth first search the advantages and disadvantages of hill climbing are as follows this copy belongs to 'acha