Применение принципа обогащения к решению ЗОК позволяет построить эффективную технологию. В этом случае технология решения состоит из двух основных алгоритмов. Первый алгоритм позволяет обогатить исходный массив данных, исключая из него те «расстояния», которые не могут участвовать в оптимальном маршруте. Второй алгоритм позволяет найти оптимальный (или близкий к оптимальному) маршрут коммивояжера.

Задача поставлена и решена, как известная задача теории графов о нахождении оптимального гамильтонова цикла в графе [42] .

Для оптимального гамильтонова цикла справедливо следующее условие оптимальности: для любого простого маршрута, являющегося участком оптимального гамильтонова цикла и проходящего вершины графа в последовательности i1, i2, i3, ...,ia, (a=4,5, ...,n; il=1,2, ..., n) сумма весов входящих в него ребер ? (i1i2i3 ..., ia ) является минимальной в сравнении с любой другой суммой вида ? (i1i?2i?3...i?a-1ia):

? ( i1i2i3...ia) = min ? (i1i?2i?3...i?a-1ia ) (1)

при a =4, 5, ..., n; i=1,2, ..., n; i?2, i?3,..., i?a-1, ?P.

Здесь i?2, i?3,..., i?a-1 — одна из перестановок чисел i2, i3, ..., ia-1, P — множество всех перестановок этих чисел.

Очевидно, что если это условие не выполняется для каких-либо значений a и i, то существует гамильтонов цикл с меньшей длиной пути обхода вершин i1, i2, i3, ..., ia-1,ia . Но, если полученный гамильтонов цикл оптимален, то его нельзя улучшить изменением пути обхода вершин i1, i2, i3, ..., ia для любого a, имеющего значения в пределах от 4-х до n.

Значения a не могут быть меньше четырех, так как очевидно, что никакие два гамильтонова цикла не могут отличаться менее, чем тремя ребрами, проходящими четыре вершины поcледовательно в одном из двух возможных вариантов обхода: i1,i2,i3,i4 или i1,i3,i2,i4 .

Пусть оптимальный гамильтонов цикл обходит вершины графа в последовательности

i1, i2, i3, ..., in, i1. (1.а)

Гамильтонов цикл, оптимальный для определенного значения a, назовем a-оптимальным. Для a = 4 справедливо неравенство:

? (ikik+1) + ? (ik+1ik+2) + ? (ik+2ik+3) ?

? ? (ikik+2) + ? (ik+2ik+1) + ? (ik+1ik+3).

Условие (2) необходимо проверить для всех ik = i1, i2, ..., in и, если оно для всех ik справедливо, то это необходимое и достаточное условие того, что гамильтонов цикл 4-оптимален. Просуммировав левые и правые части неравенств, получающихся при значениях ik = i1, i2, ..., in, получаем необходимое условие 4-оптимальности в виде:

Если гамильтонов цикл a1-оптимален, то он a2– оптимален для любого a2<a1.

Если это условие не выполняется, т.е. a1-оптимальный гамильтонов цикл не является a2– оптимальным, то какой-то из простых путей длины a1 можно улучшить изменением обхода каких-то a2 вершин, что противоречит условия a1– оптимальности.

Перейдем к определению условия a– оптимальности, получаемого аналогично тому, как условие (З) получено из (2), из системы неравенств вида (2), для любого a=const суммированием для всех ik=1, 2, ..., n