Посмотрите пожалуйста это видео и книгу.
Выделите следующую строчку и сделайте ввод правой кнопкой мыши. В появившемся окошке укажите "Перейти по адресу" :
https://vk.com/video589743012_456239017
https://ridero.ru/books/widget/iskusstvennyi_razum_zadacha_kommivoyazhera/
С полной версией данной статьи можно ознакомиться в книгах:
Г. Степанов
Искусственный разум. Задача коммивояжера Проблема перебора P=NP
Екатеринбург: ООО «Издательство Ридеро», 2020
ISBN: 978-5-4498-3818-6;
Г. Степанов
Искусственный разум. Параллельная специализированная гибридная вычислительная машина Метод точного мгновенного решенияNPзадачи
Екатеринбург: ООО «Издательство Ридеро», 2020
ISBN: 978-5-4498-5282-3.
Задача о ранце одна из труднорешаемых задач дис-
кретной математики.
Название своё получила от максимизационной зада-
чи укладки как можно большего числа ценных вещей
в ранец при условии, что общий вес (или объём) всех
предметов способных поместиться в ранец, ограничен.
Следовательно, эта задача является двухкритериаль-
ной.
На первом этапе решения необходимо найти множе-
ство подмножеств грузов с максимальной мощностью
числа ценных вещей помещаемых в рюкзак, с учётом
ограничения для ранца по весу W, а затем выявить мак-
симальную суммарную ценность грузов в результате пе-
ребора конечного числа этих подмножеств с целью полу-
чить глобальное оптимальное решение.
На втором этапе решения нужно определить локаль-
ный оптимум решения задачи о ранце, уменьшая мощ-
ность подмножеств грузов.
В настоящее время не найдено эффективного метода
точного решения задачи о ранце.
Постановка задачи о ранце
Пусть для задачи о ранце имеется n грузов. Для каж-
дого i-го груза определён вес и ценность p,. Дана грузо-
подъёмность W.
Необходимо выбрать подмножество грузов макси-
мальной мощностью, так чтобы их общий вес не превы-
шал W, а суммарная их ценность была бы максимальной.
Метод решения задачи о ранце
Принимаем в качестве числа угадывания (Nуг) опре-
делённое числа грузов и объединений грузов различной
мощности.
Предварительно необходимо выбрать подмножества
грузов с максимальной мощностью М, так чтобы их об-
щий вес не превышал W, путём выбора М грузов с мини-
мальным их весом, и запомнить это число.
Первоначально осуществляется объединение и упо-
рядочение по весу подмножества грузов по два. В даль-
нейшем проводиться поэтапное объединение грузов
в конечные подмножества грузов, с увеличением мощно-
сти подмножества с упорядочением этих подмножеств
по возрастанию веса, до получения множества грузов
мощностью М по различным правилам.
Конечные подмножества проверяются по суммарно-
му весу, которые не должны превышать W. Осуществ-
ляется итерационное угадывание количества этих под-
множеств с различной мощностью, с последующей
проверкой возможности выбрать подмножество грузов
мощностью М, так чтобы их общий вес не превы-
шал 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) Выбор подмножества грузов с максимальной
мощностью М, так чтобы их общий вес не превосходил
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.
Демонстрационный пример решения
задачи о ранце
Для задачи о ранце определим, что ранец имеет гру-
зоподъёмность 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 и Nm.
Где Кw3 — количество подмножеств грузов по три,
с суммарным весом грузов больше или равно W.
Nm — шкала угадывания количества подмножеств
грузов.
Nуг — количество угаданных подмножеств грузов.
Согласно данного метода определим локальное опти-
мальное решения задачи о ранце для значений:
М = 2 и Nуг = 4.
Рассмотрим таблицу 6 для значений М = 2 и Nуг = 4.
Таблица 6. Определённый и полученный упорядоченный
вектор грузов для М = 2 и Nуг = 4.
Из таблицы 6 определим локальное оптимальное ре-
шения задачи о ранце:
W = W2 + W4 = 4 + 8 = 12
P = P2 + P4 = 6 + 7 = 13
Согласно метода, определим локальное оптимальное
решения задачи о ранце для значений М = 1 и Nуг = 5 со-
гласно таблицы 7.
Таблица 7. Определённый вектор грузов для
М = 1 и Nуг = 5
Из таблицы 7 определим локальное оптимальное ре-
шения задачи о ранце для М = 1 и Nуг = 5 :
W = W4 = 8
P = P4 = 7
Исходя из вышеизложенного выбираем локальный
оптимальный результат данного примера задачи о ранце:
W = W2 + W4 = 4 +8 = 12
P = P2 + P4 = 6 + 7 = 13.
Таким образом, без перебора вариантов решения зада-
чи о ранце, находим данным методом локальный опти-
мальный результат и глобальный оптимального результат
для данного примера задачи о ранце с помощью моего
метода. Определение лучшего результата требует выпол-
нение дополнительных условий. Необходимо опреде-
лить, что для нас является более важным, число грузов
или их ценность.
Что и требовалось доказать.