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.