Problems Solved By Greedy Method
This document was uploaded by user and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this DMCA report form. Report DMCA
Overview
Download & View Problems Solved By Greedy Method as PDF for free.
More details
- Words: 1,176
- Pages: 24
PROBLEMS SOLVED BY GREEDY METHOD Presented By:NEHA JAIN III-B.Tech CSE
The 2-terminal one to any special channel routing problem
The 2-terminal one to any special channel routing problem
Def:Given a set of terminals on the upper row and another set of terminals on the lower row, we have to connect each marked upper terminal to the marked lower row in a one to one fashion. This connection requires that No two lines can intersect. All lines are either vertical or horizontal (track).
2 feasible solutions
ACTUAL PROBLEM
TO minimize the # of tracks
SIMPLIFIED VERSION
At each point, the local density of the solution is # of lines
the vertical line intersects.
The problem: to minimize the density. The density is a lower bound of # of tracks.
Redrawing solutions
Optimal solution (density =1)
Another solution
Reaching the solution…
Upper row terminals: P1 ,P2 ,…, Pn from left to right Lower row terminals: Q1 ,Q2 ,…, Qm from left to right m > n. It would never have a crossing connection:
Assumption Suppose
that we have a method to determine minimum density, d, of a problem instance. Now we have to solve our problem greedily… If you were greedy you would always desire to have the minimum density. (Agreed?)
THE GREEDY ALGORITHM
Step 1: P1is connected Q1. Step 2 : After Pi is connected to Qj, we check whether Pi+1 can be connected to Qj+1. If the density is increased to d+1, try to Pi+1 to Qj+2.
connect
Step 3 : Repeat Step2 until all Pi’s are connected.
How greedy method helps??
We determine a minimum value parameter (local density) This is the value we try to optimize and then use the greedy method straightforwardly. The greedy algorithm connects the terminals greedily At any time our algorithm ensures that the resulting density does not exceed d
Minimum cooperative guards problem for 1-spiral polygons
ART GALLERY PROBLEM
Solution of the art gallery problem
We are given a polygon, which represents an art gallery, and we are required to place a minimum number of guards in the polygon such that every point of the polygon is visible to at least one guard.
Minimum cooperative guards problem
The minimum cooperative guards problem puts more constraint on the art gallery problem. Note that it may be quite dangerous for a guard to be stationed in an art gallery if he cannot be seen by any other guards. We represent the relationship among guards by a visibility graph G of the guards. In G, every guard is represented by a vertex and there is an edge between two vertices if and only if the corresponding guards can see each other. In addition to finding a minimum set of guards who can see the given polygo we further require that the visibility graph of these guards is connected. In other words, we require that no guard is isolated and there is a path between every pair of guards. We call such a problem the minimum cooperative guards problem.
Minimum cooperative guards problem….
A solution of the minimum cooperative guards problem for the polygon shown earlier
NOTATION
A reflex (convex) chain, denoted as RC (CC), of a simple polygon is a chain of edges of this polygon if all of the vertices on this chain are reflex (convex) with respect to the interior of the polygon, except the vertices at the end of the chain. The term “reflex chain” always refers to a maximal reflex chain; that is, it is not contained in any other reflex chain. A 1-spiral polygon P is a simple polygon whose boundary contains exactly one reflex chain. (Convex polygon is 0-spiral.)
CC
RC Vs Vs+1
Ve Ve-1
A typical 1-spiral polygon
NOTATION
Traversing the boundary of P counterclockwise, the starting (ending) vertex of the reflex chain is called vs, (ve) and the indices of vertices of P are numbered in increasing order.
A subchain of the boundary of P from point p to point q in counterclockwise order is denoted as C[p, q]. CC q
p
RC Vs Vs+1
Ve Ve-1
STARTING REGION, ENDING REGION CC
q
CC Ve-1
q
p
RC
p Vs Vs+1
starting region
Vs ending region
Ve Ve-1
Vs+1
starting region
Vs+1
RC
Ve-1
RC Vs
Ve
Ve
CC
ending region
For two points p and q on the convex (reflex) chain, we define p < q if p is closer to vs on the convex (reflex) chain than is q. There must be a guard standing in both the starting and ending regions.
Reaching the solution..
Place a guard at l1. We as how much can this guard see? To answer this draw a tangent line of RC starting from l1 and hitting at l2 on CC. Place a guard at l2. In the adjacent figure l1,l2,l3,l4,l5 constitute an optimal solution for the minimum cooperative guards problem.
Supporting line segment Let a be a point in P and b a point on CC of P. A line segment ab tangent at a reflex vertex c is called a left (right) supporting line segment with respect to a if there are exterior points of P to the right (left) of ab in every neighborhood of c. We call vertex c the contact vertex of ab. If a is in the starting (ending) region, we define the right (left) supporting line segment with respect to a as avs (ave) with vs (ve) as its contact vertex.
left supporting line with respect to a
CC c
a
RC
c
Vs
right supporting line with respect to a
b
b
a
CC c
RC
a Ve
c a b
b
ALGORITHM
Input a 1-spiral polygon Output a set of points which correspond to the solution of the minimum co-operative guards problem Step1 find the reflex chain RC and the convex chain CC of P. Step 2 find the intersection points l1 and l2 of CC with the directed lines starting from vs and ve along the first and last edges of RC, respectively. Step 3 let lk=1 while lk is not in the ending region do draw the left tangent of lk with respect to RC until it hits CC at lk+1. (lklk+1 is the left supporting line segment with respect to lk). end while step 4 report (l1,l2,….lk)
Analysis… Since the number of guards is minimal we conclude that our algorithm produces optimal solution. Time- complexity Analysis step 1 and step 2 can be done in O(n) time by a linear scan of the boundary of P. Step3- we conduct a linear scan on the reflex chain counterclockwise and on the convex chain clockwise to find all the required leftsupporting line-segments. This can also be done in O(n) time. Thus this algorithm is linear.
THANK YOU
The 2-terminal one to any special channel routing problem
The 2-terminal one to any special channel routing problem
Def:Given a set of terminals on the upper row and another set of terminals on the lower row, we have to connect each marked upper terminal to the marked lower row in a one to one fashion. This connection requires that No two lines can intersect. All lines are either vertical or horizontal (track).
2 feasible solutions
ACTUAL PROBLEM
TO minimize the # of tracks
SIMPLIFIED VERSION
At each point, the local density of the solution is # of lines
the vertical line intersects.
The problem: to minimize the density. The density is a lower bound of # of tracks.
Redrawing solutions
Optimal solution (density =1)
Another solution
Reaching the solution…
Upper row terminals: P1 ,P2 ,…, Pn from left to right Lower row terminals: Q1 ,Q2 ,…, Qm from left to right m > n. It would never have a crossing connection:
Assumption Suppose
that we have a method to determine minimum density, d, of a problem instance. Now we have to solve our problem greedily… If you were greedy you would always desire to have the minimum density. (Agreed?)
THE GREEDY ALGORITHM
Step 1: P1is connected Q1. Step 2 : After Pi is connected to Qj, we check whether Pi+1 can be connected to Qj+1. If the density is increased to d+1, try to Pi+1 to Qj+2.
connect
Step 3 : Repeat Step2 until all Pi’s are connected.
How greedy method helps??
We determine a minimum value parameter (local density) This is the value we try to optimize and then use the greedy method straightforwardly. The greedy algorithm connects the terminals greedily At any time our algorithm ensures that the resulting density does not exceed d
Minimum cooperative guards problem for 1-spiral polygons
ART GALLERY PROBLEM
Solution of the art gallery problem
We are given a polygon, which represents an art gallery, and we are required to place a minimum number of guards in the polygon such that every point of the polygon is visible to at least one guard.
Minimum cooperative guards problem
The minimum cooperative guards problem puts more constraint on the art gallery problem. Note that it may be quite dangerous for a guard to be stationed in an art gallery if he cannot be seen by any other guards. We represent the relationship among guards by a visibility graph G of the guards. In G, every guard is represented by a vertex and there is an edge between two vertices if and only if the corresponding guards can see each other. In addition to finding a minimum set of guards who can see the given polygo we further require that the visibility graph of these guards is connected. In other words, we require that no guard is isolated and there is a path between every pair of guards. We call such a problem the minimum cooperative guards problem.
Minimum cooperative guards problem….
A solution of the minimum cooperative guards problem for the polygon shown earlier
NOTATION
A reflex (convex) chain, denoted as RC (CC), of a simple polygon is a chain of edges of this polygon if all of the vertices on this chain are reflex (convex) with respect to the interior of the polygon, except the vertices at the end of the chain. The term “reflex chain” always refers to a maximal reflex chain; that is, it is not contained in any other reflex chain. A 1-spiral polygon P is a simple polygon whose boundary contains exactly one reflex chain. (Convex polygon is 0-spiral.)
CC
RC Vs Vs+1
Ve Ve-1
A typical 1-spiral polygon
NOTATION
Traversing the boundary of P counterclockwise, the starting (ending) vertex of the reflex chain is called vs, (ve) and the indices of vertices of P are numbered in increasing order.
A subchain of the boundary of P from point p to point q in counterclockwise order is denoted as C[p, q]. CC q
p
RC Vs Vs+1
Ve Ve-1
STARTING REGION, ENDING REGION CC
q
CC Ve-1
q
p
RC
p Vs Vs+1
starting region
Vs ending region
Ve Ve-1
Vs+1
starting region
Vs+1
RC
Ve-1
RC Vs
Ve
Ve
CC
ending region
For two points p and q on the convex (reflex) chain, we define p < q if p is closer to vs on the convex (reflex) chain than is q. There must be a guard standing in both the starting and ending regions.
Reaching the solution..
Place a guard at l1. We as how much can this guard see? To answer this draw a tangent line of RC starting from l1 and hitting at l2 on CC. Place a guard at l2. In the adjacent figure l1,l2,l3,l4,l5 constitute an optimal solution for the minimum cooperative guards problem.
Supporting line segment Let a be a point in P and b a point on CC of P. A line segment ab tangent at a reflex vertex c is called a left (right) supporting line segment with respect to a if there are exterior points of P to the right (left) of ab in every neighborhood of c. We call vertex c the contact vertex of ab. If a is in the starting (ending) region, we define the right (left) supporting line segment with respect to a as avs (ave) with vs (ve) as its contact vertex.
left supporting line with respect to a
CC c
a
RC
c
Vs
right supporting line with respect to a
b
b
a
CC c
RC
a Ve
c a b
b
ALGORITHM
Input a 1-spiral polygon Output a set of points which correspond to the solution of the minimum co-operative guards problem Step1 find the reflex chain RC and the convex chain CC of P. Step 2 find the intersection points l1 and l2 of CC with the directed lines starting from vs and ve along the first and last edges of RC, respectively. Step 3 let lk=1 while lk is not in the ending region do draw the left tangent of lk with respect to RC until it hits CC at lk+1. (lklk+1 is the left supporting line segment with respect to lk). end while step 4 report (l1,l2,….lk)
Analysis… Since the number of guards is minimal we conclude that our algorithm produces optimal solution. Time- complexity Analysis step 1 and step 2 can be done in O(n) time by a linear scan of the boundary of P. Step3- we conduct a linear scan on the reflex chain counterclockwise and on the convex chain clockwise to find all the required leftsupporting line-segments. This can also be done in O(n) time. Thus this algorithm is linear.
THANK YOU
Related Documents
Problems Solved By Greedy Method
November 2019 8
Solved-problems-in-soil-mechanics.pdf
November 2019 10
Greedy-methods
July 2020 8
Greedy Proofs
May 2020 8
L12 (greedy)
July 2020 6