NP=P? Алгоритмы решения NP-задач матричным методом в программе Scilab. Математическое эссе

Задана матрица расстояний между любыми парами городов,

Задачи, подобные по приведенным выше 3-м примерам кажутся неразрешимыми (до сих пор никто не смог доказать, что какая-то из них на самом деле так сложна, как кажется, т.е. что действительно нет возможности получить ответ с помощью компьютера).

Составим модели этих задач в малых числах для нахождения алгоритма и решения этих задач:

Задача-модель №1

Предположим, что вы организуете размещение группы из 5 студентов университета. Количество мест ограничено, и только 3 студента получат места в общежитии.

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

Задача-модель №1—1

Предположим, что вы организуете размещение группы из 9 студентов университета. Количество мест ограничено 4 – это 2 комнаты по 2 человека, и только 4 студента получат места в общежитии.

Найти эти решения.

Задача-модель №3.

Требуется найти кратчайший путь, проходящий точно по одному разу через каждый из четырех городов А, B.

C. D.

. Задана матрица расстояний между любыми парами городов,

Решения NP-задач и их задач-моделей аналогичны и имеют одни и те же алгоритмы, решения задач-моделей приведены ниже.

– Задание исходных данных

Исходные данные в командах задаются вектором (единичной матрицей), но возможно и двумерной матрицей, несколькими матрицам и т. д. Каждому объекту присваивается порядковый номер. Например, имеем 5 студентов:

Зададим каждому студенту свой номер по порядку: 1.

-первый студент; 2.– 2-й студент….и т. д. до 5. В виде одномерной матрицы n

Запуск программы:

загрузка исходного окружения

– > n= [1 2 3 4 5]

n =

– 2. 3. 4. 5.

– Перестановки

Перестановка осуществляется при помощи команды perms (n):

Теперь найдем все возможные перестановки от 1 до 5-ти, их будет 120. Ответ запишется в виде матрицы, где каждая строка – это вариант одной из перестановок, число строк в матрице будет равно количеству вариантов перестановок, а число столбцов будет равно исходно заданным элементам (в нашем случае 5).

– > P=perms (n)

Перестановки с последующей заменой матрицы и нахождения решений

Как пример со сложной перестановкой (замена матрицы, полученной как перестановки на другую матрицу), задача-модель №3:

Требуется найти кратчайший путь, проходящий точно по одному разу через каждый из четырех городов А, B. C. D.