0

In my project i face a scenario where i have a function with numerous inputs. At a certain point i am provided with an result and i need to find one combination of inputs that generates that result.

Here is some pseudocode that illustrates the problem:

Double y = f(x_0,..., x_n)

I am provided with y and i need to find any combination that fits the input.

I tried several things on paper that could generate something, but my each parameter has a range of 6.5 x 10^9 possible values - so i would like to get an optimal execution time.

Can someone name an algorithm or a topic that will be useful for me so i can read up on how other people solved simmilar problems.

I was thinking along the lines of creating a vector from the inputs and judjing how good that vektor fits the problem. This sounds awful lot like an NN, but there is no training phase available.

Edit: Thank you all for the feedback. The comments sum up the Problems i have and i will try something along the lines of hill climbing.

Improve this question
4
  • 1
    I don't get what you are trying to achieve. Are you trying to find the possible inputs that yields the desired output? Without knowing what the function is - it is impossible to know, even if you can sample your function infinite number of times. However, if there is some knowledge on f - it might be done (for example: Is it a polynom?) Commented Oct 15, 2012 at 10:28
  • 1
    One view of what you are trying to do is to solve an inverse problem. Another view is that you are trying to select a vector of x values to minimise the difference between a computed y and the target y, which makes yours an optimisation problem. There are very many algorithms for tackling such problems, but without a lot more input about your problem there will be no good advice forthcoming. Commented Oct 15, 2012 at 10:35
  • You seem to be asking for an equation solver. It depends very much on the kind of f and the domain of x_i which method to choose. For example, if the domain of y and x_i are real numbers and f is an polynomial (over real numbers), you need a polynomial root finder. Commented Oct 15, 2012 at 10:44
  • 1
    If your input arguments are, as hinted at by the question title, all integers, you could start your researches at en.wikipedia.org/wiki/Combinatorial_optimization Commented Oct 15, 2012 at 11:05

1 Answer 1

Reset to default
1

The general case for your problem might be impossible to solve, but for some cases there are numerical methods that can help you solve your problem.

For example, in 1D space, if you can find a number that is smaller then y and one that is higher then y - you can use the numerical method regula-falsi in order to numerically find the "root" (which is y in your case, by simply invoking the method onf(x) -y).
Other numerical method to find roots is newton-raphson
I admit, I am not familiar with how to apply these methods on multi dimensional space - but it could be a starter. I'd search the literature for these if I were you.
Note: using such a method almost always requires some knowledge on the function.

Another possible solution is to take g(X) = |f(X) - y)|, and use some heuristical algorithms in order to find a minimal value of g. The problem with heuristical methods is they will get you "close enough" - but seldom will get you exactly to the target (unless the function is convex)

Some optimizations algorithms are: Genethic Algorithm, Hill Climbing, Gradient Descent (where you can numerically find the gradient)

Improve this answer
Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.