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

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

К ним относятся:

• метод ветвей и границ;

• метод динамического программирования.

Данные методы являются неэффективными по определению, так как требуют для решения задач КО экспоненциально зависящее от размера задачи время решения. Поэтому для решения задач КО разработаны приближённые эффективные методы.

К ним относятся:

• приближённые алгоритмы с гарантированными оценками качества получаемого решения;

• вероятностные алгоритмы.

В данной работе предлагается эффективный безпереборный метод точного решения комбинаторных оптимизационных задач.

Этот метод разработан на примере задачи коммивояжера (ЗК), которая относится к классу NP и изложен мной в книге «Искусственный разум Задача коммивояжера Проблема перебора P=NP».

Данный метод вместо перебора осуществляет поиск оптимального решения на основе закономерности, присущей задачам комбинаторной оптимизации (ЗКО).

Задача о ранце одна из труднорешаемых задач дискретной математики.

Название своё получила от максимизационной задачи укладки как можно большего числа ценных вещей в ранец при условии, что общий вес (или объём) всех предметов способных поместиться в ранец, ограничен.

Следовательно, эта задача является двухкритериальной.

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

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

В настоящее время не найдено эффективного метода точного решения задачи о ранце.

Пусть для задачи о ранце имеется n грузов. Для каждого i-го груза определён вес и ценность p,. Дана грузоподъёмность W.

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

Принимаем в качестве числа угадывания (N_>уг) определённое числа грузов и объединений грузов различной мощности.