Figure 1 700 600 100 400 250 Consider an idealization of a problem where a robot
ID: 3891105 • Letter: F
Question
Figure 1 700 600 100 400 250 Consider an idealization of a problem where a robot has to navigate its way around obstacles. The goal is to find the shortest distance between two points on a plane that has convex polygonal obstacles. Figure 1 shows an example scene with seven polygonal obstacles where the robot has to move from the point start to the point end Convince yourself that the shortest path from one polygon vertex to any other in the scene consists of straight-line segments joining some of the vertices of the polygon. (Note that the start and the end goal points may be considered polygons of size 0) a) ls it possible to solve the problem using a breadth-first or a depth-first search algorthm? If the answer is yes, briefly discuss your solutions Otherwise please explainExplanation / Answer
Hello,
Yes, We can solve this problem in breadth first search, but the thing here is breadth first search algorithm will result into the worst case possible. This can be reduced by using A* Algorithm. Since the question is only in breadth first search, I'll answer according to it. In breadth first search (BFS) evey neighbour node is visited from the root node. and next the neighbour node of first visited node is examined. This process continues till all the vertex are examined. On considering this we could assume that the robot visits the grid accordingly so that it will not collide with any obstacles. we can code up the algorithm. Below is the C code you could use to solve this problem.
//Code for the above problem:
#include<iostream>
#include<queue>
#include<stdio.h>
using namespace std;
class robot
{
public :
int x;
int y;
};
int main()
{
int block[8][8] = {
{1,1,1,1,1,1,1,1},
{1,0,0,0,1,1,1,1},
{1,1,0,0,1,1,1,1},
{1,1,0,0,1,1,1,1},
{1,1,1,2,0,1,0,0},
{1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1},
{1,1,1,1,1,1,1,1}
};
int rw = 8;
int cl = 8;
int dis[rw][cl];
for(int u = 0;u<rw;u++)
{
for(int v =0;v<cl;v++)
{
dis[u][v] = -1;
}
}
queue<robot> iterator;
robot r;
r.x = 0;
r.y = 0;
dis[0][0] = 0;
iterator.push(r);
while(!iterator.empty())
{
r = iterator.front();
iterator.pop();
for(int p = -1;p<2;p++)
{
for(int q = -1;q<2;q++)
{
if(p == q)continue;
int i = r.x + p;
int j = r.y + q;
if(i<0)i=0;
if(j<0)j=0;
if(i>rw-1)i=rw-1;
if(j>cl-1)j=cl-1;
if(i== r.x && j == r.y)
continue;
if(dis[i][j] == -1)
{
if(block[i][j] != 0)
{
dis[i][j] = dis[r.x][r.y] + 1;
robot rn;
rn.x = i;
rn.y = j;
iterator.push(rn);
}
}
}
}
}
for(int x = 0;x<rw;x++)
{
for(int y =0;y<cl;y++)
{
printf("%d ",dis[x][y]);
}
printf(" ");
}
return 0;
}
Hope I have solved your problem :)
Thank you :)
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.