# Find expression with minimal distance to target

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?

• Can you provide some motivation for this problem? Is this a theoretical exercise or do you have real data for which you are trying to solve? – Nicholas Mancuso Nov 3 '16 at 19:04
• @NicholasMancuso I was inspired by a game I once played where you roll dice and try to get as close to a target score as possible using basic arithmetic. This is a generalization of that problem. The number of operands could be more than two, but I wanted to keep the generalization relatively simple. – Arthelais Nov 3 '16 at 19:08