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 -~----------~----~----~----~------~----~------~--~---
