Protected: Algorithm Heuristics

In my past posts on solving tangram puzzles I’ve given two slightly different algorithms. Neither algorithm as I gave it had any heuristics. I aim to show you a few simple heuristics that should work in non-pathological cases.

The most obvious heuristic for the Poly-Solve algorithm is to sort the puzzle pieces by size (or bounding box) before you pass them into position_puzzle_pieces. When I implemented Poly-Solve this did substantially speed up the running time. The reason this heuristic works is because large puzzle pieces have fewer possible orientations inside the silhouette which implies that fewer combinations need to be tried. The pathological case for this algorithm is when the largest puzzle piece must be fitted last, which when you think about it, is truly pathological.

For the Vert-Solve heuristics I define P to be the set of puzzle pieces, where each element is a vertex v together with a pointer to its puzzle piece.

1. One heuristic for the Vert-Solve algorithm is to try using vertices from the puzzle pieces that are perfect matches. By perfect match for a vertex, v, I mean v is identical modulo translations, rotations, and reflections to a vertex in the silhouette. With this heuristic the complexity of the new silhouette should be reduced each time vert_solve recurses.

2. Another possible heuristic for Vert-Solve is to sort the vertices in P from largest to smallest, where by size I mean the length of the shortest line segment of the vertex. And also sort the vertices in s. Thus when we select the first tuple ((&p,v), w) from Pxs, the v, w are the largest possible vertices. The logic behind this heuristic is similar to the above heuristic for Poly-Solve.

3. We can combine 1 and 2 to create a new sorting algorithm for P, using weights for the importance of 1 and 2. In fact there are lots of ways to sort P but the running time of the sorting algorithm can be important.

That is all for today. It’s easy to think of more heuristics for both algorithms but I need to test them before posting because otherwise I’m only speculating.