© 1986 by British Computer Society
A Recursive Algorithm for the Optimal Solution of a Complex Allocation Problem using a Dynamic Programming Formulation
Department of Electrical and Electronic Engineering, Brighton Polytechnic, Moulsecomb, Brighton, BN2 4GJ, UK
The work described is a continuation of a line of research into coping with complexity. The methodology is to take a basic problem, the primitive, for which an algorithmic solution exists and whose architecture is particularly clear. Increasing complexity is then introduced into the primitive in successive stages and more complex algorithms derived, all of which are designed to exhibit the essential elegance of the primitive algorithm. To illustrate, the well-known Towers of Hanoi problem has been chosen, the added complications in this case being posed by a multiplicity of poles. In this form, the problem is likened to that of allocating resources within a strict set of rules thereby providing analogies to multi-processor system design and the routeing of information through a communication system.
The multipole Towers of Hanoi formulation represents a multi-dimensional degree-of-freedom system, graphically portrayed in its respective state-space description. This gives rise to multivariable strategy options that are checked by a dynamic programming method which optimises the overall path to the specified goal state. The paper describes a recursive algorithm for this problem formulation which accords with the architectural principles of the primitive algorithm, and therefore draws conclusions into the generation of recursive problem-solving strategies for more general problems.
Received November 1984.
* To whom correspondence should be addressed.
Department of Electrical and Electronic Engineering, Brighton Polytechnic, Moulsecomb, Brighton, BN2 4GJ