Parallel Programming in C with the Message Passing Interface.ppt

Today’s Outline
Chapter binatorial Search
Terminology
Divide and conquer
Backtrack plex munication
Branch and bound
Searching game trees
Combinatorial Search: Examples
Laying out circuits in VLSI
Planning motion of robot arms
Assigning crews to airline flights, roommates to dorm rooms
Proving theorems
Playing games
We’ll Study binatorial Search Methods
Divide and conquer
Backtrack search
Branch and bound
Alpha-beta search
State-space 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 bine solutions to subproblems
Recursive: subproblems may be solved using the divide-and-conquer methodology
Example: quicksort, mergesort
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 e a bottleneck as number of processors increases
Backtrack Search
Uses depth-first search (in OR-tree) to consider alternative solutions to binatorial search problem
Recursive algorithm
Backtrack occurs when
A node has no children (“dead end”)
All of a node’s children have been explored
Example:Crossword Puzzle Creation
Given
Blank crossword puzzle
Dictionary of words and phrases
Assign letters to blank spaces so that all puzzle’s horizontal and vertical “words” are from the dictionary
Halt as soon as a solution is found
Crossword Puzzle Problem
Given a blan