Consider the following scenario, in the "Minimum Knight Jumps" problem, you are given a weighted n cross times n chess board (a square matrix represented as a 2D array) with a knight in the upper left corner. The board is weighted in the sense that each cell has a certain weight or cost that is to be paid when the cells are used (i.e., traversed). A knight jump is defined as follows: At each jump, the knight can move either two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of an 'L'). The cost of a jump is the sum of the costs of the 3 traversed cells. The objective is to move the knight to the lower right corner via a minimum number of knight jumps. Q1: Formulate the problem as a search problem. In particular, What would be a state representation? What are the actions and what is a goal state? Q2: How would you solve the problem via BFS? Q3: Describe (briefly) a Bidirectional Search solution. Q4: How would you solve the problem via A* Search? In particular, give an effective (and efficient) admissible heuristic and describe the main steps. Q5: Can you change the problem's representation to make use of Dijkstra's algorithm? How? (Just describe how the problem becomes solvable via a Shortest Path algorithm without presenting a complete solution.) Q6: Which of the above solutions is the most efficient? Justify.