Optimal Path from source to multiple destinations

[Potatochip911]

Homework Statement

You are placed in a 2-dimensional labyrinth at a starting location $s$ and must travel to n goal locations $g_1, g_2, ..., g_n$. Determine the optimal path using the A* algorithm.

g = goal cell, s = start cell
example input:
3 11 //row length, column length
# # # # # # # # # # #
# g - - s - g - g - #
# # # # # # # # # # #example output:
# # # # # # # # # # #
# 1 2 2 2 1 1 1 1 0 #
# # # # # # # # # # #

numbers represent how many times that square was traveled over.

Homework Equations

A* Algorithm

The Attempt at a Solution

What I've currently managed to do is scan in the labyrinth, record the starting position, and create a list of all the goal locations. Then I determine which flag to travel to by checking which one is closest to the starting location and performing an A* search towards that location using Manhattan distance as the heuristic then setting my start location to the flag and repeating this operation for the next closest goal. Repeating this step $n$ times creates the path. Unfortunately, this is essentially just a greedy algorithm using A* to find the shortest path between two locations in the labyrinth and in my example it will fail to find the shortest path as it will take the path (first goal to the right of start location)->(second goal to the right of start location)->(first goal on the left of start location) resulting in it taking a longer path back to the unvisited goal(s).

I would like to remove the greedy algorithm part of picking the closest goal as the target and then just traveling to that goal location (rinse and repeat) by creating an actual heuristic to determine the fastest path between all of the goals however I have no clue how to go about doing this. For example I am completely clueless as to what the goal state would be for this since it no longer becomes reaching a single goal destination.

If someone could point me in the right direction that would be great!

 

[mfb]

A* will give you the shortest path between two given points, but the general problem of the shortest path reaching all goals should be equivalent to the traveling salesman problem, which means there is no easy solution that is guaranteed to find the optimal path.
For small n you can simply check all options (all possible orders of the goals to travel to).

 

[Potatochip911]

A* will give you the shortest path between two given points, but the general problem of the shortest path reaching all goals should be equivalent to the traveling salesman problem, which means there is no easy solution that is guaranteed to find the optimal path.
For small n you can simply check all options (all possible orders of the goals to travel to).

Ok makes sense. What if instead of the optimal path we are interested in a reasonably accurate approximation?

 

[donpacino]

Ok makes sense. What if instead of the optimal path we are interested in a reasonably accurate approximation?

the same logic applies.

a reasonably accurate prediction is just a form of optimization, its just not the ideal optimization. A reasonably accurate approximation can be found by following the same techniques used to find the ideal optimization, just with less resolution (for example if you need to decrease run-time).If you are looking for an easy to implement solution, look into simulated annealing.
The trick to finding a global minimum is to escape the local minimum.