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

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

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

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

Рис. 4.12.Пример объединения грузов.

Шаг 9) В полученном множестве подмножеств грузов большей мощности числом грузов равным осуществляем их объединение, для получения множества подмножеств грузов мощности М. Если множества подмножеств грузов мощности М будет пусто то увеличиваем N

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

на определённое значение и запоминаем. Переходим к шагу 3. Иначе выбираем из полученного множества подмножеств грузов мощности М подмножество грузов с суммарным весом грузов меньше или равно W и с максимальной суммарной ценой, которое и будет искомым решением задачи о ранце.

Шаг 10) Уменьшаем значение М на 1, выбираем N

, и запоминаем. Если М> 0 то переходим к шагу 3. Иначе переходим к шагу11.

Шаг 11) Выбираем, из полученного множества локальных подмножество грузов с максимальной суммарной ценой для различных уменьшенных значений М, подмножество грузов с максимальной суммарной ценой, который и будет локальным оптимумом решения задачи о ранце.

Индикатором нахождения искомого результата является само появление такого подмножества грузов мощности М, суммарный вес грузов которого будет больше или равен W.

Демонстрационный пример решения задачи о ранце

Для задачи о ранце определим, что ранец имеет грузоподъёмность W = 12. Количество грузов n = 5. Значения весов грузов W зададим в виде таблицы 3.

Таблица 3. Определение весов грузов

Для данного множества грузов максимальная мощность подмножеств грузов М = 3.

Согласно моего метода, для получения оптимального решения задачи о ранце, необходимо чтобы:

m = (М+1) /2 для M для нечётных;

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

Для данного примера задачи о ранце: М = 3, m = 2.

Значения цены грузов P зададим в виде таблицы 4.

Таблица 4. Определение цены грузов

С помощью метода неявного перебора был получен оптимальный результат для данного примера задачи о ранце:

W = W2 + W4 = 4 + 8 = 12

P = P2 + P4 = 6 + 7 = 13

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

Произведём объединение грузов из множества грузов в подмножества грузов по два и по три.

Полученные упорядоченные вектора подмножества грузов по два и по три и их значений суммарных весов грузов и цен занесём в таблицу 5.

Таблица 5. Определённый и полученные упорядоченные вектора грузов

Из таблицы 5 видно, что для определения глобального оптимального результата в данном примере задачи о ранце: для данного метода достаточно чтобы N

= 3. Искомый результат:

W = W1 + W2 + W3 = 3 + 4 + 5 = 12

P = P1 + P2 + P3 = 1 + 6 + 4 = 11

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

Основываясь на данных из таблицы, определим зависимость числа подмножеств по три (Kw3) с суммарным весом грузов больше или равно W = 12, от числа угадывания (N) на шкале угадывания (Nm) для данного метода.

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

и N

.

Где К

 – количество подмножеств грузов по три, с суммарным весом грузов больше или равно W.

N

 – шкала угадывания количества подмножеств грузов.

N

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

Согласно данного метода определим локальное оптимальное решения задачи о ранце для значений:

М = 2 и N

 = 4.

Рассмотрим таблицу 6 для значений М = 2 и N

 = 4.

Таблица 6. Определённый и полученный упорядоченныйвектор грузов для М = 2 и N

= 4.