Аннотация:
Рассматривается известная NP-трудная задача размещения взаимосвязанных объектов — дискретная задача Вебера. Предлагаются точный и эвристический алгоритмы, решающие исследуемую задачу для простого взвешенного цикла и конечного множества позиций размещения, основанные на динамическом программировании. На классе тестовых задач проведен вычислительный эксперимент по анализу эффективности предложенных алгоритмов в сравнении между собой и с пакетом IBM ILOG CPLEX.
Ключевые слова:задача размещения, задача Вебера, простой цикл, точный алгоритм, эвристический алгоритм, динамическое программирование.
Полный текст:
PDF файл (228 kB)