Delphi - сбориник статей
Методы нахождения базового маршрута
Метод 1.1 («жадный», Greedily). Сначала на графе, образованном матрицей А, отыскивается и включается в маршрут вершина (город) T[k] , которая ближе всех к начальной. Далее отыскивается самая близкая к T[k] из числа еще не включенных в маршрут и т. д. В результате получается приближенное решение задачи – базовый маршрут.
Метод 1.2 («деревянный», Woody). Сначала в маршрут включаются две вершины начальная T[0] и конечная T[N-1]. Далее отыскивается вершина, которая характеризуется наименьшим расстоянием D(T[i]+T[k]) + D(T[k]+T[j]) — D(T[i] + T[j]), где i = 0, j = N-1, k – номера еще не включенных в маршрут вершин. Найденная вершина помещается в маршрут (0, k, N-1). На следующем шаге отыскивается вершина L, которая характеризуется наименьшим расстоянием DL от звена (0, k), и вершина M, имеющая наименьшее расстояние DM от звена (k, N-1). Среди L и M выбирается та, которая имеет наименьшее из DL и DM, и включается внутрь своего звена (0, k) или (k, N-1). Пусть это вершина M с номером m. Теперь маршрут состоит из трех звеньев (0, k), (k, m), (m, N-1). Процесс продолжается до тех пор, пока есть не включенные в маршрут вершины.
Метод 1.3 (простейший, Simply). Промежуточные вершины в маршрут включаются случайным образом. В частности, базовым будет допустимый маршрут G[i] = i.
Маршруты, построенные этими методами, вычисляются с очень высокой скоростью (практически мгновенно). Однако длина этих маршрутов в подавляющем большинстве случаев далека от практически приемлемой. Для этих целей применено несколько методов улучшения базового маршрута.
