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

Чтение книги онлайн.

СКАЧАТЬ и с числом грузов 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.

      Согласно моего СКАЧАТЬ