0

Я пытаюсь решить эту проблему: Jobs. До сих пор я думал, что проблема такая же, как у Assignment Problem с дистрибьюторами и районами, представленными как двудольный граф, и ребрами, представляющими вероятность. Но здесь нам нужно максимизировать произведение, а не сумму весов согласованных ребер.Максимальное соответствие продукта в двухсторонних графиках

Одна идея, которая пришла мне в голову, заключалась в том, чтобы изменить каждый вес к логам (вес). Тогда проблема существенно меняется на нахождение максимальной суммы, которая затем может быть решена с использованием алгоритмов для Assignment Problem. Но это создает проблему, так как применение журнала сделает весы нецелого числа, что я считаю, что венгерский алгоритм не работает.

Просьба предложить другой альтернативный подход.

ответ

1

Теоретически венгерский алгоритм отлично работает с реальными весами.

На практике возможно, что, поскольку большинство целочисленных логарифмов не могут быть представлены точно как числа с плавающей запятой, может получиться, что округление изменит оптимальное решение. Есть способы справиться с этим даже так, но маловероятно, что вам понадобятся они для этой проблемы программирования.