2

From a vector of float numbers

std::vector<float> v { 0.32, 0.0004, 12.78, -9.2, 1.1 };

I am trying to find out what series of "+" and "-" one can place in front of each float number to get a result that is as close as possible as the value GOAL. Note that no number can be left out (all values must be used).

float GOAL = 4.9;

For this example, I think the best possible solution is 

+ 0.32 - 0.0004 + 12.78 + (-9.2) + 1.1 = 4.9996

Let true mean "+" and false mean "-", the best possible solution could be represented as 

std::vector<bool> solution { true, false, true, true, true }

One could just iterate through all possible combinations. If n is the size of v, then there are 2^n possible combinations. As n grows large, the process becomes quickly very slow (2^1000 ≈ 10^301).

How could I go about writing a search algorithm that would output not the best but a descent solution in polynomial time?

FYI, I have only basic understanding of search algorithms. I understand the concepts of heuristic, greedy algorithm, hill climbing, search tree, minimax game tree and others for examples.

Remi.b
  • 17,389
  • 28
  • 87
  • 168
  • Forget about the search algorithm. Before you can even start on it, you will need to figure out what to do with [the fact that floating point math is broken](http://stackoverflow.com/questions/588004/is-floating-point-math-broken). – Sam Varshavchik Jan 02 '17 at 13:49
  • 3
    @SamVarshavchik For *"as close as possible"*-questions, that's not really an issue (for well conditioned problems). – Baum mit Augen Jan 02 '17 at 13:51
  • @Remi.b how many places after decimal point? Is there a limit? – user2736738 Jan 02 '17 at 13:55
  • 1
    This is the [bin packing problem](https://en.wikipedia.org/wiki/Bin_packing_problem) which is NP-complete. It's equivalent to deciding whether all the items can fit into two bins, one for negative items and one for positive. – Potatoswatter Jan 02 '17 at 14:00
  • Possible duplicate of [Writing an algorithm to decide whether a target number can be reached with a set of other numbers and specific operators?](http://stackoverflow.com/questions/16564543/writing-an-algorithm-to-decide-whether-a-target-number-can-be-reached-with-a-set) – wally Jan 02 '17 at 14:03
  • 1
    @Muscampester The dupe asks for a perfect fit, OP for the closest possible. That is a significant difference. – Baum mit Augen Jan 02 '17 at 14:07
  • @BaummitAugen With floating point numbers is the challenge not essentially same? I.e. how do you know there isn't a closer solution unless you've tried them all? – wally Jan 02 '17 at 14:21
  • @Muscampester Being able to prove optimality without trying all solutions is like the whole point of algorithms. It is not clear that there is no better approach than brute-force for this problem. – Baum mit Augen Jan 02 '17 at 14:25

5 Answers5

2

I am just giving a basic algorithm to do this.

1) Calculate the length of available float numbers. ( I assumed length is fixed ).

2) Have an array of the (length-1). with all zeros. 3) Then try to perform operation between the floating numbers.( Zero refers negative ). 4) If it was not matching to GOAL, then increment the number by assuming the array as binary one. 5) Repeat step 3 & 4 until it matches GOAL. 6) Even at end if it is not matched , there is no possibility.

Ex : Floating vector size is 5. Then the all the possible operations are

Step 2: 0000 --> (1st - 2nd - 3rd - 4th - 5th)

Step 3: 0001 --> (1st - 2nd - 3rd - 4th + 5th) (Incremented binary num)

Step 4: ((1st - 2nd - 3rd - 4th + 5th) != GOAL ) --> Increment and call Step3. So, 0010

It will calculate via all the possibility.

ban
  • 71
  • 7
1

not sure if this conforms to your polynomial time requirement, but genetic algorithms tend to do pretty well in this kind of optimization.

also, as an implementation detail, since you are going to add up a large number of floating point numbers, you might want to look into Kahan summation to minimize floating point error.

QuarterlyQuotaOfQuotes
  • 406
  • 4
  • 13
1

I don't see an elegant solution but... the following is based on a recursive function (a template function, so you can use it with double and long double without changes)

#include <cmath>
#include <vector>
#include <iostream>

template <typename F>
F getSol (std::vector<F> const vals, F const & goal,
          std::vector<bool> & sol, std::size_t const & used,
          F const & sum)
 {
   F  ret;

   if ( used == vals.size() )
    {
      ret = sum;
    }
   else
    {
      std::vector<bool> sol1 { sol };
      std::vector<bool> sol2 { sol };

      sol1.push_back(true);
      sol2.push_back(false);

      F ret1 { getSol(vals, goal, sol1, used+1U, sum+vals[used]) };
      F ret2 { getSol(vals, goal, sol2, used+1U, sum-vals[used]) };

      if ( std::fabs(ret1 - goal) < std::fabs(ret2 - goal) )
       {
         ret = ret1;
         sol = std::move(sol1);
       }
      else
       {
         ret = ret2;
         sol = std::move(sol2);
       }
    }

   return ret;
 }


int main()
 {
   std::vector<float> v { 0.32, 0.0004, 12.78, -9.2, 1.1 };
   std::vector<bool>  solution;

   float goal { 4.9f };

   float res { getSol(v, goal, solution, 0U, 0.0f) };

   std::cout << "the result is " << res << std::endl;
   std::cout << "the solutions is ";

   for ( auto const & b : solution )
      std::cout << b << ", ";

   std::cout << std::endl;

 }
max66
  • 65,235
  • 10
  • 71
  • 111
1

We can think about a greedy algorithm, which gives a descent solution in O(n) time.

Algorithm :

Let the array and goal be :

vector<float> v { 0.32, 0.0004, 12.78, -9.2, 1.1 };
float GOAL = 4.9;

Now start iterating the vector from the first index, and greedily choose the sign, i.e. 

If  "+" :
     diff = |Goal- ValueTillNow| = |4.9-0.32| = 4.58
If  "-" :
    diff = |Goal- ValueTillNow| = |4.9-(-0.32)| = 5.22

Now since we want the ValueTillNow to be as close to the Goal we will greedily choose "+" for first float.

Now go similarly for rest index in array. Update ValueTillNow. Calculate the diff for two options i.e. "+" and "-" and choose the one with leads closer to GOAL.

Time Complexity : O(n)

pseudo_teetotaler
  • 1,485
  • 1
  • 15
  • 35
1

Looks like an integer linear programming problem to me. I would split this up in two linear integer programs, the first for going over GOAL, the second one for going under. Thus giving you the following two programs, where b_i = 0 stands for a - and b_i = 1 for a + in your ansatz.

Going over, thus minimizing:

min  Sum(v_i - 2 * b_i * v_i)
s.t. Sum(v_i - 2 * b_i * v_i) > GOAL
     b_i >= 0
     b_i <= 1
     b_i is an int

max  Sum(v_i - 2 * b_i * v_i)
s.t. Sum(v_i - 2 * b_i * v_i) < GOAL
     b_i >= 0
     b_i <= 1
     b_i is an int

Then apply the usual algorithms for solving the two LP and see wich solution fits better. If you let the algorithms run to the bitter end, the problem is NP-hard. But there are algorithms that deliver reasonable solutions after a finite number of steps.

Dominic Hofer
  • 5,751
  • 4
  • 18
  • 23