Chapter 1. The essence of the method; commands and typical algorithms in the program Scilab 6.0.1
— The essence of the method
Any set can be written as a matrix with elements of this set. The essence of the method used consists of operating on natural numbers (elements of sets), applying a matrix approach, that is, operating on elements of matrices, their columns and rows, as well as in the interactions between matrices (sets).
Common algorithms for combinatorics problems, such as permutation, combination, placement problems, which are given below, are applicable for NP — problems. These types of problems (on permutations, combinations, placements) with large numbers can be attributed to NP — problems. NP-problems, in essence, represent all the same problems of combinatorics, but in a complicated version, in one problem can be present immediately as permutations and combinations and placement, these operations (combinations, placement, permutations) can be repeated sequentially, but with other data obtained in the course of solving the problem, additional conditions or calculations can be set. But with the help of Scilab program typical algorithms of such problems are revealed and solutions are given, not only the number of solutions. The bottom line is that knowing the typical algorithms of permutations, placement, combinations, they can be used as many as standard algorithms in one problem and thus solve NP — problems.
— NP-problems and their models in small numbers, General algorithms
Here are examples of NP-problems:
Task №1.
Suppose that you are organizing a group of four hundred University students. The number of places is limited, and only one hundred students will get a place in the hostel. The situation is complicated by the fact that the Dean has provided you with a list of pairs of students who can’t live together, and asked that no pair from this list did not get to the final version.
Task №2.
Is it true that among the numbers {-2, -3, 15, 14, 7, -10, …} are there any such that their sum is 0?
Or else, for example: 50, 2, 47, 5, 21, 4, 78, 1. Problem: is it possible to choose among these numbers such that their sum will give 100?
Task №3.
You want to find the shortest path that passes exactly one time through each of the six cities A, B.C. D. I. F. You are given a matrix of distances between all pairs of cities,
Tasks like the above 3 examples seem unsolvable (so far no one has been able to prove that some of them are actually as complex as it seems, i.e. that there is really no way to get an answer using a computer).
We make models of these problems in small numbers to find an algorithm and solve these problems:
Task-model №1
Let’s say you’re hosting a group of 5 University students. The number of places is limited, and only 3 students will get a place in the hostel. The situation is complicated by the fact that the Dean provided you with a list of students who can’t live together, and asked that none of this list was not in the final version.
Problem-model №1—1
Let’s say you’re hosting a group of 9 University students. The number of places is limited to 4 — 2 rooms for 2 people, and only 4 students will get a place in the hostel.
Find these solutions.
Task-model №3.
You want to find the shortest path that passes exactly once through each of the four cities A, B. C. D.. You are given a matrix of distances between all pairs of cities,
Solutions of NP-problems and their model problems are similar and have the same algorithms, solutions of model problems are given below.
— Specify the source data
The initial data in the commands are given by a vector (a single matrix), but it is also possible by a two-dimensional matrix, several matrices, etc. each object is assigned a serial number. For example, we have 5 students:
Let’s give each student a number in order: 1. – first student; 2. – 2nd student....etc to 5. As a one-dimensional matrix n
Program start:
loading the source environment
— > n= [1 2 3 4 5]
n =
1. 2. 3. 4. 5.
— Permutations
The permutation is performed using the perms (n) command:
Now we find all possible permutations from 1 to 5, there will be 120. The answer will be written in the form of a matrix, where each row is a variant of one of the permutations, the number of rows in the matrix will be equal to the number of permutations, and the number of columns will be equal to the originally specified elements (in our case 5).
— > P=perms (n)
— Permutations followed by matrix replacement and finding solutions
As an example with a complex permutation (replacement of the matrix obtained as a permutation to another matrix), the problem-model №3:
You want to find the shortest path that passes exactly once through each of the four cities A, B. C. D. You are given a matrix of distances between all pairs of cities,
Decision.
The essence of the solution is that finding all the permutations between the four cities in the form of rows of the matrix, replace the rows of the resulting matrix with the rows of another matrix, the elements of which are the distances between the cities and calculate the paths, then find the smallest.
Set the initial conditions: cities A, B,C, D are numbered in order and assign each city number 1,2,3,4, respectively. Let’s set the distance between cities by matrices, for example. distance between town A and B as a matrix ab whose elements is a pair of 1 and 2 (this is the number of cities A and B):
— > 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.
We find all possible permutations and obtain the matrix P.
— -> P=perms (M);
The result is a matrix of 4 columns (cities) and rows-variants of permutations.
If in the condition of the problem it was necessary to return back to the initial point, then to the matrix obtained as a result of permutations it would be necessary to add another one column where the element in each row would be the element of the first row of the matrix P.
The program does not provide a command to replace the original matrix, therows of which are the paths indicated by a sequential enumeration of cities, with a matrix of distances between these cities (for example, such a command could be called command “between”. The value of command “between” the elements with values 1 and 2 is 10, for example, as the initial data between ([1 2]) =10; insert values between the elements of the matrix rows P as between (P:,1)). So we’ll have to go the other way. Divide the resulting matrix P into 3 parts, and then connect again, as between 4 cities can build a path of three distances between cities. These 3 matrices will consist: the 1st of the first two columns, the 2nd of the second and third columns, the 3rd of the third and fourth columns.
— > 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);
Let’s create a matrix U, such that we replace the values of the elements of the matrix T (that is, the numbers of cities) by the distances between them from the problem condition. For example, in the line items written as [1 2 2 3 4] will be written as [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];
The distances between cities are known to us by the problem condition, let us set them and write down the matrix again:
— > 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];
Let’s sum up the rows of the obtained matrix and find the smallest element:
— > Y=sum (U,2);
— > min (Y)
ans =
12.
The smallest distance is 12. Create matrix H and find the intersection of matrixes to find the string and define the path.
— > H= [12];
— > [c, iY, iH] =intersect (Y (:),H (:))
iH =
1.
iY =
5.
c =
12.
We see that the intersection of matrixes with the value of element 12 points to row 5 in matrix Y. Row 5 in matrix T points the way:
T (5,:)
ans =
4. 1. 1. 3. 3. 2.
The first answer is the shortest path 12 km path from city 4 to city 1, then from city 1 to city 3, from city 3 to city 2.
But, this answer may not be the only one, so let’s set the element of the 5th row of the obtained matrix Y to a value greater than the minimum distance of 12 km., for example 12+1=13 and repeat the matrix crossing procedure
— > Y (5,1) =13;
— > [c, iY, iH] =intersect (Y (:),H (:));
Repeat this process and record the answers on the basis of the row of the crossing until the crossing of matrices will not give the empty set.
— Placements
The number of places is limited, and only 3 (three) students out of 5 will get a place in the hostel. Find all accommodation options.
To find solutions, remove the last columns in the matrix obtained by permutations (5—3=2). Remove the two columns to leave three columns, as only 3 people can get a place.
— > P (:, 5) = []
— > P (:, 4) = []
We exclude the same rows in the matrix P:
— > M=unique (P, 1)
Let’s sort the rows of the resulting matrix M in descending order:
— > V=sort (M,‘c’)
Again, delete the same rows of the sorted matrix V:
— > Y=unique (V, 1)
Get the desired answer, each row of the matrix will be as a placement option.
The number of such placements will be equal to the number of lines:
— > size (Y)
And the number of columns is the number of places that students had to be placed.
— Fulfillment of additional conditions in the task
But the Dean set a condition that the 3rd, 1st, and 5th students do not settle together. Let’s set this condition as a one-dimensional matrix Z:
— > Z= [3 1 5]
Z =
3. 1. 5.
Let’s sort the matrix Z in descending order:
— > R=gsort (Z)
Find the intersection of rows of matrixes R and Y:
T=intersect (R,Y,1)
Finding the common row index for R and Y matrixes
— > [c, iR, iY] =intersect (R,Y,1)
iY =
6.
iR =
1.
c =
5. 3. 1.
Thus, it is necessary to delete the 6th row of the matrix Y in order to fulfill the Dean’s condition and get the final answers in the form of matrix rows:
— > Y (6,:) = []
Let’s once again we find the intersection of the rows of matrices R and Y, and so we repeat until the intersection of matrices is empty set.
We get the final answers to the task — these are the rows of the matrix Y as all possible answers.
— Complex placements
Task-model №1—1
Another example of accommodation: 9 students can be accommodated only in 2 rooms in pairs, that is only 4 places. Find all these pairs-solutions.
To save space, suppose that we have already found a solution to place 9 students in 4 places in the form of rows of the matrix (assume matrix E) similar to the Task-model №1 (get a matrix of 4 columns-the number of seats, and rows — equal to the number of solutions). Now, of all the options presented in each of therow of the resulting matrix E it is necessary to choose all kinds of options pairs. To do this, each row of the resulting matrix e is represented as an initial condition — a one-dimensional matrix, of the four numbers of one-dimensional matrices it is necessary to obtain all possible variants of pairs. Each option will be presented in pairs that are received in rows of the final matrix.
The variant of obtaining all possible pairs from one one-dimensional p matrix is presented below, but the finding of all possible pairs from other one-dimensional matrices is similar.
Decision:
Program start:
loading the source environment
— > n= [5 3 1 4]
n =
5. 3. 1. 4.
Find all possible permutations of the matrix row P
— > P=perms (n)
Since there are 2 rooms under the conditions of the problem, divide the matrix P into 2 matrices with an equal number of columns: that is, one matrix with the first two columns, the other with the 3rd and 4th columns, and sort the rows of the obtained two matrices in descending order.
— > F=P
— > F (:,4) = []
— > F (:,3) = []
— > V=gsort (F,‘c’)
— > K=P
— > K (:,1) = []
— > K (:,1) = []
— > Q=gsort (K,‘c’)
After sorting the two matrices, combine them and delete the same rows in the resulting matrix
— > W=cat (2,V,Q)
Exclude the same rows and find the answer you are looking for
— > U=unique (W,1)
Answer: variants of pairs in each row of the matrix, that is, the first option-the first row — is the 1st room of two students in the 1st and 2nd column, ie, under the numbers 3,1; 2nd room of two students in the 3rd and 4th column, ie, under the numbers 5,4. The second option is the 2nd row — this is the 1st room of two students in the 1st and 2nd column, i.e. under the numbers 4.1; 2nd room of two students in the 3rd and 4th column, i.e. under the numbers 5.3, etc. and so all the rows of the resulting matrix U. But as we wrote at the beginning of solving the task — model №1—1, this is only the answer obtained from one of the rows of the matrix E. All the same should be done with all the rows of the matrix E.
— Solving the problems of combinations and arrangements with the help of zeros in the rows of the original matrix
Numbers 2, 9.6. Problem: is it possible to choose among these numbers such that their sum will give 17?
Since we need to pick up all sorts of combinations and find their sum, we will set a one-dimensional matrix with an equal number of zeros and how many of the original numbers:
loading the source environment
загрузка исходного окружения
Solving the problems of combinations and arrangements with the help of zeros in the rows of the original matrix.
Numbers 2, 9.6. Problem: is it possible to choose among these numbers such that their sum will give 17?
Since we need to pick up all sorts of combinations and find their sum, we will set a one-dimensional matrix with an equal number of zeros and how many of the original numbers:
loading the source environment
— > n= [0 0 0 2 9 6]
n =
0. 0. 0. 2. 9. 6.
Let’s sort the initial matrix for convenience of calculations in descending order.
— > m=gsort (n)
m =
9. 6. 2. 0. 0. 0.
Find all variants of the permutations
— > v=perms (m)
Remove the last columns-3 columns, so the number of additional zeros in the original matrix was 3.
— > v (:,6) = []
— > v (:,5) = []
— > v (:,4) = []
Sort the resulting matrix in descending order:
— > x=gsort (v)
Exclude the same lines:
— > M=unique (v,1)
Again, sort in descending order, but not the entire matrix as a whole, and its rows
— > Z=gsort (M,‘c’)
Again, exclude the same rows:
— > H=unique (Z,1)
Get the matrix of size:
— > size (H)
Sum the elements row by row
sum (H,2)
We perform an action on each received sum line by row:
— > D=sum (H,2) -17
Set the zero matrix:
— > S=0
Find the intersection of two matrices
— > [c, iD, iS] =intersect (D (:),S (:))
iS =
1.
iD =
8.
c =
0.
Find a string equal to iD=8
— > H (8,:)
The answer looking for is found, but make sure it’s the only one.
Find again the intersection of two matrices
— > [c, iD, iS] =intersect (D (:),S (:))
Make sure that the intersection gives an empty set, if not, then repeat the procedure of crossing two matrices, previously changing the value in the eighth row of t
