should i burn it?

random walk

what is a random walk?
it's a very simple simple algorithm that randomly makes small changes to a solution and just keeps track of the best one so far.

it's easy to apply this to our folder problem

1. start with nothing
2. randomly choose a folder
3. if it's not in the backup we add it otherwise (it's in the backup and) we remove it
4. see if we've found a better solution then the best so far

using the script random_walk.rb we can find a pretty damn good solution in about 1 second for the 16 folder problem
(the upper bound is 4463788)

iter=0 new max=1137844 9blobs
iter=1 new max=2062294 9blobs, rgb torus reflect
iter=2 new max=2597730 9blobs, chocolate stand, rgb torus reflect
iter=3 new max=3541270 9blobs, back2revisited, chocolate stand, rgb torus reflect
iter=4 new max=3751234 rgb checker spheres, 9blobs, back2revisited, chocolate stand, rgb torus reflect
iter=5 new max=4008582 rgb checker spheres, 9blobs, back2revisited, chocolate stand, closed motor particles, rgb torus reflect
iter=7 new max=4247910 rgb checker spheres, 9blobs, back2revisited, chocolate stand, rgb torus reflect, wideanglecheckers
iter=28 new max=4352088 4step, 9blobs, back2revisited, bw nye spin, chocolate stand, the cell, wideanglecheckers
iter=96 new max=4357528 rgb checker spheres, 360statue, a minute of pi, bw nye spin, closed motor particles, rgb torus reflect, underlay
iter=132 new max=4384538 9blobs, bw meta reflect2, chocolate stand, the cell, underlay
iter=149 new max=4386042 4step, back2revisited, chocolate stand, the cell, underlay, wideanglecheckers
iter=217 new max=4436412 rgb checker spheres, back2revisited, bw meta reflect2, closed motor particles, wideangls, yellow_react_skyl
iter=523 new max=4441718 360statue, 4step, closed motor particles, rgb torus reflect, wideangls, yellow_react_skyl
iter=1171 new max=4442144 rgb checker spheres, 360statue, 4step, bw meta reflect2, bw nye spin, chocolate stand, the cell, yellow_react_skyl
iter=1574 new max=4443202 360statue, 9blobs, bw meta reflect2, underlay, wideanglecheckers
iter=1740 new max=4460478 rgb checker spheres, 360statue, 4step, 9blobs, a minute of pi, closed motor particles, underlay
iter=3025 new max=4462950 rgb checker spheres, 9blobs, bw nye spin, chocolate stand, underlay, wideanglecheckers
iter=6087 new max=4462982 rgb checker spheres, 4step, a minute of pi, bw meta reflect2, bw nye spin, closed motor particles, rgb torus reflect, yellow_react_skyl
iter=19257 new max=4463352 a minute of pi, back2revisited, chocolate stand, closed motor particles, wideangls, yellow_react_skyl
iter=29420 new max=4463668 rgb checker spheres, 360statue, 9blobs, back2revisited, bw meta reflect2, bw nye spin, chocolate stand
iter=30843 new max=4463672 4step, 9blobs, back2revisited, the cell, wideanglecheckers, wideangls

a very good solution is found very quickly, there is little improvement after the first 100 or so iterations

but how about with some more combinations? lets try 30 folders
after 5 seconds we've got a pretty good solution, only 4 off the gloabl optimal.
(recall brute_force2.c took 2.5 minutes to find the global optimum of 4,463,784)

iter=0 new max=2627414 underla3
iter=1 new max=3470954 back2revisite2, underla3
iter=2 new max=3628302 back2revisite2, closed motor particle3, underla3
iter=3 new max=3885650 closed motor particles, back2revisite2, closed motor particle3, underla3
iter=4 new max=4029190 closed motor particles, back2revisite2, closed motor particle3, underla3, back2revisite3
iter=515 new max=4406858 rgb checker spheres, 4step, a minute of pi, bw nye spin, back2revisite2, chocolate stan2, rgb torus reflec3, 4ste3
iter=2777 new max=4454504 a minute of pi, chocolate stand, closed motor particles, a minute of p2, back2revisite2, chocolate stan2, closed motor particle2, closed motor particle3, the cel3, 360statu3
iter=10266 new max=4461772 rgb checker spheres, back2revisited, chocolate stand, bw nye spi2, closed motor particle2, closed motor particle3, the cel3, rgb checker sphere3, 4ste3, back2revisite3, bw meta reflect3
iter=45709 new max=4463090 a minute of pi, chocolate stand, rgb torus reflec3, wideanglechecker3, rgb checker sphere3, 4ste3, 9blo3, bw meta reflect3
iter=147837 new max=4463710 4step, chocolate stand, back2revisite2, bw nye spi2, chocolate stan2, rgb torus reflec3, the cel3, wideanglechecker3, back2revisite3, bw meta reflect3
iter=1253248 new max=4463780 9blobs, a minute of pi, bw meta reflect2, bw nye spin, chocolate stand, closed motor particles, closed motor particle3, wideanglechecker3, rgb checker sphere3

random walk is unstoppable!!

even with 100 folders, which would be 2¹⁰⁰ ( 1,267,650,600,228,229,401,496,703,205,376 ) combos we find very good solutions quickly.
here are the outputs from 4 runs stopped after a minute

the actual best solutions are found in about 1/100 of a second and non better are found over the next 10 seconds
i think this is indicative of the type of problem this is; one where there are many nearly optimal solutions
we can see this in the 16 folder problem where there are 15,792 feasible solutions (ie would fit on a disk) out of all 65,536 possible