Многомерная проблема назначения

Многомерная задача назначения (MAP) — это фундаментальная задача комбинаторной оптимизации , предложенная Уильямом Пирскалла . Эту проблему можно рассматривать как обобщение линейной задачи о назначениях . На словах проблему можно описать так:

Экземпляр задачи имеет несколько агентов (т. е. параметр мощности ) и ряд характеристик работы (т. е. параметр размерности ), таких как задача, машина, временной интервал и т. д. Например, агенту можно назначить выполнение задачи. X, на машине Y, в течение интервала времени Z. Любой агент может быть назначен для выполнения задания с любой комбинацией уникальных характеристик задания за определенную стоимость . Эти затраты могут варьироваться в зависимости от назначения агента комбинации характеристик работы — конкретной задачи, машины, временного интервала и т. д. Проблема состоит в том, чтобы минимизировать общую стоимость назначения агентов так, чтобы назначение агентов каждой характеристике работы было или инъективная функция функция «один к одному» от агентов к заданной характеристике работы.

Альтернативно, описав проблему с помощью теории графов:

Задача многомерного назначения состоит в поиске во взвешенном многодольном графе паросочетания заданного размера , в котором сумма весов ребер минимальна.

Формальное определение

В литературе можно встретить различные постановки этой проблемы. Используя функции затрат, $D$– проблема назначения размерностей (или $D$–MAP ) можно сформулировать следующим образом:

Данный $D$ наборы, $A$ и $J_{1},\ldots J_{D-1}$, одинакового размера, вместе с массивом стоимости или многомерной весовой функцией $C$ : $A\times J_{1}\times \ldots \times J_{D-1}\rightarrow \mathbb {R} _{+}$, находить $D-1$ перестановки $\pi _{d}$ : А → $J_{d}$ такая, что функция полной стоимости :

$\sum _{a\in A}C(a,\pi _{1}(a),\ldots ,\pi _{D-1}(a))$

сведен к минимуму.

Параметры задачи

Задача многомерного назначения (MAP) имеет два ключевых параметра, определяющих размер экземпляра задачи :

1. Параметр размерности ​ $D$
2. Параметр мощности ​ $N=|A|$, где $|A|$ обозначает количество элементов в $A$.

Размер массива затрат

Любой проблемный экземпляр MAP с параметрами $D,N$ имеет свой конкретный массив затрат $C$, который состоит из $N^{D}$ параметры стоимости/веса для конкретного экземпляра $C(a,a_{1},\ldots ,a_{D-1})$. $N^{D}$ — размер массива затрат.

Количество возможных решений

Допустимая область или пространство решений MAP очень велико. Число $K$ возможных решений (размер экземпляра MAP) зависит от параметров MAP $D,N$. Конкретно, $K=(N!)^{D-1}$.

Вычислительная сложность

Проблема вообще NP-сложная . Другими словами, не существует известного алгоритма решения этой задачи за полиномиальное время, поэтому для решения экземпляров задачи даже умеренного размера (на основе параметров размерности и мощности) может потребоваться длительное время вычислений.

Приложения

Проблема нашла применение во многих областях:

• Планирование (производственные процессы)
• Объединение данных нескольких датчиков
• Связь записей или разрешение многосторонних объектов
• Физика элементарных частиц
• Обнаружение падения у пожилых людей с помощью небольших носимых устройств