7. Decryption by Optimization

The problem of optimization is to find (search for) the ``best'' solution, where we have the following two ingredients:

• Some way of measuring ``best''.
• Some way to generate all candidate solutions, i.e. all possible solutions.

We meet these two conditions: ``best'' is ``closest in L¹ distance to training text'' and Section 6.2 explained that swaps generate all possible keys. Therefore, we can look at known algorithms for solving optimization problems:

• We have already seen exhaustive search and eliminated it as being infeasible.
• Let us now look more closely at hill-climbing.