In order to be able to apply any of the widely used search strategies we will be considering for use in the project, we will need to define some way of performing an ``incremental search'' on our problem. A search where we can take steps, and decide which way to go after every step. This is necessary in order to limit the size of the subspace we seek thru.
Now, what is our solution space ? It could be seen as many things. We could search in one space first, then in another, eg. ordering the rows first, then the columns and finally the rotation sequence. Or perhaps we should decide upon the rotation sequence first ?
Some time was spend in the very beginning of this project, experimenting with different strategies, and ways of searching. I came to several conclusions doing this:
The strategy is: First, decide which row should be the upper-most row, and which column should be the left-most column. Calculate or estimate the cost of this partial solution. Then, decide on the second-upper-most row, and the second-left-most column, calculate or estimate again, and so on. For each of these partial orderings, we find a suitable sequence of Givens Rotations in order to be able to estimate a lower bound on the cost of the current solution. More on this later.
As one notices, we do not at all consider the rotation sequence in this ordering strategy. In fact, the actual rotation sequence is found from a very simple algorithm, which has some roots in theory and some roots simply in experience gathered: