You are given a bad-conditioning bike. In particular, you can\'t make left turns

Question

You are given a bad-conditioning bike. In particular, you can't make left turns when riding this bike. In addition, you arent going to make any U-turns either. You can ride down straight streets pretty fast, and your primary goal is to minimize the number of right turns you make. Now you have a. map of the town so that you can plan out a route that uses no left turns and no U-turns. The good thing is that the map comes in electronic form as an m times n grid of cells (an example is shown below). At each cell you visit, you can continue in the direction you were going, or turn right. (a). How should you convert the given map to a graph, what will be the vertices? What will be the edges? (only straight lines, left t urns, right turns or u-turns? maybe only a subset of them?) and bow would you assign the weights to the edges? (b). Based on part (a), give an efficient algorithm (pseudocode) to find a path (with no left turns and no U-turns) through an m times n map using the minimum number of left turns, or report that no such path exists. Analyze the running time of your algorithm. (Which among the three taught shortest path algorithm should 1 use? Remember under what circumstances they will be useful?) (c). Try to modify the algorithm (pseudocode) for part (b) to achieve the following: if two paths have the same number of loft t urns, then you select the path with shorter straight-line distance. That, is, if more than one optimal path exist, the path with the minimum straight-line distance will be produced by your algorithm, where straight-line distance can be referred to as the number straight steps. Analyze the running lime of your algorithm.

Explanation / Answer

The basic idea to solve this problem is to create the graph representation of the problem and then use the graph shortest path algorithm (Dijkstra) to find the optimal path.

a) Each edge (u,v) in the graph has two weights, wr(u,v)=1 if the edge represents a right turn, and ws(u,v)=1 if the edge represents a straight movement. For each cell in the maze there are four nodes, N, S, W, and E, corresponding to the possible directions the cell is entered. The edges from a node are the directions the path can leave the cell. Only straight line or right turn edges are possible.

b) he edge weight are a pair of positive numbers W=(wr,ws). They are ordered by W<W' iff wr<w'r or wr=w'r and ws<w's. We can therefore apply Dijkstra algorithm. The graph has O(mn) nodes. Since Dijkstra algorithm runs in O(V lg(V) + E) time, this algorithm runs in O(mn lg(mn)) time.

c) It uses a mXn array to store the four minimum weights for path exiting the cell in the four directions N, S, W, and E. They are all initialized to infinity. If a cell cannot be exited in a direction the corresponding weight will always remain infinity. Then construct a FIFO list of triplets (cell, from, weight), where cell is a cell in the maze, from is the neighbor cell before it on an optimal path, and weight is the weight of the optimal path from S to the cell. The list is initialized by putting (S, nil, 0) on it. While the list is not empty, pop an item and add the neighbors that, if reached from the cell, decrease its weight for exiting in the corresponding direction. For example if (C, F, w) can be followed by (N, C, w') to the South, if w'=w+w(move) if less than wsouth(C), add (N, C, w') to the list and update wsouth(C) = w'.
As we break ties by straight-line distance, and we want just a path with minimum number of right turns, then we can optimize the priority queue for Dijkstra's algorithm to support priority queue operations in O(1) time. This reduces the runtime of the algorithm to O(mn).

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.