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

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

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

К таким задачам относятся:

• задача коммивояжера;

• задача Штейнера;

• задача о ранце;

• задача о назначениях;

• задача о назначении целей;

• транспортная задача.

Доказано что они являются труднорешаемыми и относятся к классу NP. Для данного класса задач существующая проблема перебора в теории алгоритмов является открытой. Утверждается, что если будет решена эта проблема, то задачи класса NP можно будет решать с помощью одного единственного эффективного метода, так как эти задачи можно свести друг к другу.

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

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

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

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

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

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

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

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

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

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

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

Задача о ранце

Введение

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

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

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