1

I am working on an assignment which requires the use of A* algorithm but I cannot figure out how.

The assignment is, imagine a postman sending parcels on a grid map from (0,0) to infinity. He takes a list of tasks at the beginning of a day, with each task assigned a starting point (x1,y1) and an ending point (x2,y2). Since he cannot handle two tasks at the same time, he will have to arrange those tasks, so that when he finishes one task and move from the end point to the next start point, he could have the minimum travelling distance overall during the whole day. The distance is calculated as Manhattan distance which is d(x1,y1,x2,y2) = abs(x2 - x1) + abs(y2 - y1).

sample 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:

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

In my point of view, though a graph(or map) is mentioned here, it is not required since the only essential part is to sort those tasks for a minimum while the distance can be easily calculated. Something stupid would be permutation and select the one with the least cost but never to adopt that. I have also tried Greedy but it may not get the global best solution.

So the question is, since A* algo. is designed for path finding, how can we apply that or a variation of that to this problem of finding the correct way?

chad luo
  • 109
  • 10
  • See http://stackoverflow.com/questions/5344705/how-can-the-a-algorithm-be-applied-to-the-traveling-salesman-problem – Itay Karo Apr 29 '13 at 15:45

2 Answers2

0

I think you are trying to solve a variant of travelling salesman problem (TSP) http://en.wikipedia.org/wiki/Travelling_salesman_problem

For job A and B, you can calculate the Manhattan distance between the end point of A and start point of job B, and treat it as the distance From A to B. This operation will change the problem into TSP.

After the transformation, you problem became "Using A* to solve Travelling Salesman Problem", and this is a perfect match: How can the A* algorithm be applied to the traveling salesman problem?

Community
  • 1
  • 1
ArkChar
  • 323
  • 4
  • 10
0

Take all these points and feed it into a kd-tree. You can use kd-tree to find the nearest neighbour of any point.

While running the A* algo, expand the next node using the nearest neighbour. Go to the end of the path denoted by the nearest neighbour and then expand again. The delete operation will take O(log n) average time, which, I hope, will be suitable for your implementation.

For ex:

n nodes explored

cost = 31

Find nearest neighbour of (0,0) => (1,1)

Move from 0 0 to 1 1

Carry from 1 1 to 9 2

Find nearest neighbour of (9,2) => (3,3)

Move from 9 2 to 3 3

Carry from 3 3 to 5 3

Find nearest neighbour of (5,3) => (5,5)

Move from 5 3 to 5 5

Carry from 5 5 to 5 7

Find nearest neighbour of (5,7) => (3,5)

Move from 5 7 to 3 5

Carry from 3 5 to 2 7

+++++++++++++++++++++++++++++++++++++++++

Check this for kd-tree overview : http://en.wikipedia.org/wiki/Travelling_salesman_problem

and check this video for array based implementation of kd-tree : http://www.youtube.com/watch?v=2SbVSxWGtpI

P.S:- only insert first node of each path into the tree. And one more thing.... brute force will give you the global optima alright... but will take a lot of time.

metsburg
  • 2,021
  • 1
  • 20
  • 32
  • btw... I forgot to mention in the algo... if you're using A* search, you need to add the heuristic function to the cost of the expanded node... not sure how that'll help you though! – metsburg May 02 '13 at 05:15