Warning

This page is located in archive.

Create an algorithm which finds a path on the road graph of United Kingdom (UK) between two nodes (intersections).

**Input**:

- Graph representing road network in UK
- The graph edges contain length of the edge and maximal allowed speed
- The nodes are signed with unique identifier ID.

- Initial node
- Goal node

**Output**:

- A path between the initial and the goal node

**Quality criteria**, listed in descending priority:

- The algorithm fulfills all parts of the assignment (classes name and location, using given structures and the method add() in the open list - see below)
- The path is correct, i.e., leads from origin to destination, the path is connected, i.e., two subsequent edges have a common node and the edges are sorted correctly.
- The found path minimizes transport time between initial and goal state
- The number of expanded nodes is minimal

**Grading**

- Algorithm fulfills the assignment completely
- The path is correct, i.e., leads from origin to destination, the path is connected, i.e., two subsequent edges have a common node and the edges are sorted correctly. [+1b]
- The found path minimizes transport time between initial and goal state [+2b]
- The number of expanded nodes is minimal [+0-3b]

**Date/time**: 25/03/2018 23:59:59**Content**: compressed content of Java package`student`

(pack only .java source files, no subfolders please)

- Use the codebase available HERE.
- Implement class
`Planner`

in package`student`

(implementation of the interface`PlannerInterface`

) - Create class
`OpenList`

which extends class`AbstractOpenList`

in your package.**For adding the items to OpenList use only the method add(T item)** - If you modify any item in OpenList (you have added it to the OpenList earlier, you just recompute its cost), then you don't need to call the
**add**method (however, you can - the Counter value is going to be increased though). - The algorithm is going to return
**null**if the path does not exist

- The class
**RoadGraph**allows you to access the graph and contains a set of method which you can use to move along the graph - The class
**GraphEdge**contains the methods getAllowedMaxSpeedInKmph() and getLengthInMetres() which return the maximal allowed speed in km and length in meters respectively. - The class
**Utils**gives you the metric for counting the distance between any two nodes in the graph. - The class
**PlannerExecutor**allows the body of the program where you can test your algorithm.

- Origin node ID = 13823646
- Destination node ID = 188755778
- Plan length [km]: 932.8542488743733
- Time to travel [hrs]: 12.084881006921961

- Origin node ID = 26746953
- Destination node ID = 1037726044
- Plan length [km]: 664.3940259558422
- Time to travel [hrs]: 8.002850863827378

- Origin node ID = 243081231
- Destination node ID = 21728749
- Plan length [km]: 560.2105619356079
- Time to travel [hrs]: 7.149357704368445

courses/b4b36zui/tasks/task1-maze-en.txt · Last modified: 2018/03/05 10:28 by fiedlda1