A search problem and no algorithm for it
Your description is a bit vague, but the problem you describe seems very similar to the canonical problem defining the complexity class PLS (http://en.wikipedia.org/wiki/PLS_(complexity)). Problems in PLS can be described by an exponentially sized graph that you have access to using two polynomial time algorithms: one for evaluating the weight of a current vertex, and one for directing you to the neighbors of a current vertex. The goal is to find a local-minimum in the graph: any vertex such that none of its neighbors have lower weight. 

Complete problems for this class include computing pure strategy Nash equilibria in congestion games (See e.g. here), and no polynomial time algorithms for such problems are known.