Before the advent of inkjet and laser printers, straight line drawings used to be plotted by coloured pens on large sheets of paper: the pens moved very slowly so this was a time-consuming process. Since time is money, it was important to draw figures in an optimal way, using minimum time. you will implement an A* search procedure for the pen plotter problem (with only one coloured pen to make it simple, though in the real problem, there would be multiple pens which would have to be changed manually, costing even more time). [A contemporary related problem is that of a bicycle courier who has to pick up multiple packets and deliver them to their destinations around the city in minimum time, but this is a much harder problem to solve.] 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 paper sheet 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 drawings are fully contained in this quadrant and can be assumed to fit on the page. Lines can always be assumed not to be contained in other lines. The pen always starts at the origin (0, 0) but can finish anywhere. Lines are specified by the (x, y) coordinates (in integers) of their end points on the grid. The pen can either draw a line between any two points or move (without drawing anything) in a straight line between any two points. As should be obvious, a line can be drawn in either direction. Since we want to minimize the total time to draw a figure, assume the pen moves at constant speed so that an optimal drawing is one that minimizes the total distance moved by the pen whilst not drawing.
Sample Input
For example, the following input should draw a simple star shaped figure with six lines radiating from the point (4, 4). The format and meaning of the input is as follows (comments are for explanation and will not appear in the actual input):
Line between 4 1 and 4 4 # there is a line between (4, 1) and (4, 4)
Line between 4 4 and 4 7 # there is a line between (4, 4) and (4, 7)
Line between 2 6 and 4 4 # there is a line between (2, 6) and (4, 4)
Line between 4 4 and 6 2 # there is a line between (4, 4) and (6, 2)
Line between 6 6 and 4 4 # there is a line between (6, 6) and (4, 4)
Line between 2 2 and 4 4 # there is a line between (2, 2) and (4, 4)
Sample Output
The output corresponding to the above input is as follows (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):
nodes explored Move from 0 0 to 2 2
Draw from 2 2 to 4 4
Draw from 4 4 to 6 6
Move from 6 6 to 4 7
Draw from 4 7 to 4 4
Draw from 4 4 to 4 1
Move from 4 1 to 6 2
Draw from 6 2 to 4 4
Draw from 4 4 to 2 6
please help me with this problem, give me some ideas about solving this.
what algorithm should I use?
thanks a lot!!!