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

Необходимо определить, что для нас является более важным, число грузов или их ценность.

Что и требовалось доказать.

Задача о назначениях

Введение

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

В наиболее общей форме задача формулируется следующим образом:

Имеется некоторое число работ и некоторое число исполнителей. Любой исполнитель может быть назначен на выполнение любой одной работы, но с неодинаковыми затратами.

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

Постановка задачи

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

С: А ? Т ? R

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

Метод решения задачи о назначениях

Определяется в качестве числа угадывания (N

) определённое числа исполнителей и подмножеств исполнителей различной мощностью.

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

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

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

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

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

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

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

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

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

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

и N

.

Где К

 – количество подмножеств исполнителей для всех работ, N

 – количество подмножеств исполнителей а N

 – количество угаданных подмножеств исполнителей.