Beating a greedy algo

For class we have a grid and a bunch of squares on the grid that we need to detect and travel to. We start at (0,0). We scan tiny regions of the grid at a time (for reasons regarding our data structure it's mandatory), and when we detect squares that we need to travel, and then we travel. There are 32 locations on the grid, but we only need to travel 16 of them, and as fast as possible (we're racing someone else to them).

Dijkstra's algo would find the shortest path from our current location to our next location. This is sub-optimal however, because our next location may be really far from the location after that. It would be more beneficial if we could somehow figure out the density of locations as we scan, and then choose to go to a very dense place and travel all the开发者_如何学JAVA locations within that area.

Is there an algorithm best suited for a situation like this? I know the greedy heuristic isn't optimal. A* and Dijkstra's are the ones we thought about at first but we are hoping there's a completely different solution.

PS this is being done in assembly, unfortunately.

Finding dense clumps of points (e.g. locations you have to visit) is called cluster analysis. See the link for several classes of algorithms.

Assembly language is a really painful way to experiment with high-level algorithms. Is your prof a sadist??