Transcript Y - HKOI
Recursion and Exhaustion Yip Lik Yau Page 1 Why Exhaustion? Many problems can be solved by brute force in a reasonable amount of time if the problem size is small Some problems have no known “fast” algorithm Estimating the time needed for brute force let us decide whether to use exhaustion or not Example: Traveling Salesman, Hamiltonian Path, Graph Isomorphism… Example: O(2N) is okay for N~30, O(N!) is okay for N~13 Knowing what types of problems are “hard” prevents you from wasting time in competitions Page 2 Problem: Generating Permutations Given N, generate all permutations of integers 1..N When N = 3: 123 132 213 231 312 321 Page 3 Problem: Generating Permutations Nested For loop is out of the question We need a more advanced method – recursion Outline of algorithm: var used : array[0..100] of boolean; n : integer; procedure run(stage : integer); begin if (level = n) do_something; else for i = 1 to n do if not used[i] begin used[i] = true; run(stage+1); used[i] = false; end; end; Page 4 Problem: Generating Permutations Search Tree 1 2 3 2 3 1 3 1 2 3 2 3 1 2 1 Page 5 Be Jewelled! ``Be Jewelled!'' is a popular Palm game. You are given 81 jewels arranged in a 9x9 matrix. Two adjacent jewels are allowed to be swapped if and only if, after the swapping, some jewels can be counted for scoring. You can make one such swapping and get score. The score is calculated according to the following rules: 1. If there are any three or more jewels of the same kind lined up horizontally, these jewels will be counted for scoring. 2. If there are any three or more jewels of the same kind lined up vertically, these jewels will be counted for scoring. If a jewel fulfils both rule 1 and 2, this jewel will count only once for scoring. The score gained = 5*3^(number of scoring jewelled-3) Page 6 Be Jewelled! P Q P Q P Q P Q P Q P Q Q P X Y X P Q P X X X P P Y Y X Y Q P Y Y Y Y Q Q Y Q Y Q P Q Y Q Y Q P P Q P Y P Q P Q P Y P Q Q P Q P Q P Q P Q P Q P Swapping the jewels in red. The jewels in red will be counted for score: 5*3^(9-3)=3645 Page 7 General Idea of Recursion To solve a problem, break it into smaller, similar instances Suppose we can solve the smaller instances, then combining these results can solve the original problem For the algorithm to terminate, we also need to know how to solve the base case Page 8 The N-Queens Problem In a NxN chessboard, place N queens so that no two of them can attack each other One brute force algorithm is to find all permutations of 1..N Example for N=3: permutation is 132, then we place the queens at (1,1), (2,3) and (3,2) The do_something at base case is to check whether 2 queens are attacking Q Q Q Q Q Q Q Q Optimization: when placing each queen, we can immediately check if it has violated the constraint Cuts off useless branches quickly Page 9 Estimating Time Complexity of Exhaustion The time complexity for the previous 2 algorithms are easy First stage has N choices, second stage has N-1 choices, … Total time = N*(N-1)*(N-2)*…*2*1 = N! If still not convinced, look at the search tree How about other problems? Start at the top-left corner, move to the bottom-right corner Each step can go down or right only Maximize sum of numbers in the path 1 5 4 2 5 6 9 2 8 1 4 7 6 1 4 2 4 3 1 2 Page 10 Two useful mathematical concepts Permutations (n P r) : number of ways to arrange r out of n objects with ordering 5 books, but only 3 slots on a bookshelf, how many permutations? The first slot has 5 choices The second slot has 4 choices The third slot has 3 choices Total number of permutations = 5*4*3 Formula : n P r = n! / (n-r)! Page 11 Two useful mathematical concepts Combinations (n C r) : number of ways to choose r out of n objects without ordering Mark Six has 49 numbers, draw 6 of them, how many combinations? The first ball has 49 choices The second ball has 48 choices … Total number of combinations = 49*48*47*46*45*44 However, 1 3 5 10 11 12 is just the same as 12 11 10 5 1 3, 10 5 1 3 11 12 or any of 6! permutations Therefore need to divide it by 6! Formula : n C r = n! / (n-r)! r! (n P r / r!) Property : n C r = n C (n-r) Choosing r items is equal to choosing which n-r items to leave out Page 12 Estimating Time Complexity of Exhaustion For the equation x1 + x2 + … + xk = s, where xi>=0, how many possible solutions? N people sit around a round table, how many permutations? (rotations of a permutation are considered the same) Answer = (s+k-1) C (k-1), why? Answer = (N-1)!, why? Return to the previous problem To get from the top-left to bottom-right, we need to make 7 moves (4 right, 3 down) This is equivalent to choosing 4 out of 7 items Answer = 7 C 4 (or generally, (width + height – 2) C height ) Page 13 Lexicographical Ordering The objects we permutate may have some “ordering” If such an ordering exists, we can extend it to an ordering between permutations Integers : 1 < 2 < 3 < … < N Alphabets : a < b < c < … < z 123 < 213 < 321 bdca < cabd < cbad < dcab This is called “lexicographical ordering” or “dictionary ordering” Page 14 Lexicographical Ordering Three natural questions to ask…… Given a permutation, determine its “next” permutation Find the Nth permutation (Deranking) 231 -> 312 3rd permutation of 1,2,3 = 213 Given a permutation, determine its position (Ranking) 132 -> position = 2 Page 15