Thread: Machine Learning Algorithm in C

Was the example provided by your instructor? I don't see how the optimal result is 10. It looks like it should be 12: 7 + 2 + (skip -1) 3 + (skip -2) -1 + 6 + -5 = 12

Also, is there a reason why you titled this post "Machine Learning Algorithm in C"? This isn't a machine learning algorithm.

EDIT:
Looking at your code, I think you may need a more sophisticated approach (dynamic programming?) to deal with runs of negative numbers. For example, consider: -1 -3 -4 -1. The optimal path through this is to skip the first -1, pick -3, then skip -4 to pick -1, thus ending up with a total of -4. If you only consider pairs, you'll pick -1, then -3, then -1, resulting in the suboptimal -5 total.

Originally Posted by Curious_student

1. The first integer from the input indicates the number of digits(N) in the array to follow. You are also allowed to skip the first and last numbers( skip -5). The output is indeed 10, but my instructor is definitely not making this easy for a high-school level student.

Ah, I see. My mistake.

Originally Posted by Curious_student

2. It seems to me that if you dig into it, to provide the correct answer the algorithm must analyze the whole array and pick the optimal path, which is what I always thought machine learning consisted of.

That is not "machine learning" in the sense as it is currently used in computer science. Broadly speaking, machine learning involves getting machines to analyse data so as to make decisions that are as optimal as possible to what humans want when presented with similiar data that the machine has not previously encountered. You could use a machine learning approach here, but as your instructor does not appear to have provided you with a training set, that seems unlikely especially if the instructor did not mention machine learning to you.

As I mentioned in my edit to my previous post, you probably do need a more sophisticated approach than just comparing pairs of adjacent negative numbers, and my suggestion was to look into dynamic programming.

Machine learning refers to algorithms that learn from experience. It has nothing to do with your problem. Your problem is an optimization problem.

It looks like it can be solved "greedily". This is where you take the best answer at each step. For your given problem the first step is either 2 or -1, so you take 2. Then you can either take -1 or 3, so you take 3 (total 5). Then between -2 and -1, -1 is best (total 4). Then between 6 and -5, 6 is best (total 10). Then between -5 and the end, the end is best. Total 10.

I'm not sure about this, though, but I can't think of a counter-example. If it can't be solved greedily then "dynamic programming" will certainly solve it since it has both optimal substructure and repeated subproblems. Brute force will not work well on large inputs since the number of possible paths grows exponentially.

john.c, that is the approach that Curious_student tried, and I already provided a counter-example in post #2: -1 -3 -4 -1

Oh, right. I obviously didn't read very closely ... at all.

Maybe an approach that considered the values in groups of 4 would work, although a full dynamic programming solution wouldn't be that difficult. You could work backwards figuring out the optimal solution at each point. So for your example:

Code:

. 1  2  3  4
 -1 -3 -4 -1
 
   val  opt
5:  0    0    after the last position counts as 0
4: -1   -1    if we are here, the best result is -1
3: -4   -4    if we are here, the best result is -4 (skip 4th element)
2: -3   -4    if we are here, the best result is -4 (skip 3rd element)
1: -1   -5    if we are here, the best result is -5 (go to 2 or 3)
0:  0   -4    before first position counts as 0; best result here is best result overall

Superficially this resembles a backwards greedy selection, but it's actually choosing optimally at each point so, due to the problem's optimal substructure, it results in an optimal overall solution. This is what I thought of first but due to the superficial resemblance I jumped to the conclusion that it was actually greedy.

You can see the repeating subproblems (and convince yourself of the optimal substructure) in this diagram for 4 elements:

Code:

.                ________O________
                /                 \
           ____1____             __2__
          /         \           /     \
       __2__         3         3       4
      /     \       / \       / \      |
     3       4     4   X     4   X     X
    / \      |     |         |
   4   X     X     X         X
   |
   X

Also here -> A Smart Algorithm In C - C And C++ | Dream.In.Code

If you understand what I was saying then the implementation should be obvious. But I may not have been very clear, so I'll try again.

If the input is 6 elements with values a,b,c,d,e,f, then you read them into the array like this (with a 0 at the beginning and end):

Code:

0 1 2 3 4 5 6 7
0 a b c d e f 0

Then you figure out the optimal values from element 7 back to element 0:

Code:

.    optimal value
7 0    0
6 f    f
5 e    e + (optimal value of elem 6 or 7, whichever's best)
4 d    d + (opt val of elem 5 or 6, whichever's best)
3 c    c + (opt val of elem 4 or 5, ...)
2 b    ...
1 a    ...
0 0    0 + (opt val of elem 1 or 2, whichever is best)

And the optimal value for element 0 is the final answer.

Working it on your example input: 2 -1 3 –2 -1 6 -5

Code:

8  0    0
7 -5   -5
6  6    6    ( 6 +  0)
5 -1    5    (-1 +  6)
4 -2    4    (-2 +  6)
3  3    8    ( 3 +  5)
2 -1    7    (-1 +  8)
1  2   10    ( 2 +  8)
0  0   10    ( 0 + 10)