From: Simon Tatham Date: Sat, 29 Mar 2014 17:49:48 +0000 (+0000) Subject: Filled in the search-algorithms section. X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?p=matchsticks-search.git;a=commitdiff_plain;h=90d131407a55ddcecbe735d2976ea7dfa1355475 Filled in the search-algorithms section. --- diff --git a/template.html b/template.html index f8e82d1..ab04962 100644 --- a/template.html +++ b/template.html @@ -321,16 +321,74 @@ minimum fragment greater than

Computer search

-FIXME: describe our two search strategies. -

- -

-FIXME: stress that one is exhaustive but the other depends on a -conjectured denominator bound. -

- -

-FIXME: the two strategies are good at different cases. +We've done some computer searching to find the answers, or the +probable answers, to small cases. We've got two different search +strategies: +

+ +

+Iterate over adjacency matrices. This strategy relies on the +idea that we can assume, without loss of generality, that each input +stick contributes at most one piece to each output stick. (This is the +reverse of the assumption made in the proof of writinghawk's upper +bound above! But fortunately they don't have to both be true at the +same time.) So you could draw up an n Ã— m +matrix indicating which input sticks contributed to which output +sticks. Given such a matrix, the problem of finding an optimal +dissection with that matrix can be written as a linear +programming problem. (One variable per dissection fragment is the +obvious way, but then the objective function ‘take the minimum’ isn't +linear. But if you add an extra variable showing the minimum size +itself, and then make the other variables say by how much each other +piece exceeds the minimum fragment, then it is linear.) So, +in principle, we can just iterate over all the possible +2nm adjacency matrices, and solve a linear +programming problem for each one! Of course this takes exponential +time, but it turns out reasonably practicable in small cases as long +as you prune branches of the search tree early and often if you can +easily show they can't give a result as good as the best one you +already have. +

+ +

+ILP over possible stick partitions. A completely different +approach is to enumerate the various ways in which a stick can be +partitioned into smaller pieces. (There are infinitely many, of +course, but if you pick a denominator d and constrain to +multiples of 1/d then that's not too bad.) This approach +requires us to make a guess at the minimum fragment, so that we can +enumerate partitions which use pieces no smaller than that. Once we +have a list of the partition types for the input and output sticks, we +express them as vectors showing how many pieces of what lengths they +use, and then solve an integer-linear-programming problem to find +combinations of them for which all the piece counts add up. Again, ILP +is a computationally hard problem, but this algorithm seems to work OK +in small cases because if you start your minimum fragment too +big and lower it until you get a solution, you never +have too many possible partitions to worry about. +

+ +

+The first of these strategies is genuinely exhaustive: assuming no +bugs in the search program, the algorithm must find the best possible +dissection. The second, however, leaves open the possibility that a +better dissection might exist using a denominator larger than any we +had considered. Examination of the data we have so far strongly +suggests the conjecture that no denominator larger than n is +ever needed in an optimal dissection (though denominators larger +than m can certainly occur), but we have no proof of that, and +so results generated by the second search program cannot be considered +reliable unless an upper bound proof confirms that they can't be +beaten. +

+ +

+Disregarding that weakness of the ILP approach, the two search +algorithms complement each other well, because once n gets a +bit larger we find that the matrix iteration algorithm works best for +small m, while the ILP approach works best for large m +(i.e. not much smaller than n). So running both has allowed us +to collect a reasonable amount of data.