Question

How to solve this ?

3. (30 pts) Consider a hypothetical floor plan such that the area is organized in hexagonal cells as shown in Figure 3. We begin at the cell marked start, and we want to reach the cell marked end. We can travel from one cell to another, if the two cells are neighboring, i.e., they share an edge. Each time we cross from one cell to a destination cell, we consider the move as a single step and the destination cell as visited. We want to find the shortest path from the start to the end, minimizing the number of steps. Consider the following algorithm: (1) We consider the start cell as visited, and we write the number 0 on the cell. (2) If a cell has the number n written on it, we can visit all neighboring cells, writing the number n+1 on it if either: (a) the neighboring cell has not been visited before, or (b) the neighboring cell has been visited before and holds the number m such that m> n+1. (3) We stop the execution of the algorithm when we can no longer execute (2) START END Figure 3: Floor plan. Answer the following questions: (1) (15 pts) Execute the algorithm on the floor plan given in Figure 3, writing numbers on each cell. Show the result. (ii) (5 pts) Is the algorithm correct? That is, does it always find the shortest path? Yes or No? No explanations needed. (iii) (10 pts) For a given floor plan with N cells including the start and the end cell, how many steps do we need to reach the end cell, starting from the start cell, in the worst case scenario (i.e., the worst floor plan layout with N cells)? Why?

Answer 1

Solution :-

In this question we initially begin at the cell called start and want to go till the cell marked end. We want to find the shortest path from the start to the end minimizing the steps. Each step is counted as 1 when we traverse from one cell to the another if they share an edge.

The algorithm follows the following steps :-

1. The start cell is considered as visited and the number 0 is written on the cell.

2. We can visit from one cell (written n on it) to another (written n + 1 on it), if and only if the neighbouring cell has not been visited earlier or the neighbouring cell has been visited before and holds the number m such that m > n+1.

That means is the destination cell is visited earlier and the number written on it is greater than n+1, that directly means, the new distance of the node is less than the previously calculated distance.

3. We stop when we no longer execute, that means all the cells in the given diagram has been traversed.

NOTE - This algorithm corresponds to the Breadth First Search algorithm of graph theory and it capable of finding the shortest path from the source node to the destination node.

In BFS (breadth-first search), we traverse all the node according to it's level with respect to the source nodeand this algorithm does the same.

Let's answer the question based on the given knowledge of the algorithm.

1. Fristly, as suggested in the question, the start is taken as 0. Now, when applying the algorithm, we will surround all the cells that share a single side with the starting cell with number 1 as n + 1 = 0 + 1 = 1.

Similarly, all the cells that share a side with all the cells numbered 1 will be numbered 2 and this process will continue till we number all the cells present in the diagram.

Hence, following the algorithm, we numbered all the cells and the resulted floor plan is shown in the below diagram.

The floor plan with all the cells numbered is shown below.

5 5 6 7 33 3 2 22 2 1 1 2 4 5 8 3 67 1 1 N 7 7 8 2 7 8 9 12 3 start 6 17 56 10 11 12 4 4 11 11 12 5 5 6 12 12 13 end

Here, in the above diagram, all the numbers are written on the cell by executing the algorithm.

So, we need to take 12 steps from the starting cell to reach the ending cell.

2. Yes, the algorithm always finds the shortest path, and is correct.

3. The worst floor plan can be shown below,

end start

With this floor plan, it will take N number of steps, that is the total number of cells present in the floor plan, to reach from the start to the end which is the maximum.

Because with each step towards right (from start to end), we cover every cell before reaching the end cell.

Hence a linear floor planing is the worst.