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

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

СКАЧАТЬ проверкой возможности выбрать подмножество грузов мощностью М, так чтобы их общий вес не превышал W.

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

      В результате поиска, согласно данного метода путём увеличения значения Nуг, после получении первого подмножества с мощностью М суммарным весом грузов больше W, процесс поиска заканчивается. Затем осуществляется выбор локального оптимума решения задачи о ранце с мощностью меньше М, путём уменьшения значения М и выбора Nуг.

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

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

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

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

      Где Кw – количество подмножеств мощностью М с суммарным весом грузов больше или равно W, Nm– шкала количества подмножеств грузов мощностью М, а Nуг – количество угаданных подмножеств грузов.

      Метод включает:

      1) выбор множества грузов с максимальной мощностью М, так чтобы их общий вес не превышал W, путём выбора грузов М с минимальным весом;

      2) упорядочение множества грузов по возрастанию веса;

      3) объединения грузов в подмножества грузов по два с последующим упорядочением и выбором этих подмножеств грузов с их наилучшими суммарными весами и соответствующей суммарной ценой согласно Nуг;

      4) поэтапное объединение подмножества грузов меньшей мощностью грузов в подмножества грузов большей мощностью с последующим упорядочением до получения подмножеств грузов с числом грузов (М+1)/2 для М нечетных и с числом грузов М/2 +1 для М чётных и выбором, в дальнейшем, множества грузов подмножеств грузов большей мощности с их наилучшими суммарными весами и соответствующей суммарной ценой согласно Nуг.;

      5) итерационный поиск подмножества грузов с числом грузов М с суммарным весом грузов больше или равно W;

      6) выбор из множества подмножеств с максимальной мощностью М, подмножества, с суммарным весом грузов меньше или равно W, суммарная ценность грузов в котором была бы максимальной, путём перебора конечного числа этих подмножеств, т.е. получение искомого результата;

      7) выбор локального оптимума решения задачи о ранце путём уменьшения значения М и выбора Nуг.

      Алгоритм решения задачи о ранце

      Шаг 1) Выбор подмножества СКАЧАТЬ