Дисциплина:
Раздел:
Выполнил:

Вариационное исчисление

Задача Коммивояжера

студент

www.domath.ru

>    restart;

>    with(linalg):#подключим пакет линейной алгебры для работы с матрицей
with(combinat):
#для работы с перестановками подключим пакет combinat с полезными комбинаторными функциями

>    #начальные данные матрицы

>    W:=matrix(6,6,[

[infinity,25,40,32,27,29],
[5,infinity,17,30,25,34 ],
[19,15,infinity,6,3, 10 ],
[9,50,26,infinity,6, 18 ],
[22,12,7,10,infinity,19 ],
[42,13,9,13,16,infinity ]

]);

матрица коммивояжера

>    S:={2,3,4,5,6}:#Этой командой зададим набор значений от 2 до 6

S := {2, 3, 4, 5, 6}

>    P:=permute(S):#Функция перестановки

>    nops(P):# команда, которая вычисл. мощность множества P,
#вычисляет число элементов данного множества

>    L:=[]:#зададим пустой набор

>    for p in P
           do
              wp:=W[1,p[1]]+W[p[1],p[2]]+
                  W[p[2],p[3]]+W[p[3],p[4]]+
                  W[p[4],p[5]]+W[p[5],   1];
              L:=[op(L),wp];
od:

>    print(L): #печать на экран множества L

>    m:=min(op(L)); #функция минимума

m := 67

>    member(m,L,'k'); #данная функция возвращает значение истина, если элемент m встречается в наборе L

true

>    k;

106

>    P[k];

[6, 3, 4, 5, 2]

>    p_min:=[1,op(P[k]),1];

p_min := [1, 6, 3, 4, 5, 2, 1]

>    answer:=[p_min,m];

answer := [[1, 6, 3, 4, 5, 2, 1], 67]