Subscribe to andrewsw's Blog        RSS Feed
-----

Santa's Database

Icon 5 Comments
We need a very large database, to store billions of records. However, it only really needs a single table, at first estimate.

Essentially, just names and addresses. However, we also need a check field, perhaps BIT or BOOL for Good or Bad. Or would 'Naughty or Nice' be more appropriate? We'll default it to 'Naughty' - seems more likely.

Ah, but we'll need another such field, for we need to check it twice.

But wait, another check field for 'Delivered'. We don't want to miss anyone.

Distribution is a tricky issue though. We need to find the optimum route. The addresses alone seem insufficient, so we'll add Longitude and Latitude. From these, we can more easily create a density map.

But we won't want to visit just the highest density area, then the second, etc.. This second may be on the other side of the world. We need a better strategy. Something like "group areas together that have similar densities nearby". Mmm.. not sure this is sufficient? There must be a way to find the optimum route? It would also assist if we consider the North Pole as both starting and ending point. (There is no point in travelling to the first designated area without making deliveries on the way.)

I'll have to mull it over. Fetch some milk and cookies, this could take a while!

Posted Image

5 Comments On This Entry

Page 1 of 1

ishkabible Icon

23 December 2013 - 02:50 PM
traveling salesmen problem N=7,000,000,000 with minimum time complexity around O(n^2) (I think this assumes P=NP) gives us 7,000,000,000 ^ 2...I think you have to settle for "approximately optimal" rather than actually optimal. I was told of a minimum weight spanning tree solution that could guarantee an upper bound of being no more than 2 times longer than optimal. This might be the algorithm your looking for. You might still need a BA computer but at least it can be done.
0

CharlieMay Icon

24 December 2013 - 09:31 AM
Damn, I accidentally hit the minus rep on insatiable's post. Can someone fix that?
0

andrewsw Icon

24 December 2013 - 10:29 AM
Actually, on further reflection, global wind patterns are probably more significant than the density distributions. I am not sure if this makes the problem easier or more difficult. We'll find out tomorrow ;)
0

AdamSpeight2008 Icon

24 December 2013 - 06:14 PM
Maybe Santa's reindeer are diet are supplemented with Infinite Probability food pellets?

Or Santa can pause and unpause the flow of time?
Or Santa CSatNav can solve the problem in <P time.
0

CTphpnwb Icon

24 December 2013 - 08:13 PM
Don't you also need fields (or another table) for what gifts each kid wants/gets?
0
Page 1 of 1

Trackbacks for this entry [ Trackback URL ]

There are no Trackbacks for this entry

December 2014

S M T W T F S
 123456
78910111213
141516171819 20
21222324252627
28293031   

Tags

    Recent Entries

    Recent Comments

    Search My Blog

    3 user(s) viewing

    3 Guests
    0 member(s)
    0 anonymous member(s)

    Categories