Содержание к диссертации
Введение
1 О труднорешаемых задачах о назначениях 32
1.1 Планарная m-слойная 3-индексная задача о назначениях на одноциклических подстановках 32
1.1.1 Постановка задачи 32
1.1.2 Алгоритм приближённого решения задачи 33
1.1.3 Общий вероятностный анализ алгоритма 36
1.1.4 Случай равномерного распределения 39
1.2 Задача о назначениях с ограничениями на циклы в подстановке 45
1.2.1 Постановка задачи 45
1.2.2 Описание TSP-подхода 46
1.2.3 Результаты применения TSP-подхода 47
1.3 О разрешимости аксиальной 8-индексной задачи о назначениях на одноциклических подстановках 53
1.3.1 Постановка задачи 53
1.3.2 Предварительные замечания 55
1.3.3 Разрешимость задачи 8-АЗНО 59
2 2 Задача нескольких коммивояжеров с различными весовыми функциями маршрутов 73
2.1 Постановка задачи 73
2.2 Приближённый алгоритм решения задачи 74
2.3 Вероятностный анализ алгоритма
2.3.1 Входные данные с усеченным нормальным распределением 77
2.3.2 Входные данные с показательным распределением 80
3 Задача нескольких коммивояжеров с одинаковыми весовыми функциями маршрутов 85
3.1 Постановка задачи 86
3.2 Подход к приближённому решению задачи
3.2.1 Об алгоритмах нахождения гамильтонова цикла в случайном графе 88
3.2.2 Алгоритм Гимади-Перепелицы 1973 89
3.2.3 Алгоритм Angluin-Valiant 1979 92
3.3 Вероятностный анализ подхода 94
3.3.1 Непрерывное распределение входных данных 94
3.3.2 Дискретное распределение входных данных 100
Заключение 103
Публикации автора по теме диссертации 105
Благодарности 109
Литература
- Случай равномерного распределения
- О разрешимости аксиальной 8-индексной задачи о назначениях на одноциклических подстановках
- Входные данные с усеченным нормальным распределением
- Об алгоритмах нахождения гамильтонова цикла в случайном графе
Введение к работе
Актуальность темы. Предметом исследования диссертации являются труднорешаемые задачи маршрутизации, к которым приводят обобщения и вариации двух фундаментальных задач комбинаторной оптимизации - задачи коммивояжера (Traveling Salesman Problem, TSP) и задачи о назначениях. В работе исследуются: планарная m-слойная 3-индексная задача о назначениях на одноциклических подстановках (m-3-ПЗНО), задача нескольких коммивояжеров (m-Peripatetic Salesman Problem, m-PSP) в постановках с различными и с одинаковыми весовыми функциями маршрутов; многоиндексная аксиальная задача о назначениях на одноциклических подстановках; задача о покрытии графа m циклами (m Cycles Cover Problem, mССР).
Многоиндексная задача о назначениях, для которой различают пла-нарную и аксиальную постановки, является естественным обобщением классической задачи о назначениях. Она имеет широкий круг практических приложений. Аксиальные задачи о назначениях возникают при разработке алгоритмов для современных систем компьютерного зрения [16, 13], в задачах классификации и конъюгации человеческих хромосом [8], оптимизации размещения элементов на 3D интегральных схемах [19]. Планарные задачи о назначениях тесно связаны с латинскими квадратами в том смысле, что любое допустимое решение 3-индексной планарной задачи о назначениях может быть представлено как латинский квадрат. В свою очередь, латинские квадраты находят применение в комбинаторике, при изучении квазигрупп в алгебре, в теории кодов, статистике и криптографии. Планарные задачи о назначениях часто возникают в теории расписаний [9, 18], в задачах бесконфликтной работы с данными при множественном доступе и при построении кодов, исправляющих ошибки [9].
Многоиндексные задачи о назначениях с требованиями одноциклич-ности одной или нескольких подстановок являются источником постановок различных транспортных задач, которые можно рассматривать как синтез или обобщение задачи коммивояжера и задачи о назначениях. К одному из таких обобщений относится m-слойная 3-индексная планарная задача о назначениях на одноциклических подстановках или, другими словами, задача об m коммивояжерах (m-PSP) с различными весовыми функциями маршрутов.
Приложения задачи m-PSP естественным образом возникают при оптимизации маршрутов доставки товаров к местам реализации; составлении маршрутов патрулирования, кольцевых маршрутов для автоматически управляемых транспортных средств на производстве, а также при транспортировке потенциально опасных веществ [11]. De Kort в [10] упо-
минает о применении задачи m-PSP при дизайне сетей, где несколько рёберно-непересекающихся циклов передачи данных защищают сеть от сбоев, и о возникновении 2-PSP в ряде задач теории расписаний.
Все приведённые здесь обобщения задачи о назначениях и коммивояжера NP-трудны. Это означает, что, в предположении Р = NP, для них не существует одновременно точных и быстрых (полиномиальных) алгоритмов. Существующие точные алгоритмы для этих задач представляют собой различные интеллектуальные модификации алгоритма полного перебора, имеют экспоненциальное время работы и неприменимы для решения задач большой размерности. В связи с этим актуально построение полиномиальных приближённых алгоритмов для этих задач с гарантированными оценками качества.
Целью диссертации является построение новых комбинаторных приближённых полиномиальных алгоритмов и методов получения таких алгоритмов для решения рассматриваемых задач, а также обоснование оценок качества полученных алгоритмов (трудоемкости, относительной погрешности, вероятности несрабатывания, асимптотической точности) для широких классов входных данных.
Основные результаты диссертации.
Для планарной m-слойной трёх индексной задачи о назначениях на одноциклических подстановках на минимум и на максимум предложен полиномиальный приближённый алгоритм решения. Установлены оценки относительной погрешности, вероятности несрабатывания, а также условия асимптотической точности алгоритма для случаев, когда элементы матрицы стоимости являются независимыми случайными величинами, равномерно распределёнными на отрезке [ап,Ъп], 0 < ап < Ъп.
Получены новые полиномиальные приближённые алгоритмы и обоснованы гарантированные оценки их точности для симметрической и метрической задачи о покрытии графа т вершинно-непересекающимися циклами (т-ССР) на максимум, а также для задач т-ССР на максимум и на минимум с весами ребер 1 и 2.
Доказана разрешимость 8-индексной аксиальной задачи о назначениях на одноциклических подстановках при нечётных п > 85.
Для задачи о нескольких коммивояжерах с различными весовыми функциями их маршрутов на минимум предложен полиномиальный приближённый алгоритм решения и установлены достаточные условия асимптотической точности алгоритма для случаев, когда веса рёбер графа являются независимыми одинаково распределёнными
случайными величинами, принимающими значения из неограниченной сверху области [ап, оо), 0 < ап.
Перенести оценки качества упомянутого в предыдущем пункте алгоритма на случай решения задачи нескольких коммивояжеров с одинаковыми весовыми функциями не оказалось возможным. Поэтому для этой задачи разработан новый подход, дающий полиномиальные приближённые алгоритмы решения. Проанализировано два алгоритма, полученных с помощью этого подхода, найдены условия их асимптотической точности для входных данных задачи, имеющих непрерывное или дискретное распределение на отрезке [ап, Ъп\, О < ап < Ьп, и на полуинтервале [ап, оо), 0 < ап.
Научная новизна и значимость работы. Все результаты, представленные в диссертации, являются новыми и носят теоретический характер. Поскольку рассмотренные в диссертации задачи NP-трудны, известные для них точные алгоритмы справляются с решением задач весьма малой размерности. Напротив, предложенные в работе полиномиальные асимптотически точные алгоритмы способны решать задачи большой размерности за разумное время, а точность этих решений увеличивается с ростом размерности. Разработанные приближённые алгоритмы и подходы могут использоваться для получения новых теоретических результатов в данной области и решения соответствующих практических задач.
Методы исследований. В работе использовались методы алгебраического и комбинаторного анализа, методы дискретной оптимизации и исследования операций, методы вероятностного анализа приближённых алгоритмов и теории вероятности, а также элементы теории графов.
На защиту выносится совокупность результатов по исследованию эффективной разрешимости и построению новых полиномиальных алгоритмов с гарантированными оценками качества для различных модификаций задач маршрутизации и назначений, имеющих многочисленные практические и теоретические приложения.
Апробация работы. Основные результаты диссертации докладывались на следующих российских и международных конференциях и семинарах: V Всероссийская конференция "Проблемы оптимизации и экономические приложения" (Омск, 2012), Международный симпозиум по комбинаторной оптимизации СО-2012 (Великобритания, Оксфорд, 2012), 26 и 28 Европейские конференции по комбинаторной оптимизации ЕССО (Франция, Париж, 2013; Италия, Катания, 2015), Международные конференции по дискретной оптимизации и исследованию операций DOOR (Новосибирск, 2013; Владивосток 2016), Международная конференция "Интеллектуализация обработки информации" (Греция, о. Крит, 2014), Всероссийской конференции "Математическое программирование
и приложения" (Екатерибург, 2015), 17-ой Всероссийской конференции "Математические методы распознавания образов" (Светлогорск, 2015), V, VI и VII международные конференции "Optimization and Applications" OPTIMA (Петровац, Черногория, 2014, 2015, 2016), II Международная конференция и летняя школа "Numerical Computations: Theory and Algorithms" NUMTA-2016 (Калабрия, Италия 2016), а также на научных семинарах Института математики им. С.Л. Соболева.
Публикации. По теме диссертации автором опубликовано 17 работ, из них 5 статей в научных журналах из списка ВАК (3 в базе РИНЦ с переводами в Scopus или Web of Science, 2 в базе Web of Science), одна в рецензируемых трудах конференций (в базе Web of Science) и 11 тезисов докладов конференций. Постановки задач предложены научным руководителем. Вклад в развитие идей построения алгоритмов неразделим с соавторами. Доказательства гарантированных оценок качества алгоритмов проведены лично соискателем. Конфликт интересов с соавторами отсутствует.
Структура и объём работы. Диссертация изложена на 122 страницах, содержит введение, обзор литературы, три главы, заключение, список публикаций автора по теме диссертации, благодарности и список литературы, содержащий 111 наименований.
Случай равномерного распределения
Поскольку множество допустимых решений в задачах дискретной оптимизации конечно, их решение допускает перебор всех допустимых решений и выбор наилучшего. Однако, в реальных задачах, моделируемых в этой научной области, количество допустимых решений, как правило, так велико, что их перебор невозможно осуществить за приемлемое время даже с помощью самой мощной вычислительной техники. Поэтому основным направлением в дискретной оптимизации является разработка алгоритмов, которые, в отличие от алгоритма полного перебора, находят оптимум за разумное время. Но это не всегда возможно.
Введем основные определения. Для оптимизационной постановки задачи под индивидуальной задачей оптимизации I понимается пара (F/, с/), где Fj - область допустимых точек, a cj : Fj — К. функция стоимости. Требуется найти точку у Є F/, для которой в задаче на минимум ci(y ) ci(y) (или ci(y ) ci(y) в задаче на максимум) для всех у Є Fj. Массовая задача оптимизации Z — это множество индивидуальных задач оптимизации, т.е. набор индивидуальных задач, обычно порождаемых одинаковым способом.
Основной интерес как практический, так и теоретический, представляет исследование и решение массовых задач дискретной оптимизации. Построение решения задачи осуществляется с помощью алгоритма. Среди критериев оценки алгоритмов выделяют степень точности получаемых решений и время работы алгоритма. Относительно времени работы эффективными принято считать полиномиальные алгоритмы, которым для решения произвольной индивидуальной задачи І Є Z необходимо выполнить Т(п) элементарных операций, где п длина записи входных данных задачи /, а Т{п) = 0(р(п)) для некоторого полинома р(п). Алгоритмы, временная сложность которых не поддаётся такой оценке называют "экспоненциальными".
Пессимизм исследователей, вызванный неудачными попытками построить непереборные эффективные алгоритмы для ряда задач дискретной оптимизации и понятием "проклятие размерности", в 70-е годы благодаря работам Кука [53], Карпа [86] и Левина [25], а также книге Гэри и Джонсона [20] сменился на более определённое теоретическое понимание вопроса о сложности решения задач комбинаторной оптимизации. Это понимание связано с такими определяющими понятиями как NP-полная и NP-трудная задача, для которых эффективных алгоритмов скорее всего не существует (если Р т NP).
В теории вычислительной сложности рассматривают задачи распознавания свойств (decision problem), которые имеют только два возможных решения "да" или "нет". Класс задач распознавания свойств, которые могут быть решены точно некоторым полиномиальным алгоритмом, называется классом P. Класс NP состоит из задач распознавания свойств, для которых полиномиальное по длине записи удостоверение о решении проверяемо за полиномиальное время. Очевидно, Р С NP. Вопрос о возможном равенстве этих двух классов известен как "проблема Р versus NP". Большинство теоретиков в этой области склоняются к тому, что Р т NP, хотя формально вопрос остаётся открытым.
В классе NP выделяют подкласс наиболее трудных, так называемых NP-полных задач, к которым за полиномиальное время сводится любая другая задача из класса NP. Если бы нашёлся полиномиальный алгоритм для какой-либо NP-полной задачи, стало бы возможно полиномиально решить все остальные, что, в свою очередь, означало бы равенство классов Р и NP. Задачи (не обязательно из класса NP), к которым полиномиально сводится хотя бы одна NP-полная задача, называются NP-трудными. Большинство интересных и естественных задач дискретной оптимизации NP-трудны. В книге Гэри и Джонсона [20] собраны более 300 труднорешаемых задач из различных разделов математики. Существуют разные подходы к решению NP-трудных задач. К точным методам решения относятся варианты интеллектуального перебора допустимых решений, такие как метод ветвей и границ, метод ветвей и сечений (brunch-and-cut), метод динамического программирования, локальный поиск и другие. Кроме того, существуют разнообразные приближённые эвристические алгоритмы (генетические, поиск с запретами, нейронные сети и др.), для которых степень точности получаемых решений подтверждается численным экспериментом. В данной работе нас будут интересовать полиномиальные приближённые алгоритмы с аналитически доказуемыми оценками точности.
О разрешимости аксиальной 8-индексной задачи о назначениях на одноциклических подстановках
Для решения задачи при числе коммивояжёров т п/4 предлагается алгоритм А аналогичный алгоритму из главы 1.3. Алгоритм А состоит этапов г = 1,..., т; т п/4. На г-ом этапе строится г-ый гамильтонов цикл Ни к этому моменту все ребра, принадлежащие предыдущим циклам Н\,..., i7j_i, удалены из графа и таким образом запрещены для использования на данном этапе. Применяя принцип "иди в ближайший не пройденный город" п — А.І раза, алгоритм находит частичный путь (цепь). Затем с помощью процедуры Рн из главы 1.3 частичный путь достраивается до гамильтонова цикла Щ, и теперь все ребра Н{ удаляются из графа G, и таким образом не используются при построении последующих і + 1,..., т гамильтоновых циклов. Описание алгоритма А% Положим г = 1. Этап г алгоритма А і\ Шаг 1. Если і = т + 1, алгоритм заканчивает работу. Иначе для фиксированного і рассматриваем граф G(V, Е) с оставшимися в нём ребрами и с г-ой весовой функцией ребер W{ : Е — R+. Выберем случайным образом ребро (иП} щ) графа G(V, Е). Полагаем путь Нь = {мп,Мі}, s = 1, и переходим к шагу 2. Шаг 2. Пусть построена цепь Нь = {иП} щ,..., us}. Если s = п — 4г, переходим к шагу 3. Иначе в графе G среди всех ребер (us,us+i) Є G \ НІ найдем минимальное по весу, и добавим его в путь Н{ = {ип,щ,... ,ws,ws+i}. Положим s = s + 1 и вернёмся на начало шага 2. Шаг 3. Рассмотрим неориентированный граф Н = (VH,EH) СО множеством вершин VH = ((У \ Hi) U {ws,wn}), где ип и иа это начало и конец пути Щ: и множеством ребер Ен, которое состоит из всех ребер графа G между вершинами из VH- При помощи процедуры Рн строим в этом подграфе гамильтонову цепь с концами иа и ип. Пусть эта цепь {иа = г і,г 2, ,vn-s,vn-s+i = ип}. В итоге, полагаем Нг = {ui,...,us,v2,... ,vn_s,un,ui} = {щ\щ\...,и$,щ }. Удалим из графа G все ребра, принадлежащие Н{: а также обратные им ребра в случае задачи на ориентированном графе. Положим і = і + 1 и переходим к этапу і + 1 алгоритма. В результате работы алгоритма получаем т рёберно непересекающихся гамильтоновых циклов Н\,..., Нт со значением целевой функции т і=1 еЄЩ Временная сложность алгоритма равна 0(тп2). Следует отметить, что веса рёбер (дуг) построенных гамильтоновых циклов являются попарно независимыми случайными величинами как в случае ориентированного, так и в случае неориентированного графа G.
Для того, чтобы оценить точность алгоритма A2l используется метод вероятностного анализа. Множество входов задачи определяется набором значений весов ребер W{{e) полного графа G(V, Е)} где W{ : Е — М+, 1 і m, є Є Е. Предполагается что эти веса ребер являются независимыми одинаково распределёнными случайными величинами, с некоторой функцией распределения D(x), определённой на неограниченном сверху интервале [ап, оо), ап 0.
Через / (/) и ОРТ{1) обозначим соответственно полученное алгоритмом А и оптимальное значение целевой функции задачи на входе /. Согласно определению 2, оценки точности (єп, 5п) алгоритма А будут определяться неравенством: m п Pr {EE (M- +i) і1 + Ч2(п) )ОРт) 6І2(п)} (2.1) Поймем, какое распределение имеют случайные величины Wi(us , Щ ) -случайные величины, равные весу s-oro ребра в г-ом гамильтоновом цикле, построенном алгоритмом А - если исходные веса ребер графа имеют распределение D(x).
Для фиксированной пары индексов i,s при 1 s п — 4i — 1, 1 г m, величина Wi{us , Щ ) равна весу кратчайшего ребра, существующего в G на г-ом этапе, из вершины us , которое было добавлено в частичный путь Щ на шаге 2 этапа і. После построения гамильтоновых циклов Н\,..., НІ-\ И удаления соответствующих ребер из G, у каждой вершины графа осталось по п — 1 — 2(і — 1) соседей. При добавлении нового ребра (щ , и ) в частичный путь НІ на шаге 2, s вершин графа, не считая саму вершинущ\ уже принадлежат Щ и, следовательно, не могут быть вторым концом нового ребра. Это означает, что на шаге 2 ребро (щ , ivfi) выбирается из не менее чем п — 1 — 2{г — 1) — s ребер, а значит его вес равен минимуму из не менее чем п — 2г — s + 1 независимых случайных величин с функцией распределения D(x). В итоге вес выбранного ребра W{(us , Щ ) оценим сверху случайной величиной s, строго равной минимуму из п — 2г — s + 1 независимых случайных величин, распределённых согласно D(x).
Входные данные с усеченным нормальным распределением
Учитывая (3.2) и (3.11), легко показать, что результаты, полученные в данной работе, могут быть расширены на случай любой функции распределения, которая мажорирует рассмотренные распределения. Говорим, что функция f(x) мажорирует функцию f(x), если f(x) f(x) для любых х, и функции имеют одинаковую область определения.
Доказательство. Пусть для входных данных задачи m-PSP с распределением f(x) на [ап,6п] или [ап,оо), где ап 0, получены оценки точности подхода ej и 5f. Полученная в (3.11) оценка для вероятности несрабатывания Sf не зависит от распределения, а значит будет верна и для входных данных задачи m-PSP с мажорирующим распределением f(x). Из свойства монотонности функций распределения и условия/(ж) f(x) для любых ж, следует f l(x) f l(x). Тогда для оценки относительной погрешности єт, учитывая формулы (3.2) и (3.4), имеем: є = JLr-i ( m(N + n)\ _г ±Гі /4m(7V + n)\ _1 = f an V n(n -1) / an V n(n - 1) / 7 Таким образом, для входных данных задачи m-PSP с мажорирующим распределением f(x) на [an,6n] или [ап,оо), где ап О, действительны оценки точности подхода є? f и 5?= 5f.
В частности, функция усеченного нормального распределения J\fan,a2 (х) с параметрами ап,о п = (Зп/2: аг 2ЙГ (« ехр dt , 0 ап х Na а2 (%) = —/ У27Г мажорирует функцию сдвинутого показательного распределения с параметрами ап, (Зп. Поэтому те же оценки точности подхода имеют место для входных данных с функцией усеченного нормального распределения на [ап, оо) с соответствующими параметрами.
В случае дискретного распределения входных данных задачи m-PSP, поскольку Pr {х = а} 0, для больших значений п подход с высокой вероятностью (w.h.p.) даёт точное решение задачи. При этом вероятность несрабатывания, т.е. доля случаев, когда алгоритм не возвращает никакое решение, стремится к нулю с ростом размерности задачи.
Теорема 19. Пусть веса ребер исходного графа являются независимыми одинаково распределёнными случайными величинами, с дискретной функцией распределения на отрезке [а, Ь] или неограниченном полуинтервале [а, оо); где а - минимально возможный вес ребра. Пусть распределение таково, что л (ЛА х 4m(Vnlnn + 1) ра = Рг(Х = а) . п — 1 Тогда при т п 5_6 /47 где 0 в 0.57 при достаточно больших п приведённый подход с использованием AQP на третьем шаге даёт точное 100 решение задачи с вероятностью несрабатывания равной: SA = [J& Доказательство. На шаге 1 строятся случайные графы G\,... ,Gm: в которых каждое ребро присутствует с вероятностью 1/т, независимо от других ребер. На шаге 2 назовём тяжёлыми и удалим из подграфов G\,... , Gm все ребра, чей вес больше а. Тогда вероятность того, что ребро лёгкое, равна Pr{вес ребра = а} = ра . Таким образом, G\,..., Gm случайные графы, в которых каждое ребро независимо от других ребер существует с вероятностью р = ра/т. (3.8)
Оценим оптимальное значение целевой функции снизу как ОРТ атп. Если алгоритм с шага 3 успешно выполнил работу для каждого подграфа G , 1 і m, то значение целевой функции, полученное подходом, равно FA = атп. То есть, задача решена точно.
Для поиска гамильтоновых циклов в графах G\,..., Gm применяется алгоритм AQP. При этом требуется, чтобы в подграфах было по крайней мереТУ = пл/п Inп ребер, чтобы AQP С большой вероятностью завершился успешно. Аналогично рассуждениям теоремы 17, 5 равная вероятности того, что в начале шага 3 в подграфе G i, 1 і m, окажется менее N ребер, не превосходит е п, если 4(УД +1) п — 1 Соединяя (3.8) и (3.9), получим условие на распределение входных данных, необходимое для успешной работы алгоритма: „ , г ч 4ш(л/п1пп +1) ра = Рг(Х = а) У3.10 п — 1 101 Вероятность несрабатывания 5 А подхода состоит из вероятностей 5 , что в графах G{ не останется достаточно ребер к шагу 3, и вероятностей 5: что, несмотря на то, что ребер в подграфах G{ было достаточно, алгоритм из шага 3 вернул ответ "неудача". 6А т6 + тб т6 + те п = О г ] , (3.1Ґ А л rnS -I- rnS гпЛ-1- ГПР П = Г) I пО.З+6 при т п-5-в/А, где 0 Є 0.5. П Следствие 2. При числе циклов т п05_6 /47 0 в 0.37 подход даёт точное решение с вероятностью несрабатывания О ( +в ) для задачи m-PSP с одинаковой весовой функцией, где веса ребер исходного графа являются независимыми одинаково распределёнными случайными величинами, со следующими дискретными функциями распределения:q
Об алгоритмах нахождения гамильтонова цикла в случайном графе
Элементы {1,7,67,5,65,3,83} поменялись местами согласно замечанию 5. В частности, элемент {1} в подстановке сет3а-1 занимает место элемента {7} в подстановке 7Г3. Верны соотношения 7 = l(mod 3), 17 = 2(mod 3), 45 = 0(mod 3), то есть элементы {7},{17} и {45} лежат в разных циклах подстановки 7Г3. Это значит, что элементы из [5 лежат в разных циклах сет3а-1. Следовательно, /Зсет3а-1 одноциклическая.
Подстановки а7га-1,сет2а-1,сет4а-1 одноциклические по замечанию 4. Для к = 1, 2,4, верно: 17 = 45(mod к). Элемент {1} в аттка-1 занимает место элемента {7} в подстановке тік. Так как 7 17 45, то тік = (7,... , 17,..., 45,...). А значит, аттка 1 = (1,..., 17,... , 45,...). Следовательно, /Заттка 1 одноциклические. Максимальное значение п, при котором данные построения невозможны, равно тах{п Є N6\U 83} = 63. Таким образом, при п Є N6 И п 63 8-АЗНО разрешима. Лемма 14. Если п Є N7 и п 75, то 8-АЗНО разрешима. Доказательство. Если п Є N7 = { п Є N \п не делится на 2, 7, и делится на 3, 5} и п 75, то допустимое решение задачи дают подстановки 7Г1 = 7Г2 = 7г; 7Г3 = ста-; 7Г4 = 7Г5 = шга:-1; 7Г6 = /Зшга:-1; 7Г7 = (Затга 1 (3 1, гдеа = (1,88)(4,88)(1,30)(2,30) и/3 = (1, 36)(32,36). Тогда подстановки х,у, входящие в условие (1.21), имеют вид: 1. тг, тг2; 2. «7Г, «7Г2, «7Г3, «7Г4, «7Г5 ; 3. cma 1, cm2a 1; 4. /Затта 1, /Затт2а 1, f3cm3a 1, /Затт4а 1] 5. (3(ш(і 1(3 1] 6. /3«7г5, /3«7г6, /За7г7. Подстановки первого, третьего и пятого типов одноциклические, согласно утверждению 1 и замечанию 3. Покажем одноцикличность подстановок второго типа. Поскольку п Є N7, то 7Г3 и 7Г6 являются произведениями трех непересекающихся циклов. Элементы {1}, {2}, {30} принадлежат различным циклам в подстановках 7Г3 и 7Г6, а значит, по замечанию 2, (1,30)(2, 30)7Г3 и (1,30)(2,30)7Г6 одноциклические. Подстановка 7Г5 является произведением пяти непересекающихся циклов. Элементы подстановки а принадлежат разным циклам 7Г5, поэтому, в силу замечания 2, атг5 одноциклическая. Для к = 1,2,4,7, подстановки 7Г одноциклические, и верно соотношение: 2 = 30(mod к). По утверждению 2, (1,30)(2, 30) одноциклические. Для к = 1,2,3,4,6,7, верно соотношение: 4 = 88(mod /с), и 2 4 . Тогда по утверждению 3, атг одноциклические. Покажем одноцикличность подстановок шестого типа. В результате последовательного соединения циклов из 7Г5, атг5 имеет вид: атг5 = (1, [mod = 4][mod = 3][mod = 2][mod = 5][6,... ,mod = 1]). Заметим, что 32 = 2(mod 5), а 36 = 6(mod 5). То есть, атг5 = (1,..., 32,... 36,...). В подстановках (1, 30)(2,30)7Г6 и (1,30)(2,30)7Г7 элемент {32} лежит в одном блоке с {4} и {88}, так как 32 = 4(mo i к) = 88(mod к) для к = 6,7. Поэтому, согласно замечанию 4, (1,88)(4,88)(1,30)(2,30)7rfc = (1,10,16,..., 32,...) = (1,..., 32,... 36,...). Таким образом, одноциклические атг , к = 5,6,7, имеют вид: (1,... , 32,... 36,...), и, в силу замечания 4, /Затг одноциклические. Покажем, наконец, одноцикличность подстановок четвертого типа. Подстановка атг3а-1 состоит из трех непересекающихся циклов. Согласно замечанию 5, элемент {1} в подстановке атг3а-1 занимает место элемента {4} в подстановке 7Г3. Числа 4,32,36 имеют различные остатки при делении на 3, а значит эти элементы лежат в разных циклах подстановки 7Г3. Поэтому, 1,32,36 лежат в разных циклах атг3а-1, и, по замечанию 2, /Затг3а-1 одноциклическая. Подстановки аіта 1 аіт2а 1 от4а 1 одноциклические по замечанию 4. Для к = 1, 2,4, верно: 32 = 36(mod к). Элемент {1} в аттка 1 занимает место элемента {4} в подстановке ттк. Так как 4 32 36, то ттк = (4,... , 32,..., 36,...). А значит, аттка 1 = (1,..., 32,... , 36,...). Следовательно, /Заттка 1 одноциклические. Максимальное значение п, при котором данные построения невозможны, равно тах{п Є N7\n 88} = 75. Таким образом, при п Є N7 и п 75 8-АЗНО разрешима. Лемма 15. Если п Є Щ, то 8-АЗНО разрешима. Доказательство. Если п Є N8 = { п Є N \п не делится на 2, и делится на 3, 5, 7}, то допустимое решение задачи дают подстановки 7Г1 = 7Г2 = 7г; 7Г3 = «7г; 7Г4 = 7Г5 = а7га ; 7Г6 = (Затга ; 7Г7 = /За7га (3 , где а = (1, 77)(17, 77)(1, 25)(13, 25)(1, 54)(2, 54) и (3 = (1,46)(21,46). Тогда подстановки х,у, входящие в условие (1.21), имеют вид: 1. 7Г, 7Г2; 2. СШ, «7Г2, СШ3, «7Г4, «7Г5 ; 3. сша-1, а7г2а-1; 4. /За7га-1, /За7г2а-1, /Затт3а 1, /За а 1; 5. /Затга-1/ -1; 6. /Затт5, /Зет6, /Затг7.
Подстановки первого, третьего и пятого типов одноциклические, согласно утверждению 1 и замечанию 3. Покажем одноцикличность подстановок второго типа. Поскольку п N8, то 7Г3 и 7Г6 являются произведениями трех непересекающихся циклов. Элементы {1}, {54}, {2} принадлежат различным циклам в подстановках 7Г3 и 7Г6, а значит, по замечанию 2, (1, 54)(2, 54)7Г3 и (1, 54)(2, 54)7Г6 одноциклические.
Подстановка 7Г5 — произведение пяти непересекающихся циклов. Элементы подстановки (1, 25)(13, 25)(1, 54)(2, 54) принадлежат разным циклам 7Г5, поэтому, в силу замечания 2, (1, 25)(13, 25)(1, 54)(2, 54)7Г5 одноциклическая.
Подстановка 7Г7 — произведение семи непересекающихся циклов. Элементы подстановки а принадлежат разным циклам 7Г , поэтому, в силу замечания 2, атг одноциклическая.
Для к = 1,2,4, верно: 2 = 54(mod ft). По утверждению 2, (1,54)(2,54)71- одноциклические. Для к = 1,2,3,4,6 верно: 13 = 25(mod к). Значит, по утверждению 3, (1, 25)(13, 25)(1, 54)(2, 54)7rfc одноциклические. Для к = 1,... ,6 верно: 17 = 77(mod ft) и 13 17. Таким образом, используя утверждение 3, получим одноцикличность подстановок атгк. Покажем одноцикличность подстановок шестого типа. В результате последовательного соединения циклов из 7Г5, (1, 25)(13, 25)(1, 54)(2, 54)7Г5 имеет вид: