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