4
$\begingroup$

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!

|cite|improve this question
$\endgroup$
  • $\begingroup$ Given that you say the function is "well-behaved", many of these kinds of problems are amenable to en.wikipedia.org/wiki/Newton%27s_method if the first and second derivatives can be estimated. $\endgroup$ – András Salamon May 21 '11 at 13:28
  • $\begingroup$ There are many "heuristic algorithms" for search problems and even books on the topic. Just Google and you will find tons of literature. I think asking for a survey/book on heuristic algorithms for optimization/search problems might be more productive. $\endgroup$ – Kaveh May 24 '11 at 2:33
6
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
1
$\begingroup$

As observed in Aaron Roth's answer, what you're describing does indeed appear to be PLS.

In such cases, there are many, many alternative approaches under the heading of `metaheuristics'. A great introduction to the topic is "Essentials of Metaheuristics" by Sean Luke, but basically this includes techniques like simulated annealing, tabu search, genetic algorithms, particle swarm optimization etc.

|cite|improve this answer
$\endgroup$
0
$\begingroup$

I think that the description is a bit too vague. You have to assume that $w(s)$ is sufficiently smooth to make efficient optimization feasible.

Anyway, I don't know about any particular theory for this kind of problems, but the obvious algorithm that comes into my mind is to expand the successors of each element starting from the one computed from the heuristic key and then use some scheme to consider the other key in order of increasing distance form the heuristic one (either exhaustive or random sampling).

More generally, you could convert the problem into a more conventional optimization problem by considering an extended search space:

$\forall s$ consider a set $\left \{ s_d \right \}$ elements.

$s_0$ corresponds to $s$ and has as successors only $s_1$ and the element reached by the heuristic key. $s_1$ has as successors only $s_2$ and the elements reached by keys at distance $1$ from the heuristic key, and so on.

(Note however that $s_{d_{MAX}/2}$ has exponentially many successors).

You could assign the weight $w(s_d)$ equal to $w(s)$ plus some penalty (additive or multiplicative) based on distance $d$. This will drive the optimization algorithm to expand low-distance nodes first.

|cite|improve this answer
$\endgroup$
-1
$\begingroup$

It sounds like what you need is the A* algorithm. This is a good algorithm for traversing a graph using a heuristic to estimate the "distance" each node is from the destination. In your case, the destination is any node which has a low weight. The heuristic for "distance from a low weight node" would then be a guess as to how close a node is from a low weight node (it sounds like you already know this). I would check out the wikipedia page I posted above for this algorithm and others like it.

|cite|improve this answer
$\endgroup$
  • 3
    $\begingroup$ I don't think A* is appropriate in this context. First, this is a problem of optimization of the node values, not of finding the best path between two nodes. Second, for every node it expands, A* needs to examine all its successors in order to estimate its cost. In the problem presented in this question however, if I understand correctly, examining all successors is too expensive, hence the smooth key to node mapping and heuristic key function must be used. $\endgroup$ – Antonio Valerio Miceli-Barone May 20 '11 at 16:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.