Maybe this will work: Starting from each vertex using BFS calculate the shortest path which passes through vertexes from all the colors.
Best, Ridvan On Feb 24, 2:00 pm, "Ajinkya Kale" <[EMAIL PROTECTED]> wrote: > On 2/24/08, Sticker <[EMAIL PROTECTED]> wrote: > > > > > > > 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. > > I dont think that makes is identical to TSP. Cause in TSP you have to visit > every node. > But in this case you are given a list of goods and each vetex sells unique > good. > Also in TSP we have to return to the start point , but this is not the case > here ! > > 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? > > -- > Ciao, > Ajinkya --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
