From: "Niilo Sirola" <niilo.sirola@tut.fi>
Path: news.mathworks.com!newsfeed.mathworks.com!nntp-out.monmouth.com!newspeer.monmouth.com!news-east.rr.com!news.rr.com!prodigy.com!newsfeed-00.mathworks.com!webx
Newsgroups: comp.soft-sys.matlab
Subject: Re: MATLAB Programming Contest: November 3-10, 2004
Message-ID: <eeefd44.98@webx.raydaftYaTP>
Date: Tue, 9 Nov 2004 17:00:41 -0500
References: <eeefd44.75@webx.raydaftYaTP> <eeefd44.77@webx.raydaftYaTP> <eeefd44.79@webx.raydaftYaTP> <eeefd44.89@webx.raydaftYaTP> <eeefd44.92@webx.raydaftYaTP>
Lines: 36
NNTP-Posting-Host: 195.148.190.99
MIME-Version: 1.0
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
Xref: news.mathworks.com comp.soft-sys.matlab:240693


Ok, here's the description of the basic ideas behind My Sunday Push
entry.

The main idea is to solve the problem recursively, such that if the
full problem does not seem to have obvious solution, drop out some of
the lighter objects and try to solve the simpler problem. Once enough
objects are removed, the problem has an "optimal" solution, and after
that we start to add the removed objects back, heviest first. If the
re-adding fails, revert back to the recursion, again removing some
randomly selected heavy objects. This is all done in the subfunction
mainsolver.

The re-addition is done with a full shortest path search (subfunction
dijkstra). This was a fun part to tweak since it initially could
handle only couple of hundred nodes within reasonable time, and now
runs over 10000 nodes in a flash.

Moreover, the subfunction easysolver tries to find an optimal
solution by first putting the necessary moves after one another and
then trying every permutation of them. This isn't of course practical
so there is some "global" and "local" fiddling to find an order with
no conflicts.

This was actually the very first approach that came to mind, it only
took good four days until I got it to work fast enough. :)
As a peculiarity, my solver uses a slightly different coding for the
moves matrix. It contains one column for each object and the moves
are given as the changes of vectorized array indexes. This allows
fast computing of all positions given initial positions and moves.
This way it is also easy to drop some objects away.

My solver managed to shave couple of thousand points off from some
test cases but failed miserably on others, so I combined it with the
leader at the time. This was worth 0.3 points. The other 0.7 points
came from the idea of using my slow solver only if the faster one
could not get within 1.1 times the optimum move length.