Finding the best fit of 3 categories ( restaurants/meal/person analogy problem )

68 Views Asked by At

I have this problem that sounds tedious and long and I'm not sure if there exist an intuitive way to solve it. The problem is related to image recognition but I will try to give an analogy to it

You have 4 people and each can rate 8 meals in 4 restaurants [ The rating from 1-9]

Now we have a sheet for each person rating
Here x-axis represent restaurants and Y-axis represents meals

[2 3 5 9 3 5 2 3]

[3 5 6 7 9 3 2 1]

[4 3 2 1 7 9 9 2]

[9 8 4 1 2 5 6 9]

This is matrix represent the rating of one (of four) person based on the meals

We will end up with 4 of these (one for each person)

What we want to do is to have the lowest possible combined rating if we distribute each person to one restaurant ( one person for each restaurant/ there is no restriction for meals so they can all use same meal number or different ones)

The answer for example could be

Rest 1 --> Person 3 Meal 5

Rest 2 --> Person 1 Meal 5

Rest 3 --> Person 2 Meal 1

Rest 4 --> Person 4 Meal 3

Combining the numbers of all meals, we get the least possible rating

1

There are 1 best solutions below

1
On BEST ANSWER

This looks like the assignment problem https://en.wikipedia.org/wiki/Assignment_problem where the "agent" is the person, the "task" is the restaurant, and the "cost" of assigning Person X to Restaurant Y (and therefore, Restaurant Y to Person X) is Person X's lowest rated meal at Restaurant Y.

The reason we would use the lowest rated meal as the cost is that given an assignment in which Rest Y -> Person X, Meal Z, if Meal Z is not one of Person X's lowest rated meals at Restaurant Y, then we could find an assignment with a lower combined rating using the assignment with Rest Y -> Person X, Meal Z', where X rates Meal Z' lower than Meal Z.