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

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

Страниц

30

Год

—

В данной работе рассмотрена специализированная гибридная вычислительная машина (МПСГВМ), предназначенная для решения задач класса NP. В тексте изложены основные понятия и принципы функционирования данной машины.

МПСГВМ представляет собой сложную систему, объединяющую параллельные и специализированные вычислительные элементы. Эта машина обладает высокой производительностью и позволяет эффективно решать задачи с NP-трудностью.

Основным принципом работы МПСГВМ является использование метода точного мгновенного решения задач класса NP. Это означает, что машина способна быстро и точно находить оптимальное решение для сложных задач, которые обычно требуют экспоненциального времени для решения.

Функциональная схема МПСГВМ состоит из нескольких блоков, каждый из которых отвечает за выполнение определенных операций. Важным элементом данной схемы является параллельная обработка данных, что позволяет существенно ускорить процесс решения задач.

В своей работе я также провел дополнительные исследования, чтобы более подробно разобраться в особенностях МПСГВМ. Мои исследования позволили выявить некоторые улучшения, которые могут быть внесены в функциональную схему машины, чтобы повысить ее производительность и эффективность.

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

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

© Геннадий Васильевич Степанов, 2020


ISBN 978-5-4498-5282-3

Создано в интеллектуальной издательской системе Ridero

Введение

В данной работе по возможности доступно, ясно мной излагаются основные понятия и функционирование параллельной специализированной гибридной вычислительной машины (МПСГВМ).

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

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

В данной работе предлагается эффективный безпереборный метод точного решения на МПСГВМ следующих комбинаторных оптимизационных задач:

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

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

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

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

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

• задача теории расписаний;

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


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

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

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

Модель параллельной специализированной гибридной вычислительной машины

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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


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

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

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

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


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

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

Вам может понравиться: