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

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

Текст предоставлен ООО «ЛитРес».

Прочитайте эту книгу целиком, купив полную легальную версию на ЛитРес.

Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.