title: Hill Climbing non global maximum with Manhattan Distance
body: <p>Consider a shortest-path finding problem, such that the shortest path from <code>green</code> to <code>red</code> must be found. For this, I would like to use the Hill Climbing approach and using the Manhattan Distance as my heuristics. I calculated some of those distances already as you can see. Moreover, there are walls where <code>green</code> cannot pass through.
  <a href="https://i.stack.imgur.com/C8nz4m.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/C8nz4m.png" alt="enter image description here" /></a></p>
  <p>In this scenario, the agent <code>green</code> would go the field which has a MD of <code>3</code>, and after that the algorithm would already end. We did not arrive at the global maximum or the best possible solution. Now, I am looking for a scenario, where the Hill Climbing approach, given the Manhattan Distance as the heuristic and the path finding problem as described, where the agent actually finds a path, which is NOT globally optimal. I could not come up with any example, which I guess cannot be the case.</p>