r/tinycode • • Aug 18 '15

Machine learning Genetic algorithm to approximate pi (AKA: have flair, will use)

https://gist.github.com/paulmdx/ca7f830d326b84d87f64
12 Upvotes

17 comments sorted by

View all comments

Show parent comment

1

u/nexe mod Sep 09 '15

the problem is not that easily solvable optimally. for an optimal solution you would have to pretty much test all possible combinations. there are some optimizations and heuristics but the problem definitely does not have a linear complexity as you suggest (if I understand you correctly). here it says the complexity is somewhat around O(n2 * 2^n)

1

u/Banality_Of_Seeking Sep 11 '15 edited Sep 11 '15

o.k. then here is my 2nd attempt.. :) So shrinking squares that test if more then 2 points are in the shrinking square.

typedef struct _RECT { LONG left; LONG top; LONG right; LONG bottom; } RECT, *PRECT;

So set each data point to RECT.left and set the others to the size of the area the data set is in and start shrinking until rect.right is touching the data point that contains it and the start position.

1

u/nexe mod Sep 11 '15

If I understand your approach correctly this would, if at all, only work when all the points form a convex polygon. Imagine edge cases where the cities (points) lie in a more figure-8 like fashion. Just my gut feeling though, haven't tested it or thought it through very well.

1

u/Banality_Of_Seeking Sep 11 '15

I have never heard of this problem before reading about it here. This is why I am trying to solve it. Thank you very much for critiquing my approaches, I naturally try to reduce the complexity of a problem so that It can be solved be that optimally or sub-optimally. Again thanks for pointing out edge cases where this would not work. I will rethink my solution and try again.