Re: [algogeeks] Re: Shortest path in grid with dynamic programming.
BFS might be faster, though.
Don
On Tuesday, April 22, 2014 1:11:00 AM UTC-4, bujji wrote:
Hi Don,
At most we can reach a point from 4 adjacent points. So,
time complexity will be O(XY) only.
-Thanks,
Bujji.
On Mon, Apr 21, 2014 at 1:38 PM, bujji jajala jajal...@gmail.comjavascript:
wrote:
Hi Don,
Nice solution. good. Looks like in your markShortestPath(int
i, int i, int d) function
you missed to set distance[i][j] = d; as first statement.
It looks like time complexity of this program is greater than O(XY). It
depends on number of multiple paths
to a point with different path lengths and order of evaluation of
paths.Evaluating recursion paths from greater
run length to smaller run lengths will result in updating distance[i][j]
several times.
Any improvements can we think of to improve this to achieve O(XY) bound?
-Thanks
Bujji.
On Mon, Apr 21, 2014 at 10:01 AM, Don dond...@gmail.com javascript:wrote:
bool bad[X][Y];
int distance[X][Y];
void markShortestPath(int i, int i, int d)
{
if ((i = 0) (j = 0) (i X) (j Y) (distance[i][j]
d) !bad[i][j])
{
markShortestPath(i+1, j, d+1);
markShortestPath(i-1, j, d+1);
markShortestPath(i, j+1, d+1);
markShortestPath(i, j-1, d+1);
}
}
void findShortestPath()
{
int i,j;
for(i = 0; i X; ++i)
for(j = 0; j Y; ++j)
distance[i][j] = 10;
markShortestPath(X-1, Y-1, 0);
if (distance[0][0] == 10)
{
printf(No path exists\n);
return;
}
i = j = 0;
printf(Start at (0,0)\n);
while(distance[i][j])
{
if (distance[i+1][j] == distance[i][j]-1) ++i;
else if (distance[i-1][j] == distance[i][j]-1) --i;
else if (distance[i][j+1] == distance[i][j]-1) ++j;
else if (distance[i][j-1] == distance[i][j]-1) --j;
printf(Move to (%d, %d)\n, i,j);
}
}
On Monday, April 21, 2014 11:08:55 AM UTC-4, Don wrote:
Create a matrix distance[x][y] and set all values to a large number.
This will represent the distance to travel to the destination on the
shortest route.
Now set the distance at the destination to zero.
Set all adjacent locations to one, and repeat the process recursively,
always setting valid adjacent locations with a larger distance value to
the
distance from the current location plus one. In the end, you will have the
distance from every location on the grid. Now you can find the shortest
path from any location by always moving to a space which is closer than
your current location.
Don
On Sunday, April 20, 2014 11:52:44 AM UTC-4, bujji wrote:
Consider a city whose streets are defined by an X ×Y grid. We are
interested in
walking from the upper left-hand corner of the grid to the lower
right-hand corner.
Unfortunately, the city has bad neighborhoods, whose intersections we
do not want
to walk in. We are given an X × Y matrix BAD, where BAD[i,j] = “yes”
if and
only if the intersection between streets i and j is in a neighborhood
to avoid.
Give an O(XY ) algorithm to find the shortest path across the grid
that avoids
bad neighborhoods. You may assume that all blocks are of equal length.
For partial
credit, give an O(X^2 Y^2) algorithm.
If we walk in down or right directions only Dynamic programming
solution would be simple. But because of bad intersection points, we may
need to walk in up, down, right or left directions.
-Thanks
Bujji
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send
an email to algogeeks+...@googlegroups.com javascript:.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Shortest path in grid with dynamic programming.
Create a matrix distance[x][y] and set all values to a large number. This will represent the distance to travel to the destination on the shortest route. Now set the distance at the destination to zero. Set all adjacent locations to one, and repeat the process recursively, always setting valid adjacent locations with a larger distance value to the distance from the current location plus one. In the end, you will have the distance from every location on the grid. Now you can find the shortest path from any location by always moving to a space which is closer than your current location. Don On Sunday, April 20, 2014 11:52:44 AM UTC-4, bujji wrote: Consider a city whose streets are defined by an X ×Y grid. We are interested in walking from the upper left-hand corner of the grid to the lower right-hand corner. Unfortunately, the city has bad neighborhoods, whose intersections we do not want to walk in. We are given an X × Y matrix BAD, where BAD[i,j] = “yes” if and only if the intersection between streets i and j is in a neighborhood to avoid. Give an O(XY ) algorithm to find the shortest path across the grid that avoids bad neighborhoods. You may assume that all blocks are of equal length. For partial credit, give an O(X^2 Y^2) algorithm. If we walk in down or right directions only Dynamic programming solution would be simple. But because of bad intersection points, we may need to walk in up, down, right or left directions. -Thanks Bujji -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Shortest path in grid with dynamic programming.
bool bad[X][Y];
int distance[X][Y];
void markShortestPath(int i, int i, int d)
{
if ((i = 0) (j = 0) (i X) (j Y) (distance[i][j] d)
!bad[i][j])
{
markShortestPath(i+1, j, d+1);
markShortestPath(i-1, j, d+1);
markShortestPath(i, j+1, d+1);
markShortestPath(i, j-1, d+1);
}
}
void findShortestPath()
{
int i,j;
for(i = 0; i X; ++i)
for(j = 0; j Y; ++j)
distance[i][j] = 10;
markShortestPath(X-1, Y-1, 0);
if (distance[0][0] == 10)
{
printf(No path exists\n);
return;
}
i = j = 0;
printf(Start at (0,0)\n);
while(distance[i][j])
{
if (distance[i+1][j] == distance[i][j]-1) ++i;
else if (distance[i-1][j] == distance[i][j]-1) --i;
else if (distance[i][j+1] == distance[i][j]-1) ++j;
else if (distance[i][j-1] == distance[i][j]-1) --j;
printf(Move to (%d, %d)\n, i,j);
}
}
On Monday, April 21, 2014 11:08:55 AM UTC-4, Don wrote:
Create a matrix distance[x][y] and set all values to a large number.
This will represent the distance to travel to the destination on the
shortest route.
Now set the distance at the destination to zero.
Set all adjacent locations to one, and repeat the process recursively,
always setting valid adjacent locations with a larger distance value to the
distance from the current location plus one. In the end, you will have the
distance from every location on the grid. Now you can find the shortest
path from any location by always moving to a space which is closer than
your current location.
Don
On Sunday, April 20, 2014 11:52:44 AM UTC-4, bujji wrote:
Consider a city whose streets are defined by an X ×Y grid. We are
interested in
walking from the upper left-hand corner of the grid to the lower
right-hand corner.
Unfortunately, the city has bad neighborhoods, whose intersections we do
not want
to walk in. We are given an X × Y matrix BAD, where BAD[i,j] = “yes” if
and
only if the intersection between streets i and j is in a neighborhood to
avoid.
Give an O(XY ) algorithm to find the shortest path across the grid that
avoids
bad neighborhoods. You may assume that all blocks are of equal length.
For partial
credit, give an O(X^2 Y^2) algorithm.
If we walk in down or right directions only Dynamic programming solution
would be simple. But because of bad intersection points, we may need to
walk in up, down, right or left directions.
-Thanks
Bujji
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Shortest path in grid with dynamic programming.
Hi Don,
Nice solution. good. Looks like in your markShortestPath(int
i, int i, int d) function
you missed to set distance[i][j] = d; as first statement.
It looks like time complexity of this program is greater than O(XY). It
depends on number of multiple paths
to a point with different path lengths and order of evaluation of
paths.Evaluating recursion paths from greater
run length to smaller run lengths will result in updating distance[i][j]
several times.
Any improvements can we think of to improve this to achieve O(XY) bound?
-Thanks
Bujji.
On Mon, Apr 21, 2014 at 10:01 AM, Don dondod...@gmail.com wrote:
bool bad[X][Y];
int distance[X][Y];
void markShortestPath(int i, int i, int d)
{
if ((i = 0) (j = 0) (i X) (j Y) (distance[i][j] d)
!bad[i][j])
{
markShortestPath(i+1, j, d+1);
markShortestPath(i-1, j, d+1);
markShortestPath(i, j+1, d+1);
markShortestPath(i, j-1, d+1);
}
}
void findShortestPath()
{
int i,j;
for(i = 0; i X; ++i)
for(j = 0; j Y; ++j)
distance[i][j] = 10;
markShortestPath(X-1, Y-1, 0);
if (distance[0][0] == 10)
{
printf(No path exists\n);
return;
}
i = j = 0;
printf(Start at (0,0)\n);
while(distance[i][j])
{
if (distance[i+1][j] == distance[i][j]-1) ++i;
else if (distance[i-1][j] == distance[i][j]-1) --i;
else if (distance[i][j+1] == distance[i][j]-1) ++j;
else if (distance[i][j-1] == distance[i][j]-1) --j;
printf(Move to (%d, %d)\n, i,j);
}
}
On Monday, April 21, 2014 11:08:55 AM UTC-4, Don wrote:
Create a matrix distance[x][y] and set all values to a large number.
This will represent the distance to travel to the destination on the
shortest route.
Now set the distance at the destination to zero.
Set all adjacent locations to one, and repeat the process recursively,
always setting valid adjacent locations with a larger distance value to the
distance from the current location plus one. In the end, you will have the
distance from every location on the grid. Now you can find the shortest
path from any location by always moving to a space which is closer than
your current location.
Don
On Sunday, April 20, 2014 11:52:44 AM UTC-4, bujji wrote:
Consider a city whose streets are defined by an X ×Y grid. We are
interested in
walking from the upper left-hand corner of the grid to the lower
right-hand corner.
Unfortunately, the city has bad neighborhoods, whose intersections we do
not want
to walk in. We are given an X × Y matrix BAD, where BAD[i,j] = “yes” if
and
only if the intersection between streets i and j is in a neighborhood to
avoid.
Give an O(XY ) algorithm to find the shortest path across the grid that
avoids
bad neighborhoods. You may assume that all blocks are of equal length.
For partial
credit, give an O(X^2 Y^2) algorithm.
If we walk in down or right directions only Dynamic programming
solution would be simple. But because of bad intersection points, we may
need to walk in up, down, right or left directions.
-Thanks
Bujji
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
Re: [algogeeks] Re: Shortest path in grid with dynamic programming.
Hi Don,
At most we can reach a point from 4 adjacent points. So, time
complexity will be O(XY) only.
-Thanks,
Bujji.
On Mon, Apr 21, 2014 at 1:38 PM, bujji jajala jajalabu...@gmail.com wrote:
Hi Don,
Nice solution. good. Looks like in your markShortestPath(int
i, int i, int d) function
you missed to set distance[i][j] = d; as first statement.
It looks like time complexity of this program is greater than O(XY). It
depends on number of multiple paths
to a point with different path lengths and order of evaluation of
paths.Evaluating recursion paths from greater
run length to smaller run lengths will result in updating distance[i][j]
several times.
Any improvements can we think of to improve this to achieve O(XY) bound?
-Thanks
Bujji.
On Mon, Apr 21, 2014 at 10:01 AM, Don dondod...@gmail.com wrote:
bool bad[X][Y];
int distance[X][Y];
void markShortestPath(int i, int i, int d)
{
if ((i = 0) (j = 0) (i X) (j Y) (distance[i][j]
d) !bad[i][j])
{
markShortestPath(i+1, j, d+1);
markShortestPath(i-1, j, d+1);
markShortestPath(i, j+1, d+1);
markShortestPath(i, j-1, d+1);
}
}
void findShortestPath()
{
int i,j;
for(i = 0; i X; ++i)
for(j = 0; j Y; ++j)
distance[i][j] = 10;
markShortestPath(X-1, Y-1, 0);
if (distance[0][0] == 10)
{
printf(No path exists\n);
return;
}
i = j = 0;
printf(Start at (0,0)\n);
while(distance[i][j])
{
if (distance[i+1][j] == distance[i][j]-1) ++i;
else if (distance[i-1][j] == distance[i][j]-1) --i;
else if (distance[i][j+1] == distance[i][j]-1) ++j;
else if (distance[i][j-1] == distance[i][j]-1) --j;
printf(Move to (%d, %d)\n, i,j);
}
}
On Monday, April 21, 2014 11:08:55 AM UTC-4, Don wrote:
Create a matrix distance[x][y] and set all values to a large number.
This will represent the distance to travel to the destination on the
shortest route.
Now set the distance at the destination to zero.
Set all adjacent locations to one, and repeat the process recursively,
always setting valid adjacent locations with a larger distance value to the
distance from the current location plus one. In the end, you will have the
distance from every location on the grid. Now you can find the shortest
path from any location by always moving to a space which is closer than
your current location.
Don
On Sunday, April 20, 2014 11:52:44 AM UTC-4, bujji wrote:
Consider a city whose streets are defined by an X ×Y grid. We are
interested in
walking from the upper left-hand corner of the grid to the lower
right-hand corner.
Unfortunately, the city has bad neighborhoods, whose intersections we
do not want
to walk in. We are given an X × Y matrix BAD, where BAD[i,j] = “yes” if
and
only if the intersection between streets i and j is in a neighborhood
to avoid.
Give an O(XY ) algorithm to find the shortest path across the grid that
avoids
bad neighborhoods. You may assume that all blocks are of equal length.
For partial
credit, give an O(X^2 Y^2) algorithm.
If we walk in down or right directions only Dynamic programming
solution would be simple. But because of bad intersection points, we may
need to walk in up, down, right or left directions.
-Thanks
Bujji
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an
email to algogeeks+unsubscr...@googlegroups.com.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To unsubscribe from this group and stop receiving emails from it, send an email
to algogeeks+unsubscr...@googlegroups.com.
