Each square on an N * N chess board has a weight associated with it. A robot can

Question

Each square on an N * N chess board has a weight associated with it. A robot can move from one square of the chess board to an adjacent square only by moving horizontally or vertically i.e it cannot make any diagonal moves. The energy spent by a move is equal to the absolute difference of weights of the two adjacent squares.
a) Develop an algorithm to find minimum energy route for the robot starting at square (1,1) and ending at square (N,N) .Your algorithm should have the worst case complexity of polynomial in N. Analyze the running time of the algorithm

b) Show that your algorithm can be generalized if we have M-dimensional chess board N*N*N………*N. The robot will start at (1,1,1……..,1) and end at (N,N,N….…,N). How does the time complexity of your algorithm change?

Explanation / Answer

1) We will convert the chess board to a graph and use Dijkstra's algorithm to find the minimum energy from (1,1) to (N,N). Each square in board will be a vertex in the graph, whenever we can move from one square to another we add an edge between the corresponding vertices. The weight of edge will the energy consumed to move the robot.

Let's say (1,1) is represented by V(1,1) and (1,2) as V(1,2). As we can move from (1,1) to (1,2), we add an edge from V(1,1) to V(1,2) and the weight of the edge will be energy consumed to move the robot from (1,1) to (1,2).

Upon doing this for all the squares in the board. We will get a graph, now we consider V(1,1) as the source and apply Dijkstra's algorithm to the graph. In Dijkstra's algorithm we find the minimum distance from the source vertex to all other vertices. This includes the vertex V(N,N). So minimum distance from V(1,1) to V(N,N) is the energy consumed by the robot to move from (1,1) to (N,N) on the board.

The worst case runtime for Dijkstra's algorithm is O(|E| + |V|log|V| ). In this case |V| is N*N = N^2. |E| is O(N*N) as each vertex will at maximum has only 4 edges. So the worst case runtime will be O(N^2 + (N^2)xlog(N^2) ) which will be O((N^2)xlog(N)).

2) This algorithm can easily be applied to M dimensional board. We again create a graph for board in the same way as above. We apply Dijkstra's algorithm to find the minimum distance. The worst case time will be O((N^M)xMxlog(N))

Explanation of Dijkstra's algorithm, Steps involved:

1) We maintain a table to find the current minimum distance of each vertex from the source. We maintain a list of vertices which are already visited, and this has only the source initially. We also maintain a list of unvisited vertices, and this has all the vertices except the source initially.

2) We initialize the distance to all the vertices to infinity except the source. The distance for source will be zero. We start with source as current node.

3) From the current node consider all of its neighbours and calculate their tentative distance from the source. This distance will be the distance of the current node from the source plus the distance from the current node to the neighbour. Now if the tentative distance is less than the previous distance we update the distance in the table.

4) Now we add the current node to the visited and remove it from unvisited list.

5) From the set of unvisited vertices consider the vertex with smallest distance from the source. If the smallest distance is infinity then stop, otherwise make it the current node and move to step 3. If the unvisited list if empty then stop.

Related Questions

Navigate

• Browse (All)
• Browse E
• Subjects

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