Я столкнулся с проблемой, которая, как мне кажется, связана с проблемой продавца, но я не могу найти правильный способ ее решения.
У меня есть N продавцов и M домов, которые нужно посетить (N - это > = M) каждый продавец отправляется из другого места, поэтому добраться до каждого дома придется по разной цене. Я знаю эти расстояния.
Как мне выбрать лучший набор продавцов, чтобы охватить все дома M?
Если я проверю все возможные перестановки продавцов в наборах M в декартовом произведении со всеми домами будет работать, но это абсурдно дорого для любого большого количества M или N
Кто-нибудь знает, есть ли у этой проблемы конкретное c имя, чтобы я мог искать по ней? Венгерский алгоритм, и хотя он решает проблему, кажется, что венгерский алгоритм решает более широкий класс проблем. В венгерском алгоритме затраты являются произвольными, и между затратами нет ограничений или корреляций.
По описанной мной проблеме я могу назначить для посещения продавца 1, 2 и 3 (S1, S2 и S3) дома 1 и 2 (h1 и H2). Их позиции могут быть, например, S1 S2 h1 S3 h2 над линией. Существует неявная корреляция между затратами из-за того, как расстояния расположены на пространстве. Это действительно сделало бы очень важным способ измерения стоимости посещения (расстояние, которое имеет эти неявные корреляции или другое произвольное значение).
Я все еще пытаюсь выяснить, есть ли название для этой проблемы, которое, похоже, является подклассом проблемы, решаемой венгерским алгоритмом.