I'm looking for a "multi-goal" path-finding algorithm. Problem I'm running into is I'm not sure what it is called... I'm not even sure "multi-goal" is what I'm actually after. I've looked at Djiskra's, which is looking for shortest path between two points (as is A*), and I've looked at travelling salesman, which is multi-goal, but is a "stop where you started".
What I'm looking for is:
- given an unsorted list of nodes with equal priority
- given a starting node
- where not all of the nodes are connected to each other
- and nodes have a minimum of one edge
- generate a path that efficiently hits all of the grid locations (i.e. back-tracking is allowed, does not have to be shortest path, end point does not matter).
I'm assuming that there's an algorithm out there for this sort of a path-finding problem. (Or it may be a goal seeking problem, I'm not sure either.)
One option I was thinking of is a depth-first bounded search, but without a better idea of how to represent branching choices, I'm not sure how good the search would be.
I'm estimating this at about 300 nodes, with about 50 nodes as "nodes that must be visited", which may also be a small enough space that a brute force approach may be the easiest manner.
Any advice on what to look for, or even an algorithm that I could implement? Thanks!
