I have a group of nodes and edges connecting these nodes, each edge has a cost to traverse. All of these nodes are put into their subsets and a cycle must be found for the lowest cost to visit at least one node in each of these subsets. You can imagine this as each node is a different position on an island chain and each subset is an island. You start at one position and need to visit every island and then return to where you started for the lowest cost. You don't get to decide where you start, that is pre-chosen for you. I want to eventually create a program to run this and there are around 30 nodes and 6 subsets. Does anyone know of a fairly efficient algorithm that can complete what I need in a reasonable amount of time on a pretty nice computer. If you don't know a very efficient algorithm I would still love to hear it anyway just in case it might help.
I have tried just guessing and checking but it takes very long time and I would like to be able to dynamically change the weights of the edges and quickly get a new route.
Edit: To clarify you should not assume the edges between the islands are always greater than those within them. Also all nodes are connected by edges to all other nodes. This is a practical problem, and don't read to deap into the island analogy. Just trying to visualize it. Those are all the rules, you can visit an island as many time as you like and you can visit a node as many times as you like.
Create a new graph that has one vertex for each island. Link every vertex, if the islands they represent are linked, with a link of the least cost of the links between them in the original. Apply a travelling saleaman algorithm to the new graph. ( There are lots of TSP algorithms and graph theory libraries that implement them. With so few nodes ( just 6 ), you do not need an efficient one - brute force search will likely take less than a second for such a small graph )
Now you have the slightly tricky problem to identify the real vertices to be used for each island. Again, no need to be clever, just try all possibilities, and select the one or two nodes in each island that give the cheapest result.
This answer is likely to offend the computer scientists among us. However, since you have indicated this is a real world problem, not an academic exercise, and because this is supposed to be programming help site ( there are other sites for computer scientists ) I believe that a quick and dirty method that could be implemented in an afternoon is more useful than hunting around for complicated algorithms that will take days to understand and implement.