search

ydoc5212 / lil-humans

these are your lil guys, watch em grow or sabotage them, its your universe
GNU General Public License v3.0
0 stars 0 forks source link

see if we can create a marriage algorithm faster than O(N^2) time #10

Open ydoc5212 opened 2 years ago

ydoc5212 commented 2 years ago

Let's innovate on creative solutions to where marriage checks dont have to evaluate each and every person on the planet for each and every person. the simulation's integrity hangs in the balance of resolving this problem. The old simulation came grinding to a halt due to O(N^2) times. Could we get a O(N log N)? ideally O(N). if we could have the whole sim run in O(N) time, that'd be greeeeat.....

ydoc5212 commented 2 years ago

The problem is as such: what is the best algorithm for pairing each person with their most likely partner? (assuming theyve decided to marry, and they favor people with A attractiveness, B height, etc..)

The O(n^2) solution is to, for all humans x, go through all humans y and calculate a sum for partner_likelihood of y for x. Then we normalize the scores to sum to 1, and use random to pick one marriage candidate for x. Rinse and repeat for all humans x.

How do we make this more efficient? We could somehow hash all the desirable traits, or make a binary search tree??