Lecture By Dr. Baswana

Report
Data Structures and Algorithms
(CS210/ESO207/ESO211)
Lecture 12
•
Application of Stack and Queues
•
•
Shortest route in a grid with obstacles
8 queen’s problem
1
Problem 1
Shortest route in a grid with obstacles
2
Shortest route in a grid
From a cell in the grid, we can move to any of its neighboring cell in one step.
From top left corner, find shortest route to each cell avoiding obstacles.
3
The input grid is given as a Boolean matrix G such that
G[i,j] = 0 if (i,j) is an obstacle, and 1 otherwise.
3
Step 1:
Realizing the nontriviality of the problem
4
Shortest route in a grid
nontriviality of the problem
Definition: Distance of a cell c from another cell c’ is the length (number of steps) of
the shortest route between c and c’.
We shall design algorithm for computing distance of each cell from the start-cell.
As an exercise, you should extend it to a data structure for retrieving shortest route.
5
Get inspiration from nature
Did you ever notice the way ripples on the surface of
water travel in the presence of obstacles ?
The ripples travels along the shortest route ?
6
Shortest route in a grid
nontriviality of the problem
How to find the shortest route to
in the grid ?
Create a ripple at the start cell and trace
the path it takes to
7
Shortest route in a grid
propagation of a ripple from the start cell
8
Shortest route in a grid
ripple reaches cells at distance 1 after step 1
9
Shortest route in a grid
ripple reaches cells at distance 2 after step 2
10
Shortest route in a grid
ripple reaches cells at distance 3 after step 3
11
Shortest route in a grid
ripple reaches cells at distance 8 after step 8
Watch the next
few slides
carefully.
12
Shortest route in a grid
ripple reaches cells at distance 9 after step 9
13
Shortest route in a grid
ripple reaches cells at distance 10 after step 10
14
Shortest route in a grid
ripple reaches cells at distance 11 after step 11
15
Shortest route in a grid
ripple reaches cells at distance 12 after step 12
16
Shortest route in a grid
ripple reaches cells at distance 13 after step 13
17
Shortest route in a grid
ripple reaches cells at distance 14 after step 14
18
Shortest route in a grid
ripple reaches cells at distance 15 after step 15
19
Step 2:
Designing algorithm for distances in grid
(using an insight into propagation of ripple)
20
Shortest route in a grid
A snapshot of ripple after i steps

 : the cells of the grid at distance i from the starting cell.
21
Shortest route in a grid
A snapshot of the ripple after i+1 steps
 +
Can We generate
+ from  ?
22
How can we generate + from  ?
Observation: Each cell of + is a neighbor of a cell in  . But
every neighbor of  may be a cell of − or a cell of + .
Question: How to distinguish between a cell of − from + ?
Key idea: Suppose we initialize Distance[c] of each cell as ∞ in the start of the
algorithm; and set Distance[c] appropriately whenever the algorithm visits
(ripple reaches) c. Then just after our algorithm has visited  , for every
neighbor b of a cell in  ,
• If b is in − , Distance[b] = ??some number less than 
• If b is in + , Distance[b] =
?? ∞
Now can you use the above idea to design
an algorithm to generate + from  ?
23
Algorithm to compute + if we know 
Compute-next-layer(G,  )
{
CreateEmptyList(+ );
For each cell c in 
For each neighbor b of c which is not an obstacle
{
if (Distance[b] = ∞)
{
Insert(b, + );
Distance[b] i+1 ;
}
}
return + ;
}
24
The first (not so elegant) algorithm
(to compute distance to all cells in the grid)
Distance-to-all-cells(G, 0 )
It can be as high as
O( )
{   {0 };
For(i = 0 to ?? )
+  Compute-next-layer(G,  );
}
The algorithm is not elegant because of
• ??
• So many temporary lists that get created.
25
How to transform the algorithm to an elegant
algorithm ?
Key points we have observed:
• We can compute cells at distance i+1 if we know all cells up to distance i.
• Therefore, we need a mechanism to enumerate the cells of the grid in
non-decreasing order of distances from the start cell.
How to design such a
mechanism ?
26
Keep a queue Q

Q
+
27
An elegant algorithm
(to compute distance to all cells in the grid)
Distance-to-all-cells(G, 0 )
CreateEmptyQueue(Q);
Distance(0 )  0;
Enqueue(0 ,Q);
While( Not IsEmptyQueue(Q)
??
)
{
c Dequeue(Q);
For each neighbor b of c which is not an obstacle
{
if (Distance(b) = ∞)
Distance(c)
{ Distance(b) 
?? +1
;
Enqueue(b,??Q); ;
}
}
}
28
Proof of correctness of algorithm
Question: What is to be proved ?
Answer: At the end of the algorithm,
Distance[c]= the distance of cell c from the starting cell in the grid.
Question: How to prove ?
Answer: By the principle of mathematical induction on the distance from the
starting cell.
Inductive assertion:
P(i): The algorithm correctly computes distance to all vertices at distance i from the
starting cell.
As an exercise, try to prove P(i) by induction on i.
29
Problem 2
Placing 8 queens safely on a chess board
It was explained on the black board. However, for a
better understanding, the slides are also provided here.
30
8 queen problem
Find a way to place 8 queens on a chess board so that no two of them attack
each other.
31
First some notations and definitions are provided in order
• to have a better insight into the problem.
• to describe the idea underlying the algorithm compactly.
• to describe the algorithm in a formal manner.
32
A Configuration of 8 queens on chess board
where each row has exactly one queen
1
2
3
4
5
6
7
8
Q
8
Q
7
Q
6
Q
5
Q
4
Q
3
2
Q
1
Q
Each configuration can be specified by a vector <1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 >
where  is the column number of the queen placed in ith row.
For example, the above configuration can be represented by <1,1,3,4,6,4,8,7>
33
Configuration of 8 queens on chess board
where each row has exactly one queen
<1,1,3,4,6,4,8,7>
Most significant digit
Least significant digit
Lexicographic ordering: We can define a lexicographic ordering among all 
configurations. For example, <1,5,2,8,9,9,6,7> appears before
<2,1,1,1,1,1,1,2>.
Definition: A configuration of 8 queens is a safe configuration if no two
queens in the configuration attack each other.
Aim: To compute a safe configuration of 8 queens on a chess board.
34
To compute a safe configuration of 8 queens
A trivial solution: Enumerate all  configurations of 8 queens in
lexicographic ordering and then search this enumeration for a safe
configuration.
A clever approach: also searches for a safe configuration by exploring
configurations lexicographically but in a conservative manner as follows.
• Searches for a safe configuration in an incremental fashion :
placing queens one by one and cautiously.
• As soon as it is realized that a partial configuration is currently unsafe or
will only lead to unsafe configurations, it stops, backtracks, and tries the
next potential partial configuration.
(See animation on the following slide to get an idea)
35
A clever approach to search for safe configuration
An overview
1
2
3
4
5
8
6
7
8
Place queen of the 1st row in 1st column.
• It is unsafe to place second queen at
1st column or 2nd column of 2nd row.
 No need to generate configurations
<1,1,*,*,*,*,*,*> or <1,2,*,*,*,*,*,*>.
7
6
5
4
Q
3
Q
2
1
Q
So we proceed with <1,3,*,*,*,*,*,*>.
• All configurations with <1,3,k,*,*,*,*,*>
are unsafe for k<5.
 No need to generate these unsafe
configurations.
So we proceed with <1,3,5,*,*,*,*,*>.
… and so on …
36
A clever approach to search for safe configuration
An overview of general step
Let <1 , 2 , … ,  , ∗, ∗, ∗> be a safe
configuration of first i queens.
Because we are enumerating
configurations in lexicographic order
1
2
3
4
5
6
8
7
+
6

5
4
3
2
1 

7
8
We try to place queen + in the
leftmost safe position in i+1th row.
If such a position exists, we place +
and proceed to (i+2)th row.
If no safe position exists in i+1th row,
safe then <1 , 2 , … ,  , ∗, ∗, ∗> is unsafe.
To search for the next lexicographic
configuration which will be safe, we
search for the next leftmost safe position
for  in ith row.
37
Implementation of the clever approach
An important terminology:
Given a partial configuration of i queens placed on first i rows of the chess,
• A queen is said to be safe if it is not attacked by any other queen lying in
any row below it.
• A queen is said to be unsafe if it is attacked by at least one queen lying in
any row below it.
• A queen is uncertain if it is not known yet whether it is safe or unsafe.
Representation of a partial configuration:
Each queen in a partial configuration will be specified by a triplet <r,c,Flag>,
where r and c are the row and column of the cell where the queen is placed.
Flag is a variable which takes one of the values from {safe, unsafe, uncertain }
as explained above.
38
Implementation of the clever approach
A snapshot of the algorithm
At each stage, our algorithm will maintain a partial configuration
<1 , 2 , … ,  , +1 , ∗, ∗, ∗> where
• The first i queens are safe.
• The queen at i+1th place will be safe/unsafe/ uncertain
See the following slide for a visual description of a partial configuration at any stage of
our algorithm.
39
Implementation of the clever approach
A snapshot of the algorithm
safe/
Unsafe/
uncertain
+
+


safe


A step taken by our algorithm will depend upon the status of Flag of + .
Our approach of enumerating configurations in lexicographic order hints
at using a suitable data structure effectively. Can you guess it ?


stack S
For queens
40
A single step of the algorithm
Let the stack have  +  queens at present. We take out + .
(Answer the following questions to get a good understanding of the algo)
• If + is uncertain:
what should be done ?
We determine if it is attacked by any existing queen and change its
status as safe or unsafe accordingly, and push it back into stack.
• If + is safe:
what should be done ?
If  +  = , we are done; otherwise, push + back into the stack and
place a queen in the 1st column of ( + ) th row and mark it uncertain.
• If + is unsafe:
what should be done ?
We can shift + to the next available column. But if it was already in
8th column, we mark  unsafe.
41
Finally, The following slide has a simple and
elegant implementation of the clever approach
we discussed…
42
An elegant algorithm for 8 queens problem
CreateEmptyStack(S);
Push((1,1,safe), S);
While (Not IsEmptyStack(S)) do
{ (r,c,flag)  Top(S); Pop(S);
3 Cases:
{ Flag is uncertain : If ((r,c) does not attack any existing queen) Push((r,c,safe), S);
else Push((r,c,unsafe), S);
Flag is safe
: If (r = 8) { // we reached a safe configuration of 8 queens
print the solution and empty the stack S;
}
else
{ Push((r,c,safe), S); Push((r+1,1,uncertain), S)};
Flag is unsafe
: If (c = 8) {
(r’,c’,flag’)  Top(S); Pop(S);
Push((r’,c’,unsafe), S);
}
else Push((r,c+1, uncertain), S);
}
43
Homework exercises
1.
2.
3.
4.
5.
Now that you know the clever algorithm, give reason for pursuing
lexicographic approach in the search of a safe configuration by it.
Extend the algorithm for computing a safe configuration for n queens on
n by n chess board for any n.
The current algorithm finds just one safe configuration. Modify it to
enumerate all safe configurations.
If you love programming, implement the clever algorithm and trivial
algorithm and see if the clever algorithm is indeed mush faster than the
trivial algorithm.
We have given an iterative implementation of the clever algorithm. Can
you design a recursive implementation as well ? Which of them will be
faster in practical implementation, and why ?
44

similar documents