Graph search and A-star

Consider a $m \times n$ game board in which each cell has a numeric value, e.g:

A player starts the game with a token in the top-left cell (the cell GA in this example) and the player finishes the game by moving to the bottom-right cell (the cell KF in this example). In each round of the game, the player can move in four directions (up, down, left, and right). The distance of each move is determined by the value of the cell. When going over the border of the game board, one ends up on the other side. For example, if the player is in the cell JB, which has value 3, then the player can move 3 steps up (reaching GB), 3 steps right (reaching JE), 3 steps down (reaching HB), and 3 steps left (reaching JE). The score of a player is determined in the total number of rounds the player needs to reach the bottom-right cell.

P1.1

Model the above problem as a graph problem: What are the nodes and edges in your graph, do the edges have weights, and what problem are you trying to answer on your graph?

The game will be modelled as an unweighted directed graph, where the problem is to find the shortest path (minimum number of rounds) to get from top-left cell to bottom-right cell:

• Nodes: Each cell in the game board is a node.
• Edges: edges are possible moves from one cell to another. The edges will have unweighted, as each moves takes one round regardless of the distance. For example, cell $JB$ will be connected to $GB, JE, JE, BH$

P1.2

Provide an efficient algorithm that given a $m \times n$ game board, will find an optimal solution if such a solution exists. If the game board has no solution, then the algorithm should report that the game board is invalid. The runtime of the algorithm should be worst-case $\mathcal{O}(mn)$

Implement a breadth-first search to find shortest path:

P1.3

Explain why your algorithm is correct and has a complexity that is worst-case $\mathcal{O}(mn)$

For BFS, for shortest path in unweighted path has runtime complexity of $\mathcal{O}(V+E)$ worst-case. In this setup, $V=mn$ (number of vertices, which is $mn$), and $E \leq 4mn$ (number of possible moves, up, left, right, down, which would be $\leq 4mn$). Thus, worst-case runtime complexity is $\mathcal{O}(mn)$

Let $T(m,n)$ be maximum number of operations performed by the algorithm. The boundary function can be defined as:

where $c$ is a constant. Invariance requires BFS traversal holds true.

Base case: starts cell is (0, 0), therefore $T(1,1) = 1 \leq c \cdot 1 \cdot 1$

Assume that invariance holds for all cell up to $k^{\text{th}}$ cell, that is, for any $(i, j)$ we have $T(i,j) \leq c \cdots ij$

Consider the $(k+1)^{\text{th}}$ cell $(i,j)$ processed. The number of operations is as followed:

• dequeue $(i,j)$: constant $c_2$
• check if $(i,j)$ is the end cell: constant $c_3$
• retrieve value of cell: constant $c_4$
• iterate through the 4 possible moves: constant $c_5$
• check if neighbor is visited and mark nodes: constant $c_6$

Total number of operations is $c_2 + c_3 + c_4 + c_5 + c_6 = c_7$

Thus, number of operations performed for the $(k+1)^{\text{th}}$ cell is: $T(i,j) \leq c \cdot ij + c_7 \leq c \cdot mn + c_7$

Therefore, it holds for $(k+1)^{\text{th}}$ cell.

P1.4

Which of the two graph representation we saw in the course material did you use to store the game board? What would the complexity of your algorithm be if you used the other graph representation?

The graph representation is used as an adjacency list to store the game board.

If the graph representation was an adjacency matrix, the graph as 2D matrix of size $(mn) \times (mn)$, space complexity would increase to $\mathcal{O}((mn)^2)$, time complexity would remain $O(mn + E)$, where $E \leq 4mn$. Given that accessing neighbour cell would be faster since constant-time access of matrix entries. Overall time complexity would still be $\mathcal{O}(mn)$