Искусственный разум. Параллельная специализированная гибридная машина. Метод точного мгновенного решения NP задачи - страница 6
Индикатором нахождения искомого результата является само появление такого подмножества грузов мощности М, суммарный вес грузов которого будет больше или равен 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. Выявленная зависимость между К>w3 и N>m.
Где К>w3 – количество подмножеств грузов по три, с суммарным весом грузов больше или равно W.
N>m – шкала угадывания количества подмножеств грузов.
N>уг – количество угаданных подмножеств грузов.
Согласно данного метода определим локальное оптимальное решения задачи о ранце для значений:
М = 2 и N>уг = 4.
Рассмотрим таблицу 6 для значений