I would like to learn about the following search problem, in particular, which kind of algorithms exist for it.
Suppose we have a huge search space $S$. For each element $s \in S$, we have the weight function $w(s)$. We start at some element $s_0 \in S$ and want to find an element with very low $w$-value.
How can we traverse this search space? For each element $s_1 \in S$, there exists a set of keys $K_S$, and we have some function $a : S \times K_S \rightarrow S$, that computes a new element $s_2 = a(s_1,k)$ for some $k \in K_S$.
We can evaluate the weight of some element $s$ only once it is given. But computing the weight is expensive, and should be minimalized. In order to find a good choice how to traverse throughout this graph, we are given a heuristic $h(s)$, that is supposed to compute a "good" key.
We know for small changes of the key (say, in Hamming distance), the weight of $w(s)$ does not change to much.
Question: Is such a problem known in theoretical computer science, and does there exist theory for it? In particular I am looking for algorithms for problems like these, and conditions on the heuristic $h$ to provide a "good" heuristic.
The description is deliberately vague, in order to allow for wider range of answers. I think many search algorithms do not apply, because they are too generous with search space evaluation. Maybe the problem is even too ill-posed to be accessible to CST tools.
Thank you very much!