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

Геннадий Васильевич Степанов

В данной работе по возможности доступно, ясно мной излагаются основные понятия и функционирование параллельной специализированной гибридной вычислительной машины (МПСГВМ).Главное внимание уделено общему представлению об операциях параллельной специализированной гибридной вычислительной машины при решении задач класса NP.Функциональная схема параллельной специализированной гибридной вычислительной машины подчинена схеме метода точного мгновенного решения задач класса 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_уг

Конец ознакомительного фрагмента.