Геннадий Степанов - Искусственный разум. Параллельная специализированная гибридная машина. Метод точного мгновенного решения NP задачи

В настоящее время неизвестен эффективный точный метод решения задачи о назначениях.

Для задачи о назначениях даны два множества А и Т одного размера и задана функция стоимости

С: А × Т → R

Необходимо найти биекцию ƒ: А → Т такую, что целевая функция

Определяется в качестве числа угадывания (N уг) определённое числа исполнителей и подмножеств исполнителей различной мощностью.

Первоначально осуществляется объединение исполнителей по два и упорядочение по затратам подмножеств исполнителей. В дальнейшем проводиться поэтапное объединение исполнителей в конечные подмножества исполнителей, с увеличением мощности подмножества с упорядочением этих подмножеств по возрастанию затрат, до получения подмножества исполнителей мощностью m , где

m = ( М+ 1)/2 для нечётной мощности множества исполнителей ( M) и

m = M /2+1 для M чётных.

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

В результате поиска, согласно данного метода путём увеличения значения N уг, после получении первого подмножества с мощностью М процесс поиска заканчивается.

Индикатором нахождения оптимального решения является само появление первого подмножества исполнителей мощностью М .

Для данного метода существует зависимость, согласно закономерности, присущей задачам комбинаторной оптимизации, которая является объективной.

В общем виде её можно представить в виде положительного градиента со сдвигом относительно начала координат.

Рис. 4.15. Выявленная зависимость между К ии N m.

Где К и – количество подмножеств исполнителей для всех работ, N m – количество подмножеств исполнителей а N уг – количество угаданных подмножеств исполнителей.

Шаг 1) Определяем в качестве числа угадывания (N уг) определённое числа исполнителей и подмножеств исполнителей различной мощностью.

Шаг 2) Производится сортировка и запоминание исполнителей в соответствии с их затратами.

Шаг 3) Выбирается значение N уг, и запоминается…

Шаг 4) Выбирается множество исполнителей с мощностью согласно N угс соответствующими им наилучшими затратами.

Шаг 5) Производится объединения исполнителей в подмножества исполнителей по два и запоминание этих подмножеств исполнителей, с учётом их затрат.

Шаг 6) Осуществляется сортировка и запоминание подмножеств исполнителей по два с соответствующими им наименьшими затратами.

Шаг 7) Выбирается множество подмножеств исполнителей по два с мощностью согласно N угс соответствующими им наименьшими затратами

Шаг 8) Производится объединения исполнителей по два в подмножества исполнителей по три и запоминание этих подмножеств с их наименьшими затратами.

Рис.4.16. Объединение исполнителей по 3.

Данная процедура объединения подмножеств исполнителей меньшей мощности в подмножества исполнителей большей мощности, по различным правилам, должна повторятся до получения подмножеств исполнителей с числом исполнителей m = ( М+ 1) /2 для М нечётных и с числом исполнителей m = M /2+1 для M чётных (пример объединения исполнителей в подмножество показан на рис.4.17.), где М является мощностью множества исполнителей.

Рис. 4.17. Пример объединения исполнителей в подмножество.

После каждого объединения, производится сортировка подмножеств исполнителей большей мощности в соответствии с их наименьшими затратами и запоминание этих подмножеств исполнителей большей мощности с их затратами, а затем выбор подмножеств исполнителей большей мощности с их наименьшими затратами согласно N уг.Если множество подмножеств исполнителей большей мощности в результате объединения на каком-то этапе данного объединения будет пусто то увеличиваем N уг