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

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

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

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

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

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

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

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

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

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

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

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

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

– > P=perms (n)

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

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

Решение.

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

Зададим начальные условия: города A, B, C,D пронумеруем по порядку и присвоим каждому городу номер 1,2,3,4 соответственно. Зададим расстояние между городами матрицами, например. расстояние между городом А и В как матрицу ab, элементами которой является пара 1 и 2 (это номера городов А и В):

– > ab= [1 2];

– > ac= [1 3];

– > ad= [1 4];

– > ba= [2 1];

– > bc= [2 3];

– > bd= [2 4];

– > ca= [3 1];

– > cb= [3 2];

– > cd= [3 4];

– > da= [4 1];

– > db= [4 2];

– > dc= [4 3];

– > M= [1 2 3 4]

M =

– 2. 3. 4.

Найдем все возможные варианты перестановок и получим матрицу Р.

– -> P=perms (M);

Получилась матрица из 4-х столбцов (городов) и строк – вариантов перестановок.

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

В программе не предусмотрена команда замены исходной матрицы, строки которой —это пути, обозначенные последовательным перечислением городов, на матрицу расстояний между этими городами (К примеру, такую бы команду можно было бы назвать between. Значение между элементами со значениями 1 и 2 равно 10, к примеру, как исходные данные between ([1 2]) =10; вставка значений между элементами строк матрицы Р как between (Р:,1)). Поэтому придется пойти обходным путем. Разделим полученную матрицу Р на 3 части, а затем снова соединим, так как между 4-мя городами можно построить путь из трех расстояний между городами. Эти матрицы будут состоять:1-я из первых двух столбцов, 2- я из второго и третьего столбца, 3-я – из третьего и четвертого столбца.

– > N=P;

– > N (:,4) = [];