Целостный метод системной технологии и системная экология

Телемтаев Марат Махметович

Следует учесть также, что одна из этих последовательностей, а именно i1, i2, i3, ..., ik+a-1 находится в левой части этих неравенств.

Пары icic+N можно разделить на следующие виды по признаку, содержат они или нет «неподвижные» вершины ik и ik+a-1:

а) icic+N при c ? k; c + n < k+a-1; n >1, n ? a-2; это пары элементов в (5), не содержащие элементов ik, ik+a-1 и тех элементов (i1, i2, i?2, i3, i?3, i4 и т.д.), которые входят в гамильтонов цикл (1a).

Каждая из пар этого вида появится в системе неравенств (4) для определенного значения ik=i1,i2, ..., in, точно (a-3)(a-4)!

раз – по числу (a-4)! перестановок (a-4) элементов, т.е. элементов последовательности (5) за вычетом элементов ik, ik+a-1, ic, ic+N для каждого из (a-3) возможных положений пары ic, ic+N в последовательности (5).

б) ic, ic+N при n>1, c=k и ic+Nic+a-1 при n < а-2, c=k это пары элементов в (5), содержащие элементы ik или ik+a-1 и элементы гамильтонова цикла (1a).

Каждая из этих пар появится в системе неравенств (4) для определенного значения ik=i1,i2, ..., in, точно (a-3)! раз по числу возможных перестановок (a-3) элементов, т.к. элементы ik, ik+N, ik+a-1 для этих пар «неподвижны».

Кроме этого, в совокупностях пар обоих видов надо выделить пары ic, ic+1, т.е. пары элементов гамильтонова цикла (1а). Тогда можно считать, что каждая из этих пар появится в системе неравенств (4) для определенного значения ik=i1,i2, ..., in точно ((a-3)!-1) раз по числу появлений пар вида а) или б) и за вычетом появлений одной пары, находящейся в левой части неравенства (4).

Аналогично и для любой пары вида iс+N iс число появлений в системе неравенств (4) для определенного значения ik равно (a-3)!. Здесь надо учесть то обстоятельство, что ik и ik+a-1 «неподвижны», т.е. они не могут участвовать в парах вида iс+N iс .

Таким образом, каждая пара элементов вида iсiс+N, не образующая ребро, инцидентное гамильтонову циклу, а также каждая пара вида iс+N iс появятся в правой части системы неравенств, записанных для определенного значения ik, точно (a-3)! раз, а ребра, инцидентные гaмильтонову циклу, точно ((a-3)!-1) раз.

Задавая последовательно значения ik от i1 до in, мы получаем каждый раз новые системы неравенств. При этом относительно любого ребра ic, ic+N участок ik, ik+1, ..., ik+a-1 «передвигается», вследствие чего любые пары ic+N ic или ic, ic+N участвуют в a-N(k+a-1-n-k+1=a-N) системах неравенств (4). То обстоятельство, что пары вида (ic+N, ic) с участием элементов ik и ik+a-1 в каждой системе неравенств невозможны, приводит к уменьшению числа появлений каждого такого вида пар ic+N ic в системе (4) для данного N на две.

Ребра ic ic+1 участвуют, таким образом, в (a-1) системах неравенств, если, конечно, (a-3)!-1 ? [1] или a ? 5, т.е., если они по условию вообще появляются в правой части системы неравенств для любого ik.

Отсюда очевидно, что любое ребро ? (ikik+N ), N ? 1, графа будет повторяться в правых частях n систем неравенств (4) (a – N)

раз для ik= i1, i2, ..., in .

1

Прутков Козьма. Сочинения. М., «Худож. лит». 1976, 381 с.

Следовательно, правая часть системы (4) примет вид:

Итак, условие a– оптимальности примет вид:

для a ? 5.

После простых преобразований получаем

для a ? 5.

Отсюда получаем условие n-оптимальности (a=n)

И, далее, условие (n +1)-оптимальности (a=n+1), т.е. условие оптимальности собственно гамильтонова цикла, принимает вид

Можно усилить условие (7), введя вместо проверки суммарного неравенства проверку по всем k. Получим условия а– оптимальности гaмильтонова цикла в виде:

a ? 5; k = 1, 2, ..., n.

Выше было показано, что a1– оптимальный гамильтонов цикл a2– оптимален, если a1 > a2.

Поэтому условие оптимальности гамильтонова цикла можно преобразовать к виду (a = n + 1):

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

Таким образом, весь процесс решения задачи делится на 2 стадии: первая – «обогащение» исходного числового массива, вторая – применение алгоритма поиска на «обогащенном» массиве.

Реализация первой стадии при решении ЗОК производится с применением полученного условия оптимальности гамильтонова цикла в графе G с n вершинами.

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