Dijkstra's & A* shortest path algorithms

Explain why this graph is a visualisation of the problem.

A user needs to travel from planet A to planet H. They need to travel the least expensive route.

Show how Dijkstra’s algorithm can be used on the directed graph shown in Fig. 5 to find the shortest path from start planet A to the end planet H.

You must state the nodes on the final path and the distance of this path. Show your working.

You may use the table to give your answer.

The A* algorithm can also be used to find the shortest path in a graph.

Describe how an A* algorithm uses heuristics to be an efficient algorithm.

A computer game has a building containing 7 rooms. There are secret passages between each room. Fig. 3 shows the rooms and the passages between the rooms represented as a graph data structure.

The number in bold below each node in Fig. 3 is the heuristic value.

Perform an A* algorithm on the graph shown in Fig. 3 to find the shortest path from A to G.

Show your working, the nodes visited and the distance.

You may use the table below to give your answer.

State four ways that a graph data structure is different from a tree data structure.

* The final game will involve multiple computer-controlled characters and interactive elements that make use of artificial intelligence to determine the moves they will make.

The artificial intelligence will use heuristics to determine where the computer-controlled characters will move in the game.

Discuss how heuristics can be used in algorithms.

You should include the following in your answer:

• the purpose of heuristics

• the benefits and drawbacks of heuristics

• the suitability of heuristics in algorithms within a computer game.

A tree is one example of a data structure.

Give two characteristics of a tree data structure.

The following data is entered into a binary search tree.

22 13 5 36 55 14 8

Draw the binary search tree when the given data is entered in the order given.

Describe how a leaf node is deleted from a binary search tree.

Describe how a binary search tree can be searched for a value.

Identify the order that the nodes will be visited in a depth-first (post-order) traversal of this binary search tree.

Explain how backtracking is used in depth-first (post-order) traversals.

State one way a directed graph is different to an undirected graph.

State one way a graph data structure is different to a tree data structure.

Give one reason why the graph is a visualisation of the problem.

Give a similarity and difference between the performance of Dijkstra’s algorithm and the performance of A* algorithm.

State why performance modelling is used to test a system.

Describe how performance modelling can be used in the delivery system.

Taylor is creating an online multiplayer game where users can create accounts and build their own circus. Each circus will contain characters such as clowns, animals, magicians and dancers.

Users can set up a new circus in the online world, purchase new characters and visit other users’ circuses.

Taylor uses computational methods to analyse the problem including abstraction.

Describe how Taylor could use abstraction in the design of his online circus game.

Taylor will make use of concurrent processing within his circus game.

Describe what is meant by the term ‘concurrent processing’.

Explain why concurrent processing is needed to allow multiple users to log in and interact with game elements at the same time.

Some of the characters in the game will move and interact independently. Taylor is going to use graphs to plan the movements that each character can take within the game.

DancerGold is one character. The graph shown in Fig. 1 shows the possible movements that DancerGold can make.

DancerGold’s starting state is represented by node A. DancerGold can take any of the paths to reach the end state represented by node G.

The number on each path represents the number of seconds each movement takes.

The number in bold below each node is the heuristic value from A.

Define the term heuristic in relation to the A* algorithm.

Perform an A* algorithm on the graph shown in Fig. 1 to find the shortest path from the starting node to the end node. Show your working, the nodes visited and the distance. You may choose to use the table below to give your answer.

A breadth-first traversal can be performed on both a tree and a graph.

Show how a breadth-first traversal is performed on the following binary tree.

* The game will have thousands of users. Taylor will store data about the users and their actions while playing the game in a large database.

Evaluate how Taylor can use data mining to inform future changes to improve his circus game.

Mabel is a software engineer. She is writing a computer game for a client. In the game the main character has to avoid their enemies. This becomes more difficult as the levels of the game increase.

Mabel uses decomposition to design the program.

Explain how decomposition can aid the design of this program.

The computer game allows a user to select a character (e.g. name, gender). They can then choose a level for the game (easy, normal, challenging). The user controls their character by moving it left or right. The character can jump using space bar as an input. If the character touches one of the enemies then it loses a life. The character has to make it to the end of the level without losing all their lives.

The game is designed in a modular way.

One sub-procedure will handle the user input.

Describe three other sub-procedures Mabel could create for the given game description.

Describe the decision that the program will need to make within the user input sub- procedure and the result of this decision.

Define pipelining and give an example of how it could be applied in the program.

*Mabel has been told that true programmers write programs in a text editor, and do not use IDEs. Mabel does not agree with this statement.

Discuss the use of an IDE in the development of this program.

The graph in Fig. 3 is a visualisation of the problem.

Identify one difference between a graph and a tree.

Explain how the graph is an abstraction of the problem.

Identify two advantages of using a visualisation such as the one shown in Fig. 3.

Demonstrate how Dijkstra’s algorithm would find the shortest path to the solution in Fig. 3.

* The creator of the puzzle has been told that the A* algorithm is more efficient at finding the shortest path because it uses heuristics.

Compare the performance of Dijkstra’s algorithm and the A* search algorithm, making reference to heuristics, to find the shortest path to the problem.