Mainly Tech projects on Python and Electronic Design Automation.

Sunday, May 29, 2011

Good enough solutions can be great!

I've had to imlement the solutions to two problems on Rosetta code lately and they both involve heuristics that get around the prolems of exhaustive search.

The first problem was in finding a way to shuffle the letters of a string so that a minimum of letters end up in the same place. My first solution was to go through all letter permutations and return the best. That takes for ever on longer strings such as the word 'antidisestablishmentarianism'.
The algorithm I then turned to just swaps letters if they swap into positions that put different characters into corresponding locations. That algorithm is very fast and seems to give good answers.

The second problem was in creating knights tours of chess boards of varying sizes. The given Wansdorff's algorithm is much quicker than a full depth first search, and was straight-forward to code . I later found evidence that for larger board sizes the algorithm fails . (Although the paper does suggest simple improvements that work for boards sizes with thousands of squares).

Coding those two, makes me remember that results are what count  normally. You won't achieve much by searching for the theory of relativity if the queen wants Newtons laws of motion so that sailing ships can trade and plunder!


Subscribe Now: google

Add to Google Reader or Homepage

Go deh too!