Задача поиска гамильтонова цикла в графе

Однако эти маршруты являются безымянными и не дают информации о вершинах в маршрутах. Если в матрице смежности заменить единицы на имена вершин, то возведение такой матрицы в степень будет давать больше информации о маршрутах.В работе [4] автор приводит алгебраический метод построения гамильтоновых циклов, который включает в себя построение всех простых цепей с помощью последовательного перемножения матриц.В качестве начальной матрицы в описываемом методе берется матрица смежности Aзаданного графа, в которой все диагональные элементы равны нулю (отсутствие петель в графе). Исходная матрица модифицируется в матрицу B так, что вместо единиц в матрице Bстоят имена вершин.Далее последовательно находятся вспомогательные матрицы P'k и PkP'k=BPk,P1=A,Pk=Ф(P'k)(5)Матрицы Bи Pk умножаются как обычные матрицы, при этом под произведением вершин понимается некоммутативная бинарная операция, заданная на множестве слов. Словом будем считать упорядоченную последовательность вершин (букв). Под произведением слова u1u2...uk и слова v1v2...vmбудем понимать слово u1u2...ukv1v2...vm. Оператор Φ, преобразующий матрицу P'k в матрицуPk воздействует на элементы pij матрицы, заменяя нулем те элементы, в которых содержатся вершины vi или vj, так кактакие элементы содержат контуры, замыкающиеся на vi или vj. Для упрощения расчетов можно дополнительно обнулять диагональ матриц Pk кроме самой последней матрицы Pn, поскольку искомые циклы будут находиться как раз на её диагонали (без начальной и конечной вершины, которые необходимо добавить).[3]Рассмотрим алгебраический метод на примере следующего графа (рис. 15).Рисунок 15– Граф для поиска гамильтонова цикла алебраическим методомИсходная матрица смежности этого графа равнаabcdea01010b00011A=c01001d00100e10100Модифицировананя матрица смежности равнаabcdea0b0d0b000deB=c0b00ed00c00ea0c00Пусть первая матрица произведений P1=A. Матрица P'2=BP1равнаabcdea00dbbbe0d+ed0P'2=ce0e0bd0c00ce0a+c0acМатрицу P2получаем из матрицы P'2, заменяя подчеркнутые элементы в P'2 на нули (диагональные элементы). Матрица P'3=BP2равнаabcdeabedcbd+be0dcb0dc+ea+ec0eadcP'3=cbeea+ecbd+beea0dce00cbcbece0cadab+cbab+cbПолучаем матрицу P4 (P3получаем из матрицы P'3, заменяя подчеркнутые элементы в P'3 на нули, а P'4):abcdea0000bdc+dcbbdce0ead00P4=c000bea+eab0dcbecea000e0adcabd00Последняя матрица P5 – диагональная. abcdeabdce+dcbe0000b0dcea+eadc000P5=c00bead+eabd00d000cbea+ceab0e0000abdc+adcbДобавление замыкающих точек даёт нам гамильтоновы циклы:abdcea, adcbea, bdceab, beadcb, cbeadc, ceabdc, dcbead, dceabd, eabdce, eadcbe.При этом различных гамильтоновых циклов только два: abdcea, adcbea. Остальные получаются из первых двух перестановкой начальной вершины.Можно не строить финальную матрицу Pn, а ограничиться построением матрицыPn-1, дающей все гамильтоновы цепи (имеющие длину n-1) между всеми парами вершин. Гамильтоновы циклы получаются тогда сразу из цепей в Pn-1 и тех дуг из G, которые соединяют начальную и конечную вершины каждой цепи. Этот метод довольно простой, но недостатки его очевидны: при каждом умножении матриц, элементы матрицы будут состоять извсё большего числа слагаемых, соответственно увеличивая требования к необходимому для хранения матрицы Pk объему памяти.Алгоритм Робертса и ФлоресаАлгебраические методы определения гамильтоновых циклов не могут быть применены с более чем несколькими десятками вершин, так как они требуют слишком большого времени работы и большой памяти компьютера. Более приемлемым является метод Робертса и Флореса, который относится к переборным методам. В противоположность алгебраическим методам, с помощью которых пытаются найти сразу все гамильтоновы циклы и при реализации которых приходится хранить все цепи, которые могут оказаться частями таких циклов, метод перебора имеет дело с одной цепью, непрерывно продлеваемой вплоть до момента, когда либо получается гамильтонов цикл, либо становится ясно, что эта цепь не может привести к гамильтонову циклу. Тогда цепь изменяетсякаким-либо систематическим способом (гарантирующим, что будут проверены все возможные варианты), после чего продолжается поиск гамильтонова цикла. Такой способ требует небольшой объем памяти и находитза один раз один гамильтонов цикл, хотя по затратам времени он является экспоненцильным относительно числа вершин графа.В графе произвольным образом выбирается первая вершина, заносится в стек и помечается просмотренной, затем смотрятся все смежные с ней. Если найдена какая-то смежная и не просмотренная ранее вершина, то она заносится в стек. Дальше просматриваются вершины смежные с ней. Для остановки просмотра имеется всего две причины: либо больше нет смежных вершин, либо построенная последовательность включает все вершины и является гамильтоновой цепью.Если больше не найдено смежных вершин, то вершина, попавшая в стекпоследней, удаляется, и просматриваются предыдущие вершины. И так до тех пор, пока не будут просмотрены все возможные варианты. [9]Если построена последовательность смежных вершин длиной n, то возможны два варианта:а) в графесуществует дуга, соединяющая последнюю найденную вершину с первой, и поэтому найден гамильтонов цикл, илиб) дуга, соединяющая последнюю найденную вершину с первой, не существует и не может быть получен никакой гамильтонов цикл.[4]Во втором случае производится удаление последней добавленой вершины и производится поиск других смежных вершин, в случае а) можно прекратить поиск и вывести результат (если требуется найти только один гамильтонов цикл), или (если нужны все гамильтоновы циклы) вывести результат и вернуться на шаг назад.Поиск заканчивается тогда, когда в стеке остается только одна вершина – первая, и не существует никакой возможной вершины, которую можно добавить к последовательности, так что удаление этой вершины делает стек пустым.[7]В качестве примера рассмотрим поиск гамильтоновых циклов в графе, изображенном на рис. 16.Рисунок 16 – Обход графа с помощью алгоритма Робертса и ФлоресаПри обходе графа по алгоритму Робертса и Флореса получим следующие последовательности вершин (начиная с вершины 1):«2»«3»«5»1) S = {1}2) S = {1, 2}3) S = {1, 2, 3}4) S = {1, 2, 3, 4}5) S = {1, 2, 3, 4, 5} – Г 4→3 4→56) S = {1, 2, 3, 4}7) S = {1, 2, 3} 3→1 3→2 3→48) S = {1, 2}9) S = {1}{1, 2, 3, 4, 5,1}10) S = {1, 3} 3→211) S = {1, 3, 2} 2→112) S = {1, 3} 2→313) S = {1, 3, 4} 3→4 4→514) S = {1, 3, 4, 5, 4} 5→нет15) S = {1, 3, 4}16) S = {1, 3}17) S = {1}18) S = {1, 5}19) S = {1, 5, 4}20) S = {1, 5, 4, 3}21) S = {1, 5, 4, 3, 2} - Г22) S = {1, 5, 4, 3}23) S = {1, 5, 4}24) S = {1, 5}25) S = {1}26) S = Ø{1, 5, 4, 3, 2,1}В результате получили два гамильтонова цикла: {1,2,3,4,5,1} и {1,5,4,3,2,1}.Алгоритм Робертса и Флореса(поиска с возвращением)приходит к экспоненциальной сложности, но поскольку он является общим методом, его можно несколько усовершенствовать за счет- выбора стартового узла с как можно меньшей степенью;- способа перестройки дерева поиска на каждом шаге так, чтобы осуществлять только два выбора;-разбить задачу наk подзадач, при этом могут повыситься требования к памяти, но будет получен выигрыш во времени. [10]Чтобы метод был полезен, его следует использовать как схему решения, которую надо хорошо приспособить к конкретнойзадаче.Среди переборных методов выделяются ещё методы, разбивающие основную задачу на ряд подзадач. Так, в литературе рассматривается способпоиска гамильтонова цикла методом перебора гамильтоновых подграфов.[1]Метод использует 1. Перебор гамильтоновых разбиений.2.Удаление некоторых дуг, которые не входят в какой-либо гамильтоновый цикл.3.Ускоренное углубление по дереву перебора вглубь.4. Мультицепной метод.Под гамильтоновым разбиением орграфа 𝐺=(𝑉,E) понимается разбиение его вершин на непересекающиеся подмножества 𝑉0, 𝑉1, 𝑉2, , 𝑉𝑘−1 такие, что все индуцируемые ими подграфы орграфа 𝐺 содержат гамильтоновы контуры.Для нахождения гамильтонова разбиения по заданному орграфу строится двудольный орграф, дуги в максимальном паросочетании двудольного орграфа составляют гамильтоново разбиение. Если какая то дуга (u,v) не попадает ни в одно из гамильтоновых разбиений, то она удаляется из рассмотрения, при этом орграф может стать не сильно связным.Алгоритм определяет компоненты связности исходного графа, а затем проверяет – существуют ли мосты между компонентами связности. Если все найденные гамильтоновые разбиения можно связать между собой, то получаем гамильтоновый цикл (рис. 17).Рисунок 17 – Применение эвристики в алгоритме поиска гамильтонова цикла методом перебора гамильтоновых подграфов (а – выделенные компоненты связности, б) гамильтоново разбиение, в) гамильтонов цикл после соединения компонент связности)Конечно, не каждый граф позволяет найти гамильтонов цикл применением эвристики, однако на произвольных графах с большим колчеством вершин эвристика работает с допустимой погрешностью в 1% [1]Гамильтоновы разбиения также используются для ускоренного перебора дерева «в глубину», при этом дополнительно можно использовать и эвристические алгоритмы.Мультицепной метод сначала удаляет все лишние дуги в рассматриваемой цепи, затем при просмотре остальных вершин орграфа помечает их как начальные и конечные вершины цепей, и на последнем этапе объединяет цепи. Этот алгоритм повторяется, если остались помеченные вершины или удаленные дуги. Утверждается, что этот метод позволяет выполнять поиск гамильтонова цикла на многовершинных произвольных графах. Применение рассмотренного алгоритма возможно при создании отверстий в платах роботом, задачах секвенирования генома, задачах логистики. [1]Однако неявный метод перебора имеет для большинства типов графов очень небольшой показатель роста времени вычислений в зависимости от числа вершин. Он может быть использован для нахождения гамильтоновых циклов в очень больших графах. Этот метод включает в себя построение всех простых цепей с помощью последовательного перемножения матриц.ЗаключениеЗадача отыскания гамильтонова цикла или эквивалентная ей задача коммивояжера являются практически очень востребованной, но для нее неизвестен (и, возможно, не существует) эффективный алгоритм решения.В настоящее время благодаря использованию современной вычислительной техники для ответа на вопрос – является ли граф гамильтоновым и если да, то каковы гамильтоновы циклы в графе? – наиболее точно отвечают различные переборные методы. При этом, если при малом числе вершин графа можно использовать полный перебор, пожертвовав временем, но сэкономив объемы памяти, то чем больше число вершин в графе, тем чаще применяются переборные методы с отсеканием неудачных последовательностей вершин.Базируется большинство подобных методов на алгоритме Робертса и Флореса(поиск «в глубину»), либо на методе ветвей и границ.Развитие вычислительной техники позволяет подключать к решению задачи поиска гамильтонова цикла различные эвристические алгоритмы(генетические, муравьиные алгоритмы и др.), нейронные искусственные сети, а также их комбинации с переборными методами, как в работе [1].Задача отыскания гамильтонова цикла в графе является классической трудноразрешимой задачей теории графов и до сих пор не имеет эффективного решения. Точные методы требуют больших временных затрат, а приближенные методы находятся в развитии.В процессе написания данной курсовой работы мы рассмотрели основные понятия теории графов и понятия, относящиеся к обходу графов и гамильтонову циклу, рассмотрели условия существования гамильтонова цикла в графе и различные методы решения задачи поиска гамильтонова цикла в графе, привели примеры их применения.Таким образом, поставленные в настоящей курсовой цель и задачи выполнены.Список использованной литературыГавриков, А. В. О поиске гамильтонова цикла методом перебора гамильтоновых подграфов / А. В. Гавриков // Компьютерные науки и информационные технологии: Материалы Международной научной конференции, Саратов, 02–03 июля 2018 года. – Саратов: ИЦ "Наука", 2018. – С. 95-98. – EDN FKOUUJ.Галяутдинов Р.Р. Задача коммивояжера – метод ветвей и границ // Сайт преподавателя экономики. [2020]. URL: http://galyautdinov.ru/post/zadacha-kommivoyazhera (дата обращения: 19.05.2022).Кирсанов М.Н. Графы в Maple. Задачи, алгоритмы, программы. – М.: Издательство ФИЗМАТЛИТ, 2007. – 168 с.Кристофидес Н. Теория графов. Алгоритмический подход / Н.Кристофедерс – М.:Мир, 1978Курейчик, В. М. Обзор состояния проблемной области по теме решение задачи коммивояжёра / В. М. Курейчик, Ю. А. Логунова, А. С. Игнатьева // Информатика, вычислительная техника и инженерное образование. – 2017. – № 3(31). – С. 39-59. – EDN YOPCLY.Мудров В.И. Задача о коммивояжере. – М.: Знание, 1969. – 64 с.Носов, В. В. Обзор методов отыскания гамильтоновых циклов в графе / В. В. Носов, М. С. Орлов // Университетский комплекс как региональный центр образования, науки и культуры : материалы Всероссийской научно-методической конференции, Оренбург, 01–03 февраля 2017 года / Оренбургский государственный университет. – Оренбург: Оренбургский государственный университет, 2017. – С. 3137-3141. – EDN YKCYTF.Свами М., Тхуласираман К. Графы, сети и алгоритмы. – М.: Мир, 1984.– 454с.Чувагина, В. В. Обучающая программа по теме "Нахождение гамильтоновых циклов с помощью алгоритма Робертса-Флореса и решение задачи коммивояжёра методов ветвей и границ" / В. В. Чувагина, П. А. Корнилов // Инновационный потенциал молодёжи - 2017 : сборник статей открытого университетского конкурсного отбора инновационных проектов молодых учёных по приоритетным направлениям науки и техники, Ярославль, 14 марта 2017 года. – Ярославль: Ярославский государственный педагогический университет им. К.Д. Ушинского, 2017. – С. 16-18. – EDN XPDRAT.Чумаченко, А. А. Поиск с возвращением в гамильтоновых циклах / А. А. Чумаченко, М. С. Шадричева // Аллея науки. – 2017. – Т. 1. – № 12. – С. 402-404. – EDN ZGDLGN.Шухман, Е. В. Алгоритм Эйлера поиска гамильтоновых циклов и путей / Е. В. Шухман // История науки и техники. – 2014. – № 12. – С. 3-11. – EDN TDOYLD.