по одному разу и
по одному разу и вернуться в исходный город. При этом маршрут коммивояжера должен быть минимальной длины (стоимости).
Задача коммивояжера принадлежит классу NP-полных, то есть неизвестны полиномиальные алгоритмы ее решения. В задаче с n городами необходимо рассмотреть (n-1)! маршрутов, чтобы выбрать маршрут минимальной длины. Итак, при больших значениях n невозможно за разумное время получить результат.
Перебор вариантов. Оказывается, что и при простом переборе не обязательно просматривать все варианты. Это реализуется в данном классическом методе.
Структуры данных.
Const Max=100;
Var A:array[1..Max,1..Max] of integer;{Матрица расстояний между городами}
B:array[1..Max,1..Max] of byte;{Вспомогательный массив, элементы каждой строки матрицы сортируются в порядке возрастания, но сами элементы не переставляются, а изменяются в матрице В номера столбцов матрицы А }
Way, BestWay:array[1..Max] of byte;{Хранится текущее решение и лучшее решение}
Nnew:array[1..Max] of boolean;{Значение
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа