Cheap and Secure Web Hosting Provider : See Now

Find expression with minimal distance to target

, , No Comments
Problem Detail: 

I will start of with an informal example and give a more formal problem definition later.

Say I have a finite set of positive real values: $\{2.3, \pi, 4.382, 0.3\}$. Using normal addition and multiplication, we can construct expressions like $(\pi + 2.3) * 0.3 + 4.382$ and $(0.3 + \pi) * (2.3 + 4.382)$. We put the following constraints on the expressions:

  1. Each value in the set must be used exactly once in the expression.
  2. We can only use addition, multiplication and brackets in our expression.

The goal now is to get as close to a target value, say $9.5$. For example, the expression $2.3 * \pi * 4.382 * 0.3 = 9.49886...$ gets close. How can we find the expression whose evaluation is closest to $9.5$? Or more formally:

Given a finite set $V$ of - not necessarily unique - elements, two binary operands $f(x, y)$ and $g(x, y)$ that operate on the elements in $V$ and a target value $t$, find the expression $E$ containing each element of $V$ exactly once, such that the evaluation of $E$ is as close to $t$ as possible. $E$ must consist only of the values in $V$, the given operands and brackets.

I understand that for small sets, an exhaustive check that checks all possible expressions is feasible. Using heuristics, quickly finding an approximate answer (with small distance to the target) is probably possible for larger sets too. My questions are; does a more efficient method exist to find exact answers for large sets? Do efficient methods exist specifically for certain operands? What fields of mathematics and computer science touch on this subject?

Asked By : Arthelais
Answered By : Juho

This is a very difficult problem. For an already hard special case, you can look at the subset sum problem. So in general, one direction to look at is NP-hard optimization problems (and ways of coping with hardness).

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65495

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback