μ ( 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
Для каждого значения k будет иметь место система из ((а-2)!-1) неравенств по числу элементов множества Р, состоящего из (а-2)! перестановок чисел i΄k+1, i΄k+2, …, i΄k+a-2
При этом мы полагаем, что
μ (ik,ik+1, …, ik+a-1) = μ (ik, ik+1) + μ (ik+1ik+2 ) + … + μ (ik+a-2 ik+a-1).
μ (ik, i΄k+1, …, i΄k+a-2, ik+a-1) = μ (ik, i΄k+1) + μ (i΄k+1, i΄k+2) + … + μ (i΄k+a-2, ik+a-1).
Обозначим левую и правую части условия (4) буквами А и В, соответственно: А ≤ В.
В левой части неравенства вес каждого ребра, принадлежащего проверяемому участку гамильтонова цикла, участвует точно по одному разу в каждом неравенстве системы из ((a-2)!-1) неравенств, задаваемых перестановками, принадлежащими множеству Р, при фиксированной начальной вершине.
Кроме этого, при заданном a=const, если производить проверку выполнения условия (9.2.4), изменяя последовательно номер начальной вершины от i1 до in, то любое ребро гамильтонова цикла появится точно в (a-1) системах из этих ((a-2)!-1) неравенств как первое по счету, второе, третье и т.д. (a-1)-e ребро в проверяемых участках гамильтонова цикла.
Следовательно, левая часть неравенства (4) имеет вид:
Выражение для правой части условия (4) можно записать в виде:
Для того, чтобы получить выражение для правой части условия (4), необходимо найти число появлений ребер графа вида (ic, ic+N ) в каждой системе из ((a-1)!-1) неравенств, задаваемых определенным значением k, а также во всех системах этих неравенств, получаемых при изменении ik от i1 до in.
Очевидно, что число появлений пар (iс, ic+N) в правых частях неравенств вида (4) равно числу появлений пар (ic, ic+N) в последовательностях:
ik, i΄k+1, i΄k+2, …, i΄k+a-2, ik+a-1 (5)
задаваемых (a-2)! перестановками чисел i΄k+1, i΄k+2, …, i΄k+a-2.
Следует учесть также, что одна из этих последовательностей, а именно 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 на две.
Задавая последовательно значения 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 .
Следовательно, правая часть системы (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 вершинами.
Условие оптимальности можно использовать для «обогащения» исходного множества ветвей графа: после проверки всех ветвей графа на условие оптимальности число ветвей, которое целесообразно использовать при дальнейшем решении ЗОК, сократится. Ввиду очевидной простоты описание алгоритма не приводится.
Опыт применения этого условия для графов с n = 11–67 показал, что даже после однократного применения такой операции ко всем ветвям графа число ветвей в обогащенном массиве существенно сокращается.
● Системная философия может быть применена для формирования целостных теорий и практик осуществления специально-научного знания – культурологии, социологии, других наук.
Использовать системную философию в качестве методологической основы специально-научного знания можно следующим образом.
Для этого необходимо выделить три ступени реализации этой возможности:
– первая ступень: применение целостного метода, как философии целого, для построения целостной философии (философии целого) специально-научного знания. Могут быть построены, например, целостная социальная философия, как раздел социальной философии, целостная философия культуры, как раздел философии культуры.
На этой ступени применяются и развиваются, применительно к философии данной области знания, определения, а также постулаты и иные положения целостного метода системной технологии. Формируется код целого данной области специально-научного знания и практики;
– вторая ступень: применение метода системной философии для построения комплекса целостных теорий специально-научного знания, реализующих соответствующую целостную философию с применением моделей целостных и целых систем, Принципов, правил, Законов системной философии.
На этой ступени метод системной философии можно применить, например, для построения комплекса социологических теорий (или культурологических теорий) реализующих целостную социальную философию (либо целостную философию культуры).
Вполне возможна необходимость использования двух и более целостных философий специально-научного знания для построения какой-либо одной теории из комплекса теорий специально-научного знания. Например, целостная философия культуры и целостная социальная философия могут быть использованы при построении целостной социологии.
В свою очередь, при построении комплекса теорий, как целостного комплекса, возможно и определенное упорядочение в данном комплексе. Так, какие-либо теории могут быть выделены в качестве ключевых, другие – в качестве узловых, остальные – в качестве частных.
При этом, по определению, ключевые теории содержат модели формирования узловых и частных теорий, узловые – модели формирования частных теорий. С другой стороны, ключевые теории позволяют разрешать ключевые проблемы данной области специально-научного знания, а также содержат целостную основу для разрешения узловых и частных проблем. Узловые теории позволяют разрешать узловые проблемы данной области специально-научного знания, а также содержат целостную основу для разрешения частных проблем.
Ключевые теории представляют собой реализации кода целого в узловых и частных теориях данной области специально-научного знания и практики.
Узловые теории представляют собой реализации кода целого в частных теориях данной области специально-научного знания и практики.
На этой ступени могут применяться как узкоспециальные модели данной области знания, так и эти же модели, преобразованные с помощью моделей целостных и целых систем. Это могут быть, например, модели социальных, физических, энергетических, биологических, психологических и иных процессов, структур и систем, традиционно применяемые в данной области знания.
– третья ступень: применение метода системной технологии для построения целостных прикладных теорий специально-научного знания и целостных практик их реализации, напр., прикладных социологических теорий, направленных на построение системных технологий социального аудита, экспертизы, анализа, исследований, проектирования, управления и т.д. Или – на построение системных технологий аудита, анализа, экспертизы, исследований, проектирования, управления, мониторинга культуры и ее применения.
В результате, к примеру:
На первой ступени будет построена целостная социальная философия, рассматривающая общество, как целостное и целое. В целостном и целом обществе будут выделены и описаны ядро целого, код целого. Будет произведено формирование объектов, субъектов и результатов, как триад, направленных на разрешение проблем выживания, сохранения и развития общества, как целостного и целого. Целостная социальная философия будет также содержать определения и постулаты целостного метода социальной философии, Принципы, правила, Законы, модели целостной и целой деятельности общества.
На второй ступени будет построена, к примеру, целостная ключевая теория в комплексе социологических теорий. Основной моделью целостной и целой системы тогда может быть принята ДНИФ-модель целостной и целой системы.
На третьей ступени будут построены, напр., прикладные социологические теории, направленные на построение системных технологий социального аудита, экспертизы, анализа, исследований, проектирования, управления и т.д. Будут также разработаны методики формирования и реализации указанных системных технологий практики социальной деятельности.