Best Origin Point

[Medestrac]

Hi, what about finding the best starting point?

I need to paint several 2 colours objects: [Red, Blue], [Green, Yellow], [Blue, Green]...but don't want to wash my tools too many times. In this case the distance is the number of unique colour between two objects: [Red, Blue] and [Blue, Green] is distance 3: I need to open 3 paint cans, whereas [Red, Blue] and [Green, Yellow] is distance 4. So I have a matrix with only (0, 1, 2, 3 and 4): 0 when two objects are identicals, 4 when the 4 colours are different. Example: [[0 4 4 3 4 4 4 4 3 4] [4 0 4 4 4 4 3 4 3 4] [4 4 0 4 3 4 4 4 4 3] [3 4 4 0 4 4 4 4 3 4] [4 4 3 4 0 4 4 4 4 3] [4 4 4 4 4 0 4 3 4 4] [4 3 4 4 4 4 0 4 4 4] [4 4 4 4 4 3 4 0 4 4] [3 3 4 3 4 4 4 4 0 4] [4 4 3 4 3 4 4 4 4 0]] The TSP module is fantastic for finding the best arrangement...if I give it a good starting point, that I don't know. I could try each permutation of the matrix...but I'm not sure it's the more efficient way to find a good starting point. Any advice?

[fillipe-gsm]

Hi, @Medestrac

I probably need a more detailed example to actually understand your problem. But from what I got in your description there are two points I can make.

First, if I get this correctly, you may need a new definition of distance. For objects [Red, Blue] and [Blue, Green] you need to wash your tool once from the Red to Green. The blue one can be kept. If that is the case, then your "distance" is actually 1. Similarly, for objects [Red, Green] and [Green, Yellow] your distance would be 2 as you would need to wash both of your tools. So your new distance function would go from 0 to 2. Try if this makes more sense.

Second, given that the distance between two objects is the same regardless of their order, your distance matrix is symmetric. This means that the starting point is actually irrelevant since the returned route is circular.

For instance, say you have objects:

0: [Red, Blue],
1: [Red, Green],
2: [Green, Blue],
3: [Green, Yellow],

Say the algorithm returns the permutation [0, 2, 3, 1]. Remember from the README that this is circular, so after object 1 you go back to 0. So your actual route is 0 -> 2 -> 3 -> 1 -> 0. and the total cost is d_{0, 2} + d_{2, 3} + d_{3, 1} + d_{1, 0}.

Notice that if you change the starting point to 2, you get [2, 3, 1, 0] which means 2 -> 3 -> 1 -> 0 -> 2 and your distance is d_{2, 3} + d_{3, 1} + d_{1, 0} + d_{0, 2}. Notice this is the same, we just move the first term to the last. This is the same regardless of starting from 3 or 1.

If that does not answer your question, feel free to provide more details.

[Medestrac]

You have perfectly understood the situation, and I agree that distance 1 or 2 make more sense. I understand the circular pattern, but for this example: 0: [Red, Blue], 1: [Red, Green], 2: [Green, Blue], 3: [Purple, Yellow], Say the algorithm return the permutation[0, 1, 2, 3] which implies 6 "cleaning", including the final cleaning If I change the starting point to 1 for the permutation [1, 2, 3, 0] , it implies 7 cleaning, including the final one. Writing this I realise that I need a 5th object as a starting point, with [Clean, Clean]...which is the real start&end point.

Thanks for your help and for your work!

[fillipe-gsm]

Good to know! Good luck on your project!