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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Шаг 2) Производится сортировка и запоминание грузов в соответствии с их весом, а также запоминается ценность этих грузов.

Шаг 3) Выбирается значение N уг, и запоминается…

Шаг 4) Выбирается множество грузов с мощностью согласно N угс соответствующими им наилучшими весами и ценами.

Шаг 5) Производится объединения грузов в подмножества грузов по два. Осуществляется запоминание этих подмножеств грузов, с учётом их весов и цен.

Шаг 6) Производится сортировка и запоминание подмножеств грузов по два с соответствующими им наилучшими весами и соответствующей суммарной ценой.

Шаг 7) Выбирается множество подмножеств грузов по два с мощностью согласно N угс соответствующими им наилучшими суммарными весами и соответствующей суммарной ценой.

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

Рис. 4.11. Объединение грузов по три.

Данная процедура объединения подмножеств грузов меньшей мощности в подмножества грузов большей мощности, по различным правилам, должна повторятся до получения подмножеств грузов с числом грузов 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.