Оглавление

1. Искусственный разум. Параллельная специализированная гибридная машина
2. Введение
   1. Модель параллельной специализированной гибридной вычислительной машины
3. Задача о ранце
   1. Введение
   2. Постановка задачи о ранце
   3. Метод решения задачи о ранце
   4. Алгоритм решения задачи о ранце
   5. Демонстрационный пример решения задачи о ранце
4. Задача о назначениях
   1. Введение
   2. Постановка задачи
   3. Метод решения задачи о назначениях
   4. Алгоритм решения задачи о назначениях
   5. Демонстрационный пример решения задачи о назначениях
5. Задача о назначении целей
   1. Введение
   2. Постановка задачи о назначении целей
   3. Метод решения задачи о  назначении целей
   4. Алгоритм решения задачи о назначении целей
   5. Демонстрационный пример решения задачи о назначении целей
6. Транспортная задача
   1. Введение
   2. Постановка транспортной задачи
   3. Метод решения транспортной задачи
   4. Алгоритм решения транспортной задачи
   5. Демонстрационный пример решения транспортной задачи
7. Задача теории расписаний
   1. Введение
   2. Постановка задачи теории расписаний
   3. Метод решения задачи теории расписаний
   4. Алгоритм решения задачи теории расписаний
   5. Демонстрационный пример решения задачи теории расписаний
8. Задача Штейнера
   1. Введение
   2. Постановка задачи Штейнера
   3. Метод решения задачи Штейнера
   4. Алгоритм решения задачи Штейнера
   5. Демонстрационный пример решения задачи Штейнера
9. Структурная схема модели параллельной специализированной гибридной вычислительной машин
   1. Алгоритм решения задачи коммивояжёра на МПСГВМ
   2. Алгоритм решения задачи о ранце на МПСГВМ
   3. Алгоритм решения задача о назначениях на МПСГВМ
   4. Алгоритм решения задачи о назначении целей на МПСГВМ
   5. Алгоритм решения транспортной задачи на МПСГВМ
   6. Алгоритм решения задачи теории расписаний на МПСГВМ
   7. Алгоритм решения задачи Штейнера на МПСГВМ
10. Заключение
    1. Выводы
    2. Список сокращений
    3. Литература

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение

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

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

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

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

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

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

Постановка задачи о ранце

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

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

Метод решения задачи о ранце

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

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

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

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

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

В результате поиска, согласно данного метода путём увеличения значения N_уг, после получении первого подмножества с мощностью М суммарным весом грузов больше W, процесс поиска заканчивается. Затем осуществляется выбор локального оптимума решения задачи о ранце с мощностью меньше М, путём уменьшения значения М и выбора N_уг.

Индикатором нахождения оптимального решения является само появле