Приближенные методы

В настоящее время для решения задачи коммивояжера существует более 100 приближенных методов среди которых наиболее прост метод ближайшего соседа.

Метод ближайшего соседа реализует требование включить в искомый замкнутый контур вершину ближайшую к только что найденной.Алгоритм состоит в последовательном добавлении к начальной вершине следующей ближайшей к ней и т.д.

Поскольку степень приближения к оптимальному решению существенно зависит от выбора начальной вершины , то алгоритм повторяют начиная с каждой из вершин, а затем выбирают контур минимальной длины.

При этом следует отметить, что если ближайший сосед для некоторой вершины уже вошел в контур, то берется следующая по близости вершина.

Для решения задач о назначении хорошее приближение дает метод аппроксимации Фогеля. При использовании этого метода в каждом ряду (строке или столбце) отыскиваем минимальный и ближайший к нему элемент и их разность записываем справа и внизу исходной таблицы.

Из этих разностей отыскиваем максимальную и в соответствующем ей ряду находим минимальный элемент. Производим назначение, затем из матрицы вычеркиваем строку и столбец с произведенным назначением и с оставшейся матрицей производим аналогичные операции до тех пор пока не будут произведены все назначения.

В том случае если известны решения задачи и полученное одним из точных методов можно оценить погрешность решения. При этом различают абсолютную погрешность

Δ =Fпр-Fточн , где Fпр и Fточн – значение целевой функции полученное приближенным и точным методом соответственно.

Относительная погрешность:

δ = Δ/ Fточн = (Fпр-Fточн)/ Fточн ;которая может быть так же выражена в %

δ%= δ*100%