NP=P? Алгоритмы решения NP-задач матричным методом в программе Scilab. Математическое эссе

Зададим начальные условия: города 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;