Reference no: EM131576925

This is a astar problem. the Locations are states not nodes.

Courier Delivery Problem

You have just been hired as a bicycle courier. At the beginning of each day you receive a list of jobs comprising packets that need to be delivered from one location to another. You can choose to deliver the packets in any order, however you can carry only one packet at a time. Naturally you want to minimize the total distance travelled during the day, starting from home and finishing when the last packet is delivered. In this, you will implement an A* search procedure for the courier delivery problem. In your program design, make use of the Strategy pattern to supply a heuristic to the search procedure, and don't forget to ensure that your heuristic is admissible.

The city map is understood to be laid out on a grid with both the x-axis and y-axis running from 0 up to infinity (notionally). All locations are fully contained in this quadrant. You always start at your home, which is at the origin (0,0) but can finish anywhere. Jobs are specified by the (x,y) coordinates (in integers) of their start and end points on the grid. You can either carry a packet or move (without carrying anything) between any two points by following a path along the grid lines. Since all packets must be delivered in any solution, an optimal solution is one that minimizes the total Manhattan distance covered whilst not carrying any packets.

All input will be in a file with a sequence of lines of the following form:

Job <x1> <y1> to <x2> <y2>
# there is a job to deliver a packet from the point (<x1>,<y1>) to the point (<x2>,<y2>)

Create all your Java source files in the default package. Call your main Java file CourierDelivery.java. Read input from a file whose name is passed as an argument to the main method in the call to java CourierDelivery and print output to System.out. For machine marking, the output will be redirected to a text file that will be compared to the expected output (so do not print out extra spaces, etc.). For the purposes of machine marking, problems will be used for which there is only one optimal solution, though in the case of multiple optimal solutions, your program should produce one of them. To handle input from a text file, as in Assignment 1, use Java code such as:

try
{
Scanner sc = new Scanner(new FileReader(args[0])); # args[0] is the first command line argument
}
catch (FileNotFoundException e) {}

Sample Input

For example, the following input has three jobs as indicated. The format and meaning of the input is as follows (comments are for explanation and should not appear in the actual input):

Job 3 3 to 5 3 # there is a job from (3,3) to (5,3)
Job 1 1 to 9 2 # there is a job from (1,1) to (9,2)
Job 3 5 to 2 7 # there is a job from (3,5) to (2,7)
Job 5 5 to 5 7 # there is a job from (5,5) to (5,7)

Sample Output

One valid output corresponding to the above input is as follows (the n in the first line in the output should indicate the number of nodes explored in the search, which of course will vary according to the heuristic used, and the second line should give the cost of the solution found as an integer which is the total distance travelled):

n nodes explored
cost = 31
Move from 0 0 to 1 1
Carry from 1 1 to 9 2
Move from 9 2 to 3 3
Carry from 3 3 to 5 3
Move from 5 3 to 5 5
Carry from 5 5 to 5 7
Move from 5 7 to 3 5
Carry from 3 5 to 2 7