CSCI103 03a Strategy_BruteForce(print)4

1 CSCI103 Spring 2010 Algorithms and Problem Solving (S3a) Illustrating the need for strategies: Brute force vs finesse Brute Force vs. Finesse • Often, the “easy” way to solve a problem (or to think  of solving a problem) is to list all possible answers  and select the best one, one of the correct ones, or  the only correct one. – This is a brute force approach– This is a brute force approach. • However, this will generally involve far more work  than is strictly needed. • The following problems will illustrate this idea. • We will also see the significance of invariants again,  and begin to see how to use some notation. Problem 1: Crossing the river • A Farmer has a wolf, a goat and a cabbage and  must cross a river using a small boat. – Only two things will fit in the boat at a time, and  this includes the farmer! – Without the supervision of the farmer, the wolf  will eat the goat. – Without the supervision of the farmer, the goat  will eat the cabbage. • We want to get everything safely across the  river. • Let us look at using a brute force approach first  of all. • What do we do? 1. We list all possible configurations. 2 We eliminate the illegal ones2. We eliminate the illegal ones. 3. We find a sequence of configurations starting at the  initial state and ending at the goal state. If we were being really “brutal”, we might not even  make the sensible choice of eliminating the illegal  configurations. 2 States… • Stepping back a bit we know our start state, – All on the first bank, bank 0. • and we know our goal state, – All on the second bank, bank 1. • In step 1 we construct all intermediate states as a  i f l ti f h ti i tmix of locations for each participants. • In step 2 we eliminate those that would result in  something getting eaten. ☺ • In step 3 we are looking for an evolution between  allowed states that in consistent with the allowed  operation, that is only two entities in the boat at a  time. • List all possible configurations. • How many are there? – Each of the four entities can be in one of two places,  so 24=16. • We will use some abbreviations: – F=Farmer, W=Wolf, G=Goat, C=Cabbage 0 0 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 0 1 0 1 0 1 0 0 1 1 0 1 1 1 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 0 1 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1 1 F W G C Some notes on the table… • We have listed the numbers 0 to 15, in base 2. – Is there any real value in actually giving a label to  each of the states in that range? – Well it is a concise representation but we shouldWell, it is a concise representation but we should  be very cautious trying to assign any “physical  meaning” to those overall values. • Each column pair (c,15‐c) is mirrored under  the replacement 0ÅÆ1. Invariants and invalid states • The goat will eat the cabbage unless: – The farmer, goat and cabbage are all on the same bank (F = G =  C) or … – The goat and the cabbage are on different banks (G ≠ C). • Formally we could write this as y (F = G = C) ∨ (G ≠ C) where ∨means OR.  • Similarly, the wolf will eat the goat unless: (F = W = G) ∨ (W ≠ G) • Overall: ((F = G = C) ∨ (G ≠ C)) ∧ ((F = W = G) ∨ (W ≠ G)) where ∧means AND. 3 • We could simplify the expression… ((F = G = C) ∨ (G ≠ C)) ∧ ((F = W = G) ∨ (W ≠ G)) ((F = G) ∨ (G ≠ C)) ∧ ((F = G) ∨ (W ≠ G))((F = G) ∨ (G ≠ C)) ∧ ((F = G) ∨ (W ≠ G)) ((F = G) ∨ ((G ≠ C) ∧ (W ≠ G))) • ∨means OR and ∧means AND • Going back to our table, the next step is to  eliminate the invalid states. • Notice we have eliminated mirror pairs. 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 0 0 1 0 0 1 1 1 F W 0 0 0 0 0 0 1 0 0 1 0 0 0 1 0 0 1 0 1 1 0 1 1 0 0 0 1 0 0 1 1 0 1 1 0 1 0 1 1 0 1 1 1 1 1 1 1 1 W G C Fat wolf Fat goat Very fat wolf? • Now we need to find a sequence of configurations starting at  the initial state (0000) and ending at the goal state (1111). • We can draw up the valid states and look at the available  paths. • An aside: • Given that we have four parameters it would be useful to  have a four dimensional space with which to represent the  states. – We have four dimensions readily available but representing them on  h hi b d ’ b /the whiteboard won’t be easy / • Actually, we can represent the states of the four dimensional  state by considering pairs of two‐dimensional states, and we  can draw this on the flat board by considering an “inner” two‐ dimensional vector at each “outer” two‐dimensional location. 4 • So here go our solutions in terms of states: 0000 1010 0010 1101 0101 1111 1110 0100 FWGC 1011 0001 „ Are these the only two solutions? „ If not, is there a better solution? – What do we mean by better? Some thoughts on brute force • There is often a tendency to apply brute force  without thinking when faced with a new problem.  – However, brute force should only be used where it is  unavoidable or where the effort is small even with brute  force.  • Brute force is only useful for “very simple” problems.  – Otherwise the search space quickly becomes much too  large. – Effectively we are making the term “very simple”  synonymous with the concept of a small search space. Not  completely appropriate, consider a single guess at a  integer in the range 1 to 100 inclusive. • In the jargon used by computing scientists, brute force  does not scale up to larger problems.  • The goat‐cabbage‐wolf‐problem is not representative;  the thoughtless solution has a manageable number of  states, and a manageable number of transitions. W h i kl th h b l i– We can see how quickly the search space can grow by analyzing  what is involved in using brute force to solve bigger problems  such as the jealous husband problem we will look at soon. • Brute force is still important though, in particular we are  considering a problem with a size parameter n and the  small cases can be brute forced to try and obtain some  insight into the structure of the problem or the solution  to the problem. Problem 1a: Crossing the river with finesse • Observe that the wolf and cabbage are not  threats to each other.  – The goat is a “problem” with either. • We rephrase the problem to recognise that the  wolf and cabbage can be abstracted. • A Farmer has two alphas and a beta and must  safely transport them across a river using a small  boat. – Only two things will fit in the boat at a time. – An alpha and a beta may never be left alone together. 5 After this abstraction … • …  the single invariant is: (F = α = β) ∨ (α ≠ β) • We have to be a little careful with what the variables  represent, since there are now two alphas. • The solution should now be easier to recognise than before. k h b• Farmer takes the beta over. • Comes back on his own. • Takes an alpha. • Returns with the beta. • Takes the other alpha. • Comes back on his own. • Takes the beta. Problem 2: Crossing the river again • Three couples (husband and wife) wish to  cross a river using a small boat. • Only two people will fit in the boat at a time. • Each husband is too jealous to leave his wifeEach husband is too jealous to leave his wife  with another man, even if his wife is present. • Get everyone safely across the river. Brute force on the Jealous Husbands • Recall that we begin by determining all possible  configurations, and then eliminate the ones we need to  avoid. • How many possible configurations are there? – Each of six persons in two possible places Æ 26=64. – 64 isn’t actually too bad for configuration listing, at least not if we64 isn t actually too bad for configuration listing, at least not if we  had a computer to help. ☺ – However, if a similar problem involved 60 people in one of two  states we are going to have trouble even with a computer. / • We call this the “State Space Explosion”, and we have an  unmanageable number of states and transitions. • Clearly the brute force approach quickly becomes  unattractive. / • So we need to find a finesse solution. What is the Problem? • We can look at the problem in more than one  way. – 3 couples must cross. – 3 wives and 3 husbands must cross. – 6 people must cross. • Some ways are more useful than others. – Notice in particular that the wives and husbands  are not equivalent. • Wives don’t get jealous so we can leave a husband with  a couple, but we cannot leave a wife with a couple. 6 • Several possible strategies suggest  themselves: – Get all the wives across first. Get all the husbands across first– Get all the husbands across first. – Get one couple across at a time. • Can we make use of symmetry and solve only  half the problem? Representing states • We need a good notation to represent  positions (states) in the problem. • We do not need to identify individual people. – In some problems we might need to.In some problems we might need to. • We have three types of thing to deal with. – Couples. Æ c – Husbands. Æ h – Wives. Æ w • Thus: – 3c represents 3 couples on one bank.  – 2ch represents 2 couples and a husband. • The unspecified wife is on the other bank. – 2w represents two wives. • What will be on the other bank? • 2ch or c2h? • We can represent a state in the problem using a  notation of the form  {L || R} where L and R { || } represent the current contents of the left (L, initial)  and right (R, final) bank respectively. • Thus: – {3c ||   } is the initial state; – {   || 3c} is the goal state. – {2h || c2w} might be an intermediate state. • Although it’s actual illegal since the husbands will be jealous. Representing moves • We can represent moves by using a notation  of the form {L | B | R} where L and R have the  same meanings as before and B is the  contents of the boatcontents of the boat. • The following are some valid moves: – {c | c | c} – {2ch | w | w} – {3h | 2w | w} 7 The boat? • What about the boat? • If we have the move {c | c | c} it is obvious where the  boat is, but where is it going? • We could add some notation to tell us … • So {c| c*| c} means the boat is going to the right• So {c| c | c} means the boat is going to the right. • So {c|* c| c} means the boat is going to the left. • Do we need this? – If we have a sequence of states or moves we can work out  which way the boat is going by looking at the before and  after moves. – Adding the stars (or something else) might clarify things  though! And the states? • Again, a sequence of states will allow us to determine  where a boat is at a particular point. • However we could be more complete with our notation  and include the boat location in the state representation. • So our starting configuration will be {3c *|| }{3c  ||   } • Do we need this information? – What if we started with {3c ||* }? • The position of the boat is critical to being able to string  our configurations together, but sometimes too much  notation can obscure important details. – In particular the positioning of the people in configurations is  independent of where the boat is at a particular time. Variables and invariants • We use C, H and W to represent the total number of  couples, husbands (without wives) and wives  (without husbands) present across both banks. • There are always between 0 and 3 couples present. – 0 ≤ C ≤ 3 Both our start and end states have C=3– Both our start and end states have C=3. • The husbands must be somewhere, we have “The  Law of Conservation of Husbands”. – C + H = 3 • The wives must be somewhere, we have “The Law of  Conservation of Wives”. – C + W = 3 • Combining the last two we see that H = W = 3‐C. An Aside: Conservation, invariants and symmetry • Roughly, a continuous symmetry implies an invariant  or conserved quantity. • Formal symmetry isn’t the focus of this subject but it  is an important concept. • Here go some examples: R t ti l t Æ C ti f A l• Rotational symmetry Æ Conservation of Angular  momentum. – It’s not rotational symmetry of an object, it’s invariance of  the physical laws (the dynamics) under such rotations! • Classically, conservation of linear momentum arises  from the invariance of physical laws under spatial  translations, while energy conservation arises from  the invariance under temporal translations. 8 Illegal states and moves • States in which couples are present with wives, … {2cw || h}, {cw || ch}, {c2w || 2h}, … , are all forbidden (independent of where the boat is). • Moves must obey these rules with the additional  rule that the boat can only take 2 people. – The allowed values are thus h, c, w, 2h and 2w. – And this is independent of which way the boat is  going. State Transitions  • We denote a transition between two states, the  result of a move, by the notation: {p} m {q} • Where: { } i h b f h{p} is the state before the move, {q} is the state after the move, and m is the move.  • If we list state transitions the boat location and the  direction will be apparent anyway. Composite Transitions  • We can combine moves as follows: – If {p0} m1 {p1} and {p1} m2 {p2}  then we can write {p0} m1, m2 {p2}. • In general we write: {p} S {q} where S is a sequence of individual moves. Restating the problem • The problem can now be written as: Find a sequence of moves, S, so that, {3c ||  } S {  || 3c}. • We can decompose this to the following• We can decompose this to the following  symmetric sub‐problems. • Find S1, S2 and S3 such that: {3c  ||      }  S1  {3h  || 3w} {3h  || 3w}  S2  {3w ||  3h} {3w ||  3h}  S3  {      ||  3c}. 9 Restating the problem • We now have three smaller problems: – Getting the wives across (S1). – Swapping the husbands and wives (S2). Getting the wives across again (S )– Getting the wives across again (S3). • S3 will simply be the reverse of S1 so we do not  have to find it as well. The sequence S1 • We need {3c || } S1 {3h || 3w} Think about what moves are possible here. S is {c2h | 2w| }S1 is  {c2h | 2w| } {c2h || 2w} {c2h | w | w} {2ch || w} {3h | 2w | w} S3 will then be the mirror image of S1. Finding S2 • If we keep assuming that we are going to have  a symmetric solution, we need to find two  sequences T1 and T2 so that  {3h || 3w} T {c | c | c} T {3w || 3h}{3h || 3w} T1 {c | c | c} T2 {3w || 3h} • Again, T2 will simply be the reverse of T1. • So let us look at the structure of T2. Finding T1 • The middle move, {c | c | c}, can be interpreted in  two ways: – The couple is crossing left‐to‐right; {2c || c} {c | c | c} {c || 2c} The couple is crossing right to left– The couple is crossing right‐to‐left. {c || 2c} {c | c | c} {2c || c} • We do not yet know which is the case. • We need to find a set of moves which gets from {3h  || 3w} to one of these two states ({c || 2c} or {2c ||  c}). 10 The sequence T1 • We need {3h || 3w} T1 {c || 2c}  or  {3h || 3w} T1 {2c || c} T1 is  {3h | w | 2w}1 { | | } {c2h || 2w} {c | 2h | 2w} {c || 2c} T2 should be the mirror image of T1.