This seems like it would be a fun competition, for those who don’t have way too much work to do already ... !! http://azspcs.com/Contest/Nearness …
-
If the grid size is bounded at 30x30 all random examples are just relabelings of the canonical labeling. The best solution can be precomputed and mapped to the relabeling.
Given that there are 900! possibilities, I think the point is that the search space is way too large to precompute exhaustively.
-
-
(Less than that due to symmetry, etc, but yeah.)
Thanks. Twitter will use this to make your timeline better. UndoUndo
-
-
-
I think what he meant is that the program you submit really could just have memorized solutions since you know the max grid size is 30.
-
(even though that memorized solution would probably be sub-optimal)
-
Oh, I see. Hmmm. Yeah the problem would have to be modified further.
-
I agree it would be more interesting to make it a speed game, though. As it stands, someone with free college supercomputer credits might just run 1000 CPU-days of brute force for the win.
-
I am not even convinced yet that the problem space has local minima. If I did pairwise swaps as long as each of them decreases the score, would I get stuck in a suboptimal solution?
-
My thinking is scramble the board and then do greedy pairwise swaps until you stop getting gains. Repeat for a few days and submit the best result. I thiiink you'll get stuck in local minima, but I'm not 100% sure.
End of conversation
New conversation -
Loading seems to be taking a while.
Twitter may be over capacity or experiencing a momentary hiccup. Try again or visit Twitter Status for more information.