Искусственный разум. Параллельная специализированная гибридная машина. Метод точного мгновенного решения NP задачи - страница 8
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.), где