How to formulate a best-search algorithm limited by a count of nodes visited?

The problem

I'm doing a search by computer program. Each node takes about 5 minutes of wall time to get a result so I'm looking to carefully choose the nodes to inspect so as to find the best result possible within the limited number of inspections available. A brute force approach will take far too long so we'll settle for somethings like "here's 1 million inspections - do the best you can with it for now".

The result of each inspection is numeric and can be fed back into deciding which node to look at next; ranging from pick a node within the same cell which is "close" or "far" to this one, or pick a cell close or far to this one (and a node within it); or just pick a cell and node at random. Whatever we like.

The Search Table

The search is laid out as table 1400 x 1400 where each cell contains (15 x 5)$^{2}$ x 2 x 2 = 11,250 nodes, the merit of each node is determined by the compute. It's expected that the results of nodes near each other inside the same cell will return results close to one another. Each cell in a row is tenuously related to the proximity of its neighbour cells within the same row. But there is no relationship whatsoever between each column and its immediate or distant neighbours.

Other influences

As an aside, there is some small bias toward doing full inspections of a single cell (all 11250 nodes) since it has a byproduct: we'll permanently store the best one (best 100 more likely), discard the rest, and thereafter be content to exempt that cell from all subsequent searches. I'm not sure how much this consideration should influence the search algorithm since if you're only given 10000 nodes to inspect then we don't want to waste it all on one cell, but if we have a million knocking off a few complete cells would have long-term value.

ideas to date

Well actually searching the whole table is still too much for me to handle. I'm still trying get a hold of searching one row. The idea for which is to spend the first 1400 inspections taking a sample from each cell. Then discarding the worst x number of them, and sampling a second node from each of those cells and repeating this sample/discard cycle until no more inspections remain. The trick there was working out how many to discard with each cycle? And thus was born this question: I'm perhaps not the best person to be attempting to solve this problem.

Anyone? Thanks for reading. Hope you can help.

-