I have a graph problem, which is different from the standard salesman problem. I say it is more difficult.
In a graph, I have many vertexes with different colors. It is more easier to think of each vertex as a shop selling only one goods and vertexes with the same color selling the same goods. There are edges between any two vertexes, with different distances. You start at a specific position (different from any vertex), and have a list of goods you need to buy. Figure out an optimal path with shortest distance so you can get all the goods from the shops on the path. You are not required to start and end at the same position and edges and vertexes can be visited more than once if you want. If there is no color on vertex, or in other words, each vertex sells a distinct goods, then the above problem is identical to salesman problem. But now we have colors on vertexes and once a vertex with a color is visited, you don't want to visit vertex with the same color (which will only increase the total distance). Since this problem is an extension of the standard salesman problem, the practical solution is probably heuristic. The key is, what heuristic strategy are you going to use. I think the problem a bit and come up with a very naive solution: For each vertex, calculate its distances to the closest vertexes with other colors. For vertexes with the same color, choose the one with the minimum total/average such distances. Then, only one vertex with a color is remained in the graph. Then use heuristic strategy for salesman problem. any other idea? --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
