These notes are intended for use by students in cs1501 at the University of Pittsburgh and no one else



Download 186.06 Kb.
Page2/24
Date03.05.2017
Size186.06 Kb.
1   2   3   4   5   6   7   8   9   ...   24

Pruning and Branch and Bound

      • For example on board:
        • Since edge (C, D) does not exist we know that no paths with (C, D) in them should be tried
          • If we start from A, this prunes a large subtree from the tree and improves our runtime
        • Same for edge (A, E) and others too
    • Important note:
      • Pruning / Branch and Bound does NOT improve the algorithm asymptotically
        • The worst case is still exponential in its run-time
      • However, it makes the algorithm practically solvable for much larger values of N

Recursion and Backtracking

  • Exhaustive Search algorithms can often be effectively implemented using recursion
    • Think again of the execution tree
      • Each recursive call progresses one node down the tree
      • When a call terminates, control goes back to the previous call, which resumes execution
        • BACKTRACKING

Recursion and Backtracking

  • Idea of backtracking:
    • Proceed forward to a solution until it becomes apparent that no solution can be achieved along the current path
      • At that point UNDO the solution (backtrack) to a point where we can again proceed forward
    • Example: 8 Queens Problem
      • How can I place 8 queens on a chessboard such that no queen can take any other in the next move?
        • Recall that queens can move horizontally, vertically or diagonally for multiple spaces
      • See on board

8 Queens Problem

    • 8 Queens Exhaustive Search Solution:
      • Try placing the queens on the board in every combination of 8 spots until we have found a solution
        • This solution will have an incredibly bad run-time
        • 64 C 8 = (64!)/[(8!)(64-8)!]
          • = (64*63*62*61*60*59*58*57)/40320
          • = 4,426,165,368 combinations
          • (multiply by 8 for total queen placements)
      • However, we can improve this solution by realizing that many possibilities should not even be tried, since no solution is possible
      • Ex: Any solution has exactly one queen in each column

8 Queens Problem

        • This would eliminate many combinations, but would still allow 88 = 16,777,216 possible solutions (x 8 = 134,217,728 total queen placements)
      • If we further note that all queens must be in different rows, we reduce the possibilities more
        • Now the queen in the first column can be in any of the 8 rows, but the queen in the second column can only be in 7 rows, etc.
        • This reduces the possible solutions to 8! = 40320 (x 8 = 322,560 individual queen placements)
        • We can implement this in a recursive way
      • However, note that we can prune a lot of possibilities from even this solution execution tree by realizing early that some placements cannot lead to a solution

8 Queens Problem

        • Ex: No queens on the same diagonal
        • See example on board
      • Using this approach we come up with the solution as shown in 8-Queens handout
        • JRQueens.java
      • Idea of solution:
        • Each recursive call attempts to place a queen in a specific column
          • A loop is used, since there are 8 squares in the column
        • For a given call, the state of the board from previous placements is known (i.e. where are the other queens?)
        • If a placement within the column does not lead to a solution, the queen is removed and moved "down" the column

8 Queens Problem

        • When all rows in a column have been tried, the call terminates and backtracks to the previous call (in the previous column)
        • If a queen cannot be placed into column i, do not even try to place one onto column i+1 – rather, backtrack to column i-1 and move the queen that had been placed there
        • Using this approach we can reduce the number of potential solutions even more
        • See handout results for details

Finding Words in a Boggle Board

    • Another example: finding words in a Boggle Board
      • Idea is to form words from letters on mixed up printed cubes
      • The cubes are arranged in a two dimensional array, as shown below
      • Words are formed by starting at any location in the cube and proceeding to adjacent cubes horizontally, vertically or diagonally
  • F
  • R
  • O
  • O
  • Y
  • I
  • E
  • S
  • L
  • D
  • N
  • T
  • A
  • E
  • R
  • E
  • Any cube may appear at most one time in a word
  • For example, FRIENDLY and FROSTED are legal words in the board to the right

Finding Words in a Boggle Board

      • This problem is very different from 8 Queens
      • However, many of the ideas are similar
      • But now the calls are in (up to) eight different directions:
        • For letter [i][j] we can recurse to
          • letter [i+1][j] letter [i-1][j]
          • letter [i][j+1] letter[i][j-1]
          • letter [i+1][j+1] letter[i+1][j-1]
          • letter [i-1][j+1] letter[i-1][j-1]
      • If we consider all possible calls, the runtime for this is enormous!
        • Has an approx. upper bound of 16!  2.1 x 1013

Download 186.06 Kb.

Share with your friends:
1   2   3   4   5   6   7   8   9   ...   24




The database is protected by copyright ©sckool.org 2020
send message

    Main page