-
Notifications
You must be signed in to change notification settings - Fork 1
/
Search Techniques.html
322 lines (257 loc) · 14.5 KB
/
Search Techniques.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
<!-- saved from url=(0053)http://train.usaco.org/usacotext2?a=zWju1un286A&S=rec -->
<html><head><meta http-equiv="Content-Type" content="text/html; charset=windows-1252"><title>Search Techniques
</title>
</head><body bgcolor="#f0f0f0">
<font face="Verdana,Tahoma,sans-serif,Arial,Lucida Sans,Gill Sans">
<div style="width:45em;background-color:white;border-style:solid;border-width:1px;padding:1em;">
<table cellspacing="8">
<tbody><tr><td><img src="./Search Techniques_files/cowhead2.gif"></td>
<td> </td>
<td><b><font size="5">
<font face="Verdana,Tahoma,sans-serif,Arial,Lucida Sans,Gill Sans">
Search Techniques
</font></font></b></td>
</tr>
</tbody></table>
<h4>Sample Problem: <i>n</i> Queens [Traditional]</h4>
<p>Place <i>n</i> queens on an <i>n x n</i> chess board so
that no queen is attacked by another queen.
</p><h4> Depth First Search (DFS) </h4>
<p> The most obvious solution to code is to add queens recursively
to the board one by one, trying all possible queen placements. It
is easy to exploit the fact that there must be exactly one queen
in each column: at each step in the recursion, just choose where
in the current column to put the queen.
<br>
<tt><font size="2"> <br>
1 search(col)<br>
2 if filled all columns<br>
3 print solution and exit <br><br>
4 for each row<br>
5 if board(row, col) is not attacked<br>
6 place queen at (row, col)<br>
7 search(col+1)<br>
8 remove queen at (row, col)<br>
</font></tt>
</p><p>Calling <tt><font size="2"> search(0)</font></tt> begins the search. This
runs quickly, since there are relatively few choices at each step:
once a few queens are on the board, the number of non-attacked
squares goes down dramatically.
</p><p> This is an example of <i>depth first search</i>, because the
algorithm iterates down to the bottom of the search tree as quickly
as possible: once <i>k</i> queens are placed on the board, boards
with even more queens are examined before examining other possible
boards with only <i>k</i> queens. This is okay but sometimes it
is desirable to find the simplest solutions before trying more
complex ones.
</p><p> Depth first search checks each node in a search tree for some
property. The search tree might look like this:
<br><img src="./Search Techniques_files/rec.tree1.gif"><br>
The algorithm searches the tree by going down as far as possible
and then backtracking when necessary, making a sort of outline of
the tree as the nodes are visited.
Pictorially, the tree is traversed in the following manner:
<br><img src="./Search Techniques_files/rec2.gif"><br>
</p><h5>Complexity</h5>
<p> Suppose there are <i>d</i> decisions that must be made. (In
this case <i>d=n</i>, the number of columns we must fill.) Suppose
further that there are C choices for each decision. (In this case
<i>c=n</i> also, since any of the rows could potentially be chosen.)
Then the entire search will take time proportional to <i>c<sup>d</sup></i>,
i.e., an exponential amount of time. This scheme requires little
space, though: since it only keeps track of as many decisions as
there are to make, it requires only O(<i>d</i>) space.
</p><h4>Sample Problem: Knight Cover [Traditional]</h4>
<p> Place as few knights as possible on an <i>n x n</i> chess
board so that every square is attacked. A knight is not considered
to attack the square on which it sits.
</p><h5>Breadth First Search (BFS)</h5>
<p> In this case, it is desirable to try all the solutions with
only <i>k</i> knights before moving on to those with <i>k+1</i> knights.
This is called <b>breadth first search</b>. The usual way to
implement breadth first search is to use a queue of states:
<br>
<tt><font size="2"> <br>
1 process(state)<br>
2 for each possible next state from this one<br>
3 enqueue next state <br><br>
4 search()<br>
5 enqueue initial state<br>
6 while !empty(queue)<br>
7 state = get state from queue<br>
8 process(state)<br>
</font></tt>
</p><p> This is called breadth first search because it searches an
entire row (the breadth) of the search tree before moving on to
the next row. For the search tree used previously, breadth first
search visits the nodes in this order:
<br><img src="./Search Techniques_files/rec3.gif"><br>
It first visits the top node, then all the nodes at level 1, then
all at level 2, and so on.
</p><h5>Complexity</h5>
<p>Whereas depth first search required space proportional to the
number of decisions (there were <i>n</i> columns to fill in the
<i>n</i> queens problem, so it took O(<i>n</i>) space), breadth
first search requires space exponential in the number of choices.
</p><p>If there are <i>c</i> choices at each decision and <i>k</i>
decisions have been made, then there are <i>c <sup> k</sup></i>
possible boards that will be in the queue for the next round. This
difference is quite significant given the space restrictions of
some programming environments.
</p><p>[Some details on why <i>c<sup>k</sup>: Consider the nodes in the
recursion tree. The zeroeth level has 1 nodes. The first level
has c nodes. The second level has c<sup>2</sup> nodes, etc. Thus,
the total number of nodes on the k-th level is c<sup>k</sup></i>.]
</p><h5>Depth First with Iterative Deepening (ID)</h5>
<p> An alternative to breadth first search is <i>iterative
deepening</i>. Instead of a single breadth first search, run D
depth first searches in succession, each search allowed to go one
row deeper than the previous one. That is, the first search is
allowed only to explore to row 1, the second to row 2, and so on.
This ``simulates'' a breadth first search at a cost in time but a
savings in space.
<br>
<tt><font size="2"> <br>
1 truncated_dfsearch(hnextpos, depth)<br>
2 if board is covered<br>
3 print solution and exit <br><br>
4 if depth == 0<br>
5 return <br><br>
6 for i from nextpos to n*n<br>
7 put knight at i<br>
8 truncated_dfsearch(i+1, depth-1)<br>
9 remove knight at i <br><br>
10 dfid_search<br>
11 for depth = 0 to max_depth<br>
12 truncated_dfsearch(0, depth)<br>
</font></tt>
</p><h5>Complexity</h5>
<p> The space complexity of iterative deepening is just the space
complexity of depth first search: O(<i>n</i>). The time complexity,
on the other hand, is more complex. Each truncated depth first
search stopped at depth <i>k</i> takes <i>c<sup>k</sup></i> time.
Then if <i>d</i> is the maximum number of decisions, depth first
iterative deepening takes <i>c<sup>0</sup> + c<sup>1</sup>
+ c<sup>2</sup> + ... + c<sup>d</sup></i> time.
</p><p> If <i>c = 2</i>, then this sum is <i>c<sup>d+1</sup> - 1</i>,
about twice the time that breadth first search would have taken.
When <i>c</i> is more than two (i.e., when there are many choices
for each decision), the sum is even less: iterative deepening cannot
take more than twice the time that breadth first search would have
taken, assuming there are always at least two choices for each
decision.
</p><h4>Which to Use?</h4>
<p> Once you've identified a problem as a search problem, it's
important to choose the right type of search. Here are some things
to think about.
</p><h5>In a Nutshell </h5>
<center>
<table>
<tbody><tr><td>Search</td> <td>Time</td> <td>Space</td> <td>When to use</td></tr>
<tr><td>DFS</td> <td>O(<i>c<sup>k</sup></i>)</td><td>O(<i>k</i>)</td><td>Must search tree anyway, know the level the answers are on, or
you aren't looking for the shallowest number.</td></tr>
<tr><td>BFS</td> <td>O(<i>c<sup>d</sup></i>)</td><td>O(<i>c<sup>d</sup></i>)</td> <td>Know answers are very near top of tree, or want shallowest answer.</td></tr>
<tr><td>DFS+ID</td> <td>O(<i>c<sup>d</sup></i>)</td> <td>O(<i>d</i>)</td> <td>Want to do BFS, don't have enough space, and can spare the time.</td></tr>
</tbody></table>
</center>
<i>d</i> is the depth of the answer
<br>
<i>k</i> is the depth searched
<br>
<i>d <= k</i>
<p> Remember the ordering properties of each search. If the
program needs to produce a list sorted shortest solution first
(in terms of distance from the root node), use breadth first search
or iterative deepening. For other orders, depth first search is
the right strategy.
</p><p> If there isn't enough time to search the entire tree, use the
algorithm that is more likely to find the answer. If the answer
is expected to be in one of the rows of nodes closest to the root,
use breadth first search or iterative deepening. Conversely, if
the answer is expected to be in the leaves, use the simpler depth
first search.
</p><p> Be sure to keep space constraints in mind. If memory is
insufficient to maintain the queue for breadth first search but
time is available, use iterative deepening.
</p><h4>Sample Problems</h4>
<h5>Superprime Rib [USACO 1994 Final Round, adapted]</h5>
<p> A number is called superprime if it is prime and every number
obtained by chopping some number of digits from the right side of
the decimal expansion is prime. For example, 233 is a superprime,
because 233, 23, and 2 are all prime. Print a list of all the
superprime numbers of length <i>n</i>, for <i>n <= 9</i>. The
number 1 is not a prime.
</p><p> For this problem, use depth first search, since all the answers
are going to be at the <i>n</i>th level (the bottom level) of the
search.
</p><h5>Betsy's Tour [USACO 1995 Qualifying Round]</h5>
<p>A square township has been partitioned into <i>n <sup> 2</sup></i>
square plots. The Farm is located in the upper left plot and the
Market is located in the lower left plot. Betsy takes a tour of
the township going from Farm to Market by walking through every
plot exactly once. Write a program that will count how many unique
tours Betsy can take in going from Farm to Market for any value of
<i>n <= 6</i>.
</p><p> Since the number of solutions is required, the entire tree must
be searched, even if one solution is found quickly. So it doesn't
matter from a time perspective whether DFS or BFS is used. Since
DFS takes less space, it is the search of choice for this problem.
</p><h5>Udder Travel [USACO 1995 Final Round; Piele]</h5>
<p> The Udder Travel cow transport company is based at farm A and
owns one cow truck which it uses to pick up and deliver cows between
seven farms A, B, C, D, E, F, and G. The (commutative) distances
between farms are given by an array. Every morning, Udder Travel
has to decide, given a set of cow moving orders, the order in which
to pick up and deliver cows to minimize the total distance traveled.
Here are the rules:
</p><ul>
<li>The truck always starts from the headquarters at farm A and must return
there when the day's deliveries are done.</li>
<li>The truck can only carry one cow at a time.</li>
<li>The orders are given as pairs of letters denoting where a cow is to be
picked up followed by where the cow is to be delivered.</li>
</ul>
<p> Your job is to write a program that, given any set of orders,
determines the shortest route that takes care of all the deliveries,
while starting and ending at farm A.
</p><p> Since all possibilities must be tried in order to ensure the
best one is found, the entire tree must be searched, which takes
the same amount of time whether using DFS or BFS. Since DFS uses
much less space and is conceptually easier to implement, use that.
</p><h5>Desert Crossing [1992 IOI, adapted]</h5>
<p> A group of desert nomads is working together to try to get one
of their group across the desert. Each nomad can carry a certain
number of quarts of water, and each nomad drinks a certain amount
of water per day, but the nomads can carry differing amounts of
water, and require different amounts of water. Given the carrying
capacity and drinking requirements of each nomad, find the minimum
number of nomads required to get at least one nomad across the
desert.
</p><p> All the nomads must survive, so every nomad that starts out
must either turn back at some point, carrying enough water to get
back to the start or must reach the other side of the desert.
However, if a nomad has surplus water when it is time to turn back,
the water can be given to their friends, if their friends can carry
it.
</p><p> Analysis: This problem actually is two recursive problems: one
recursing on the set of nomads to use, the other on when the nomads
turn back. Depth-first search with iterative deepening works well
here to determine the nomads required, trying first if any one can
make it across by themselves, then seeing if two work together to
get across, etc.
</p><h5>Addition Chains</h5>
<p> An addition chain is a sequence of integers such that the first
number is 1, and every subsequent number is the sum of some two
(not necessarily unique) numbers that appear in the list before
it. For example, 1 2 3 5 is such a chain, as 2 is 1+1, 3 is 2+1,
and 5 is 2+3. Find the minimum length chain that ends with a given
number.
</p><p> Analysis: Depth-first search with iterative deepening works
well here, as DFS has a tendency to first try 1 2 3 4 5 ... n,
which is really bad and the queue grows too large very quickly for
BFS.
</p></div><br>
<center>
<a href="http://train.usaco.org/usacogate?a=zWju1un286A">USACO Gateway</a> | <a href="mailto:rob.kolstad@gmail.com">Comment or Question</a>
</center>
</font></body></html>