Bundler resolver blows up with many available versions

I've seen Bundler's resolver blow up (takes a very long time, but does complete) in a production situation where we have a moderate number of dependencies (say 10-20) where some of these have many versions available in the repository (three gems have at least 40 available versions).

I think I've reproduced this situation in a unit test.  It's not a very good test, but it serves to illustrate the problem.

I don't (yet...?) have a solution to the resolver algorithm.  Would be a fun problem if I can find the time.