а) 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.
Следовательно, правая часть системы (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 показал, что даже после однократного применения такой операции ко всем ветвям графа число ветвей в обогащенном массиве существенно сокращается.
• Для эффективного формирования целостности и системности собственного мышления и практики профессиональной деятельности рекомендуется провести работу по следующим темам (консультации на сайте systemtechnology.ru):
1) разработка комплекса формул Законов индустриализации, машинизации, технологизации прикладных математических методов и методик их применения;
2) разработка комплекса условий Принципа целостности прикладного математического метода (по выбору);
3) разработка комплекса правил Закона целостности прикладного математического метода (по выбору);
4) разработка комплекса правил Закона развития целого для прикладного математического метода (по выбору);
5) разработка комплекса условий Принципов развития целого для прикладного математического метода (по выбору).
• Положения системной философии могут быть применены и для решения задач образования[93] .
Так, системная триада образовательной системы странового формата включает в себя следующие системы:
а) система-субъект – совокупность государственных и неправительственных структур управления образованием. Эта система ответственна перед внешней средой (в том числе, перед страной) в целом за формирование концепции целостной образованности человека и общества, необходимой для целей выживания и развития страны. В функции этой системы входит также и управление реализацией концепции целостного образования;
6) система-объект – совокупность учреждений и заведений образования. Эта система ответственна перед системой-субъектом и страной за реализацию концепции целостной образованности человека и общества, необходимой для выживания и развития страны;
в) система-результат – предполагаемое приращение интеллектуального потенциала страны, необходимое для целей выживания и развития страны, за счет целостной образованности человека и общества, а также предполагаемая система управления сохранением, использованием и развитием целостной образованности человека и общества в обозримом будущем.
• Примем следующие определения:
продуктом воспитания является воспитанность человека и общества, продуктом образования – образованность человека и общества, продуктом просвещения – просвещенность человека и общества;