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

Шаг 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