Любое множество можно записать в виде матрицы с элементами этого множества. Сущность применяемого метода состоит из оперирования над натуральными числами (элементами множеств), применяя матричный подход, то есть оперированием элементами матриц, их столбцов и строками, а также во взаимодействиями между матрицами (множествами).
Общие типовые алгоритмы для задач комбинаторики, таких как задач на перестановки, сочетания, размещения, которые приведены ниже, применимы для 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>6. Задана матрица расстояний между любыми парами городов,
Задачи, подобные по приведенным выше 3-м примерам кажутся неразрешимыми (до сих пор никто не смог доказать, что какая-то из них на самом деле так сложна, как кажется, т.е. что действительно нет возможности получить ответ с помощью компьютера).
Составим модели этих задач в малых числах для нахождения алгоритма и решения этих задач:
Задача-модель №1
Предположим, что вы организуете размещение группы из 5 студентов университета. Количество мест ограничено, и только 3 студента получат места в общежитии. Ситуация усложняется тем, что декан предоставил вам список студентов, которые не могут жить вместе, и просил, чтобы никто из этого списка не попал в окончательный вариант.
Задача-модель №1—1
Предположим, что вы организуете размещение группы из 9 студентов университета. Количество мест ограничено 4 – это 2 комнаты по 2 человека, и только 4 студента получат места в общежитии.
Найти эти решения.
Задача-модель №3.
Требуется найти кратчайший путь, проходящий точно по одному разу через каждый из четырех городов А, B. C. D.>6. Задана матрица расстояний между любыми парами городов,
Решения NP-задач и их задач-моделей аналогичны и имеют одни и те же алгоритмы, решения задач-моделей приведены ниже.
