NP=P? Algorithms for solving NP-problems by matrix method in Scilab program

– > 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) = [];