The Fast Fourier Transform参考.ppt

Parallel Programmingin C with MPI and OpenMP Michael J. Quinn Chapter 16 Combinatorial Search Outline Terminology Divide and conquer Backtrack search Distributed termination detection Branch and bound Searching game trees Terminology Combinatorial algorithm: computation performed on discrete structure Combinatorial search: finding one or more optimal or suboptimal solutions in a defined problem space Kinds of combinatorial search problem Decision problem Optimization problem Combinatorial Search: Examples Laying out circuits in VLSI Planning motion of robot arms Assigning crews to airline flights Proving theorems Playing games We’ll Study Four Combinatorial Search Methods Divide and conquer Backtrack search Branch and bound Alpha-beta search Search Tree Each node represents a problem or sub-problem Root of tree: initial problem to be solved Children of a node created by adding constraints AND node: to find solution, must solve problems represented by all children nodes OR node: to find solution, solve any of problems represented by children nodes Search Tree (cont.) AND tree Contains only AND nodes Divide-and-conquer algorithms OR tree Contains only OR nodes Backtrack search and branch and bound AND/or tree Contains both AND and OR nodes Game trees Divide and Conquer Divide-and-conquer methodology Partition a problem into subproblems Solve the subproblems Combine solutions to subproblems Recursive: subproblems may be solved using the divide-and-conquer methodology Example: quicksort Centralized Multiprocessor Divide and Conquer Unsolved subproblems kept in one stack Processors needing work can access stack Processors with extra work can put it on the stack Effective workload balancing mechanism Stack can become a bottleneck as number of processors increases Multicomputer Divide and Conquer Subproblems must be distributed among memories of individual processors Two designs Original problem and final solution stored in memory of a single processor Both original pr