7 Design Strategies for Divide-and-Conquer Algorithms
Given a problem specification Π a design strategy derives specifications for subproblems in such a way that solutions for the subproblems can be assembled (via a program scheme) into a solution for Π. Note that a strategy does not solve the derived specifications, it merely creates them.
Three design strategies emerge naturally from the structure of divide-and-conquer algorithms. Each attempts to derive specifications for subalgorithms that satisfy the conditions of Theorem 6.1. If successful then any operators which satisfy these derived specifications can be assembled into a divide-and-conquer algorithm satisfying the given specification. The design strategies differ mainly in their approach ...
Get Readings in Artificial Intelligence and Software Engineering now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
