[url=http://infinitesearchspace.dyndns.org/cont...ons-il-brigante]http://infinitesearchspace.dyndns.org/cont...ons-il-brigante[/url]
Submitted by Jim Gillogly on Mon, 12/26/2011 - 09:14New
A couple of insights
I mostly did simple hill-climbing -- start with a set of points, either random or a set from a previous solution, and then move the points one at a time to try to improve the result.
My first "aha" was using 3-point lines as a tiebreak for the hillclimbing: they're "builders" for 4-point lines, so usually the more incomplete 3's you have, the better chance you have of getting another 4.
My major "aha" was figuring out how to make the updating incremental. There were lots of special cases to sort out, but it was worth it: I gained about three orders of magnitude (!) in execution speed.
After getting a solution I'd try a few multiples of it to see what turned up (and that was often helpful), but looking at the winning solutions I can see I didn't go nearly far enough on that track. My solutions were mostly pretty small: for example, for N=37 my tied solution was:
(-72,36),(108,16),(-216,-36),(-1332,-144),(84,24),(162,18),(243,-9),(108,-54),(-12,-24),(-180,72),(-900,72),(144,-36),(396,0),(108,-24),(648,36),(-252,36),(288,36),(153,-9),(1188,216),(-117,-9),(756,0),(-432,-54),(504,-36),(348,-24),(-348,48),(-252,-144),(378,-54),(108,-144),(-162,-54),(423,-9),(228,-24),(1188,-144),(540,72),(216,0),(-324,0),(-36,-36),(-360,72)
I clearly missed some "ahas" to try!
Jim Gillogly Знаял третье место.
Как я понял смыл его алгоритма такой:
Берем предыдущее решение или случайный набор точек. Перемещая точки стремимся улучшить решение. При этом используются специальные процедуры "ahas" и "multiples". Специфика алгоритма такова, что координаты точек получаются весьма небольшими.
