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

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

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

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

Математическое эссе

Людмила Наумова

© Людмила Наумова, 2018

ISBN 978-5-4493-7193-5

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

Введение

Из курса школьной математики нам все известны задачи комбинаторики, такие как задачи на перестановки, сочетания, размещения, представленные соответствующими формулами. Но эти формулы дают нам только количество решений, а не сами решения. Общих типовых алгоритмов самих решений на эти типы задач не было. Эти типы задач с большими числами можно отнести к NP задачам. Но с помощью программы Scilab раскрываются типовые алгоритмы таких задач и выдаются сами решения, и не только количество решений. Суть алгоритмов состоит в оперировании с элементами натурального ряда в строках и столбцах матрицы, а также в оперировании со строками и столбцами матрицы с помощью команд Scilab. NP- задачи, в принципе, представляют все те же задачи комбинаторики, но в больших числах. Так в одной NP- задаче могут присутствовать сразу как перестановки, так и сочетания и размещения, могут быть эти операции (сочетания, размещения, перестановки) последовательно повторяться, но уже с другими, полученными в ходе решения задачи, данными, могут быть заданы дополнительные еще какие либо условия или вычисления. Суть в том, что зная типовые алгоритмы перестановок, размещения, сочетания, эти алгоритмы можно использовать сколько угодно в одной задаче и таким образом решать NP задачи. Подчеркнем еще раз, что приведенные ниже алгоритмы дают сами решения, а не только ответы о количестве решений, хотя и их тоже дают. В больших числах решение этих задач требует большой разрешительной мощности компьютера, но алгоритмы остаются все те же. В данной книге приводятся примеры с малыми числами, но суть дела остается та же. Тем самым, автор хочет показать, что часто решение задачи лежит на поверхности, но мы иногда не можем увидеть решение под таким углом. Автор уверен, что все больше NP-задач будет переходить в разряд P- задач. Этот процесс неизбежен с развитием программ и ростом мощности компьютеров.

Глава 1. Сущность метода, команды и типовые алгоритмы в программе Scilab 6.0.1

– Сущность метода

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

Общие типовые алгоритмы для задач комбинаторики, таких как задач на перестановки, сочетания, размещения, которые приведены ниже, применимы для NP- задач. Эти типы задач (на перестановки, сочетания, размещения) с большими числами можно отнести к NP- задачам. NP- задачи, по сути своей, представляют все те же задачи комбинаторики, но в усложненном варианте, в одной задаче могут присутствовать сразу как перестановки, так и сочетания и размещения, могут быть эти операции (сочетания, размещения, перестановки) последовательно повторяться, но уже с другими полученными в ходе решения задачи данными, могут быть заданы дополнительные еще какие либо условия или вычисления. Но с помощью программы Scilab раскрываются типовые алгоритмы таких задач и выдаются сами решения, а не только количество решений. Суть в том, что зная типовые алгоритмы перестановок, размещения, сочетания, их можно использовать сколько угодно как типовые алгоритмы в одной задаче и таким образом решать NP- задачи.

– NP-задачи и их модели в малых числах, общие алгоритмы

Приведем примеры NP-задач:

Задача №1.

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

Задача №2.

Верно ли, что среди чисел {—2, —3, 15, 14, 7, —10, …} есть такие, что их сумма равна 0?

Или еще, например, примерно такая же задача: 50, 2, 47, 5, 21, 4, 78, 1. Задача: можно ли подобрать среди этих чисел такие, что их сумма даст 100?

Задача №3.

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

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

Задачи, подобные по приведенным выше 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.

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

Решение.

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