работа по Теория информационных процессов и систем на тему Алгоритм Фаулкса и его приложения (стр. 3 из 4)

Рис. 16.5

Возвращаясь к задаче Фреголи, которую мы решили выше, мы устанавливаем, что вычисление М ^[2] дало нам пути длины <= 2, вычисление М ^[4] - пути длины <= 4. Если бы мы вычислили М ^[7] , мы имели бы пути длины <= 7; в действительности мы вычислили М ^[8] , которая дает все пути, ибо каждый путь длины больше 7 проходит два раза через одну точку. Мы констатировали совпадении М ^[8] и М ^[4] .

Затем мы нашли классы эквивалентности, представляя М ^[4] в форме ABDFGCEH; в частности, BDF и EH образуют классы эквивалентности.

Замечание: Очевидно, что когда записывают отношения порядка (как, например, отношения предшествования) в некотором множестве, алгоритм Фаулкса представляет собой один из методов выяснения их совместимости (поскольку не должно существовать цикла). Он позволяет, кроме того, найти все отношения порядка между двумя, которые выводятся из предположений в силу транзитивности отношения порядка (из А<B и В<С следует, что А<С, хотя это отношение не было явно выражено ранее).

Только тогда, когда между точками нет связи виде отношения, можно вводить законно отношение индифферентности ><.

Зато на практике часто приходится иметь дело с соотношением частичного упорядочения, допускающим циклы. В этом случае этот алгоритм дает нам метод, хорошо приспособленный для решения задач.

Вводное описание Гамильтоновых циклов

Название «гамильтонов цикл» произошло от задачи «Кругосветное путешествие» предложенной ирландским математиком Вильямом Гамильтоном в 1859 году. Нужно было, выйдя из исходной вершины графа, обойти все его вершины и вернуться в исходную точку. Граф представлял собой укладку до декаэдра, каждой из 20 вершин графа было приписано название крупного города мира.

Основные понятия и определения

Цикл называется гамильтоновым, если он содержит все вершины графа. Цепь называется гамильтоновой, если она содержит все вершины графа. Если граф имеет простой цикл, содержащий все вершины графа по одному разу, то такой цикл называется гамильтоновым циклом, а граф называется гамильтоновым графом. Граф, который содержит простой путь, проходящий через каждую его вершину, называется полугамильтоновым. Это определение можно распространить на ориентированные графы, если путь считать ориентированным. Гамильтонов цикл не обязательно содержит все ребра графа. Ясно, что гамильтоновым может быть только связный граф и, что всякий гамильтонов граф является полугамильтоновым. Заметим, что гамильтонов цикл существует далеко не в каждом графе. В графе берется первая произвольная вершина, и заносится в стек как уже просмотренная, затем смотрятся все смежные с ней. Если найдена какая-то смежная вершина, то она заносится в стек и дальше просматриваются все смежные с ней вершины. И так до тех пор пока не будет найден гамильтонов цикл или цепь, или пока не будут просмотрены все возможные варианты.

Метод Робертса и Флореса

Следующая схема перебора, использующая обычную технику возвращения, была первоначально предложена Робертсом и Флоресом [2, 3]. Начинают с построения (k×n) матрицы M = ||m[i][j]||, где элемент m[i][j] есть i-ая вершина (скажем xq), для которой в графе G = (X, Г) существует дуга (xj, xq). Вершины xq в множестве Г(xj) можно упорядочить произвольно, образовав элементы j-ого столбца матрицы M. Число строк k матрицы M будет равно наибольшей полу-степени исхода вершины.

Метод состоит в следующем. Некоторая начальная вершина (скажем xj) выбирается в качестве отправной и образует первый элемент множества S, которое каждый раз будет хранить уже найденные вершины строящейся цепи. К S добавляется первая вершина (например a) в столбце x1. Затем к множеству S добавляется первая возможная вершина (например, вершина b) в столбце a, потом добавляется к S первая возможная вершина (например, вершина c) в столбце b и т. д. Под "возможной" вершиной мы понимаем вершину, ещё ен принадлежащую S. Существую две причины, препятствующие включению некоторой вершины на шаге r в множество S = {x1, a, b, c, …, xr-1, xr}. Или (1) в столбце xr нет возможной вершины, или (2) цепь, определяемая последовательностью вершин в S, имеет длину n-1, т. е. является гамильтоновой цепью. В случае (2) (а) в графе G существует дуга (xr, x1) и поэтому найден гамильтонов цикл, или (б) дуга (xr, x1) не существует и не может быть получен никакой гамильтонов цикл. В случаях (1) и (2б) следует прибегнуть к возвращению, в то время как в случае (2а) можно прекратить поиск и напечатать результат. Возвращение состоит в удалении последней включенной вершины xr из S, после чего остается множество S = {x1, a, b, c, …, xr-1}, и добавлении к S первой возможной вершины, следующей за xr, в столбце xr-1 матрицы M. Если не существует никакой возможной вершины, делается следующий шаг возвращения, и т. д.

Задачи связанные с поиском гамильтоновых циклов

В ряде отраслей промышленности возникает следующая задача планирования. Нужно произвести n продуктов, используя единственный тип аппаратуры. Аппарат должен быть перенастроен после того как был произведен продукт pi (но до того как начато производство продукта pj), в зависимости от комбинации (pi,pj). Стоимость перенастройки аппаратуры постоянна и не зависит от производимых продуктов. Предположим, что эти продукты производятся в непрерывном цикле, так что после производства последнего из n продуктов снова возобновляется в том же фиксированном цикле производство первого продукта.

Возникает вопрос о том, может ли быть найдена циклическая последовательность производства продуктов pi (i=1,2,…,n), не требующая перенастройки аппаратуры. Если представить эту задачу в виде ориентированного графа, то ответ на поставленный вопрос зависит от того, имеет ли этот ориентированный граф гамильтонов цикл или нет.

Если не существует циклической последовательности продуктов, не требующей перенастройки аппаратуры, то какова должна быть последовательность производства с наименьшими затратами на перенастройку, т.е. требующая наименьшего числа необходимых перенастроек?

Таким образом мы рассмотрим следующие две задачи.

Задача 1. Дан ориентированный граф G, требуется найти в G гамильтонов цикл (или все циклы), если существует хотя бы один такой цикл.

Задача 2. Дан полный ориентированный цикл G, дугам которого приписаны произвольные веса C=[cij], найти такой гамильтонов цикл, который имеет наименьший общий вес. Следует отметить, что если ориентированный граф G неполный, то его можно рассматривать как полный ориентированный граф, приписывая отсутствующим дугам бесконечный вес.

Алгоритмы решения задачи коммивояжера и ее вариантов имеют большое число практических приложений в различных областях человеческой деятельности. Рассмотрим, например, задачу, в которой грузовик выезжает с центральной базы для доставки товаров данному числу потребителей и возвращается назад на базу. Стоимость перевозки пропорциональна пройденному грузовиком расстоянию, и при заданной матрице расстояний между потребителями маршрут с наименьшими транспортными затратами получается как решение соответствующей задачи коммивояжера. Аналогичные типы задач возникают при сборе почтовых отправлений из почтовых ящиков, составлении графика движения школьных автобусов по заданным остановкам и т.д. Задача очень легко обобщается и на тот случай, когда доставкой (сбором) занимаются несколько грузовиков, хотя эту задачу можно также переформулировать как задачу коммивояжера большей размерности. Другие приложения включают составление расписания выполнения операций на машинах, проектирование электрических сетей, управление автоматическими линиями и т.д.

Очевидно, что сформулированная выше задача (1) является частным случаем задачи (2). В самом деле, приписывая случайным образом дугам заданного ориентированного графа G конечные веса, получаем задачу коммивояжера. Если решение для этой задачи, т.е. кратчайший гамильтонов цикл, имеет конечное значение, то это решение является гамильтоновым циклом ориентированного графа G (т.е. ответом на задачу 1). Если же решение имеет бесконечное значение, то G не имеет гамильтонова цикла.

С другой стороны можно дать еще одну интерпретацию задачи 1).
Рассмотрим снова полный ориентированный граф G1 с общей матрицей весов дуг
[cij] и рассмотрим задачу нахождения такого гамильтонова цикла, в котором самая длинная дуга минимальна. Эту задачу можно назвать минимаксной задачей коммивояжера. Тогда классическую задачу коммивояжера в той же терминологии можно было бы назвать мини-суммой задачей коммивояжера. Покажем теперь, что задача (1) действительно эквивалентна минимаксной задаче коммивояжера.

В вышеупомянутом полном ориентированном графе G1 мы можем наверняка найти гамильтонов цикл. Пусть это будет цикл Ф1, и пусть вес самой длинной его дуги равен ?1. Удалив из G1 любую дугу, вес которой не меньше ?1,получим ориентированный граф G2. Найдем в ориентированном графе G2гамильтонов цикл Ф2, и пусть вес его самой длинной дуги равен ?2. Удалим из G2 любую дугу, вес которой не меньше ?2, и так будем продолжать до тех пор, пока не получим ориентированный граф Gm+1, не содержащий никакого гамильтонова цикла. Гамильтонов цикл Фm в Gm (с весом ?m) является тогда по определению решением минимаксной задачи коммивояжера, так как из отсутствия гамильтонова цикла в Gm+1 следует, что в G1 не существует никакого гамильтонова цикла, не использующего по крайней мере одну дугу с весом, большим или равным ?m.