Глава 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. F6. Задана матрица расстояний между любыми парами городов,
Задачи, подобные по приведенным выше 3-м примерам кажутся неразрешимыми (до сих пор никто не смог доказать, что какая-то из них на самом деле так сложна, как кажется, т.е. что действительно нет возможности получить ответ с помощью компьютера).
Составим модели этих задач в малых числах для нахождения алгоритма и решения этих задач:
Задача-модель №1
Предположим, что вы организуете размещение группы из 5 студентов университета. Количество мест ограничено, и только 3 студента получат места в общежитии. Ситуация усложняется тем, что декан предоставил вам список студентов, которые не могут жить вместе, и просил, чтобы никто из этого списка не попал в окончательный вариант.
Задача-модель №1—1
Предположим, что вы организуете размещение группы из 9 студентов университета. Количество мест ограничено 4 — это 2 комнаты по 2 человека, и только 4 студента получат места в общежитии.
Найти эти решения.
Задача-модель №3.
Требуется найти кратчайший путь, проходящий точно по одному разу через каждый из четырех городов А, B. C. D.6. Задана матрица расстояний между любыми парами городов,
Решения 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.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) = [];
— > N (:,3) = [];
— > A=N;
— > X=P;
— > X (:,1) = [];
— > X (:,3) = [];
— > X (:,3) = [];
— > Q=P;
— > Q (:,1) = [];
— > Q (:,1) = [];
— > T=cat (2,A,X,Q);
Создадим матрицу U, такую, что заменит значения элементов матрицы Т (то есть номера городов) на расстояния между ними из условия задачи. Например, в строке элементы записаны как [1 2 2 3 3 4] запишутся как [ab bc cd].
— > U= [dc cb ba; dc ca ab; db bc ca; db ba ac; da ac cb; da ab bc; cd db ba; cd da ab; cb bd da; cb ba ad;
ca ad db; ca ab bd; bd dc ca; bd da ac; bc ca ad; bc cd da; ba ad dc; ba ac cd; ad dc cb; ad db bc; ac cd db;
ac cb bd; ab bd dc; ab bc cd];
Расстояния между городами нам известны по условию задачи, зададим их и снова запишим матрицу:
— > ab= [10 0];
— > ac= [5 0];
— > ad= [4 0];
— > ba= [10 0];
— > bc= [3 0];
— > bd= [6 0];
— > ca= [5 0];
— > cb= [3 0];
— > cd= [7 0];
— > da= [4 0];
— > db= [6 0];
— > dc= [7 0];
— > U= [dc cb ba; dc ca ab; db bc ca; db ba ac; da ac cb; da ab bc; cd db ba; cd da ab; cb bd da; cb ba ad;
ca ad db; ca ab bd; bd dc ca; bd da ac; bc ca ad; bc cd da; ba ad dc; ba ac cd; ad dc cb; ad db bc; ac cd db;
ac cb bd; ab bd dc; ab bc cd];
Суммируем строки полученной матрицы и найдем наименьший элемент:
— > Y=sum (U,2);
— > min (Y)
ans =
12.
Наименьшее расстояние равно 12. Создадим Н и найдем пересечение матриц, для нахождения строки и определения пути.
— > H= [12];
— > [c, iY, iH] =intersect (Y (:),H (:))
iH =
1.
iY =
5.
c =
12.
Мы видим, что пересечение матриц со значением элемента 12, указывает на строку 5 в матрице Y. Строка 5 в матрице Т указывает путь:
T (5,:)
ans =
4. 1. 1. 3. 3. 2.
Первый вариант ответа кратчайший путь 12 км. Это путь от города 4 до города 1, затем от города 1 до города 3, затем от города 3 до города 2.
Но, это ответ, может быть не единственным, поэтому зададим элементу 5-й строки полученной матрицы Y значение большее минимального расстояния 12 км., например 12+1=13 и повторим процедуру пересечения матриц
— > Y (5,1) =13;
— > [c, iY, iH] =intersect (Y (:),H (:));
Так будем повторять и записывать варианты ответов, исходя из номера строки пересечения, пока пересечение матриц не даст пустое множество.
— Размещения
Количество мест ограничено, и только 3 (три) студента из 5 получат места в общежитии. Найти все варианты размещения.
Для нахождения решений удалим последние столбцы в полученной при перестановках матрице (5—3=2). Удаляем два столбца, чтобы осталось три столбца, так как только 3 человека могут получить место.
— > P (:,5) = []
— > P (:,4) = []
Исключим одинаковые строки в матрице Р:
— > M=unique (P,1)
Отсортируем строки полученной матрицы М в порядке убывания:
— > V=gsort (M,’c’)
Снова удалим одинаковые строки отсортированной матрицы V:
— > Y=unique (V,1)
Получится искомый ответ, каждая строка матрицы будет как вариант размещения.
Количество таких размещений будет равно числу строк:
— > size (Y)
А число столбцов — это число мест, по которым требовалось разместить студентов.
— Выполнение дополнительных условий в задаче
Но декан задал условие, чтобы 3-тий,1-ый, и 5-й студент не поселились вместе. Зададим это условие как одномерную матрицу Z:
— > Z= [3 1 5]
Z =
3. 1. 5.
Отсортируем матрицу Z в порядке убывания:
— > R=gsort (Z)
Найдем пересечение строк матриц R и Y:
T=intersect (R,Y,1)
Нахождение индекса общей строки для матриц R и Y:
— > [c, iR, iY] =intersect (R,Y,1)
iY =
6.
iR =
1.
c =
5. 3. 1.
Таким образом, необходимо удалить 6-ю строку матрицы Y, чтобы выполнить условие декана и получить окончательные варианты ответов в виде строк матрицы:
Y (6,:) = []
Еще раз найдем пересечение строк матриц R и Y и удалим строку равную полученному iY, и так повторим, пока не будет ответом пересечения матриц пустое множество.
Получим окончательные ответы задачи — это строки матрицы Y как все варианты ответов.
— Сложные размещения
Задача-модель №1—1
Другой пример размещения: 9 студентов могут разместиться только в 2-х комнатах попарно, то есть всего 4 места. Найти все эти пары-решения.
Для экономии места пояснений, предположим, что мы уже нашли решение размещения 9 студентов на 4 местах в виде строк матрицы (предположим матрица Е) аналогично задаче №1 (получится матрица из 4-х столбцов — количество мест, и строк — равных количеству решений). Теперь из всех вариантов, представленных в каждой полученной строке матрицы Е надо выбрать всевозможные варианты пар. Для этого каждую строку полученной матрицы E представляем в виде начального условия — одномерной матрицы, из четырех чисел одномерных матриц надо получить всевозможные варианты пар. Каждый вариант, будет представлен парами, полученными в виде строк конечной матрицы.
Вариант получения из одной одномерной матрицы Р всех возможных пар представлен ниже, но нахождение из остальных одномерных матриц всех возможных пар аналогично.
Решение:
Запуск программы:
загрузка исходного окружения
— > n= [5 3 1 4]
n =
5. 3. 1. 4.
Находим все возможные перестановки строки матрицы Р
— > P=perms (n)
Так как комнат по условиям задачи 2 шт., разделим матрицу Р на 2 матрицы с равным количеством столбцов: то есть одна матрица с первыми двумя столбцами, другая с 3-м и 4-м столбцами, и отсортируем строки полученных двух матриц в порядке убывания.
— > F=P
— > F (:,4) = []
— > F (:,3) = []
— > V=gsort (F,’c’)
— > K=P
— > K (:,1) = []
— > K (:,1) = []
— > Q=gsort (K,’c’)
После сортировки двух матриц объединим их и удалим одинаковые строки в полученной матрице
— > W=cat (2,V,Q)
Исключим одинаковые строки и найдем искомый ответ
— > U=unique (W,1)
Ответ: варианты пар в каждой строке матрицы, то есть первый вариант — первая строка — это 1-я комната из двух студентов в 1–м и 2-м столбце, т.е. под номерами 3,1; 2-я комната из двух студентов в 3–м и 4-м столбце, т.е. под номерами 5,4. Второй вариант — это 2-я строка — это 1-я комната из двух студентов в 1–м и 2-м столбце, т.е. под номерами 4,1; 2-я комната из двух студентов в 3–м и 4-м столбце, т.е. под номерами 5,3 и т. д. И так все строки полученной матрицы U. Но как мы писали в начале решения задачи модели №1—1, это только ответ, полученный из одной из строк матрицы Е. Все то же самое надо проделывать со всеми строками матрицы Е.
— Решение задач сочетаний и размещений при помощи нулей в строках исходной матрицы
Числа 2, 9,6. Задача: можно ли подобрать среди этих чисел такие, что их сумма даст 17?
Так как нам надо подобрать всевозможные сочетания и найти их сумму зададим одномерную матрицу с равным количеством нулей сколько и количество исходных чисел:
загрузка исходного окружения
— > n= [0 0 0 2 9 6]
n =
0. 0. 0. 2. 9. 6.
Отсортируем исходную матрицу для удобства вычислений в порядке убывания.
— > m=gsort (n)
m =
9. 6. 2. 0. 0. 0.
Найдем все варианты перестановок
— > v=perms (m)
Удалим последние столбцы — 3 столбца, так количество дополнительных нулей в исходной матрице было 3.
— > v (:,6) = []
— > v (:,5) = []
— > v (:,4) = []
Отсортируем полученную матрицу в порядке убывания:
— > x=gsort (v)
Исключим одинаковые строки:
— > M=unique (v,1)
Снова отсортируем в порядке убывания, но всю матрицу в целом, а ее строки
— > Z=gsort (M,’c’)
Снова исключим одинаковые строки:
— > H=unique (Z,1)
Получим матрицу размером:
— > size (H)
Суммируем элементы строк построчно
sum (H,2)
Произведем действие над каждой полученной суммой построчно:
— > D=sum (H,2) -17
Зададим нулевую матрицу:
— > S=0
Найдем пересечение двух матриц
— > [c, iD, iS] =intersect (D (:),S (:))
iS =
1.
iD =
8.
c =
0.
Найдем строку равную iD=8
— > H (8,:)
Искомый ответ найден, но убедимся в том, что он единственный.
Найдем снова пересечение двух матриц
— > [c, iD, iS] =intersect (D (:),S (:))
Убедимся, что пересечение дает пустое множество, если нет, то повторим процедуру пересечения двух матриц, предварительно изменив значение в восьмой строке матрицы D с нулевого на другое.
— Сочетания
Пример. Частица состоит из 3-х кварков, возможны все сочетания. Кварки трех типов- зеленые, синие, красные. Найти все возможные сочетания кварков в одной частице.
