МЕНЮ


Фестивали и конкурсы
Семинары
Издания
О МОДНТ
Приглашения
Поздравляем

НАУЧНЫЕ РАБОТЫ


  • Инновационный менеджмент
  • Инвестиции
  • ИГП
  • Земельное право
  • Журналистика
  • Жилищное право
  • Радиоэлектроника
  • Психология
  • Программирование и комп-ры
  • Предпринимательство
  • Право
  • Политология
  • Полиграфия
  • Педагогика
  • Оккультизм и уфология
  • Начертательная геометрия
  • Бухучет управленчучет
  • Биология
  • Бизнес-план
  • Безопасность жизнедеятельности
  • Банковское дело
  • АХД экпред финансы предприятий
  • Аудит
  • Ветеринария
  • Валютные отношения
  • Бухгалтерский учет и аудит
  • Ботаника и сельское хозяйство
  • Биржевое дело
  • Банковское дело
  • Астрономия
  • Архитектура
  • Арбитражный процесс
  • Безопасность жизнедеятельности
  • Административное право
  • Авиация и космонавтика
  • Кулинария
  • Наука и техника
  • Криминология
  • Криминалистика
  • Косметология
  • Коммуникации и связь
  • Кибернетика
  • Исторические личности
  • Информатика
  • Инвестиции
  • по Зоология
  • Журналистика
  • Карта сайта
  • Эйлеровы и гамильтоновы графы

    момента, когда либо получается гамильтонов цикл, либо становится ясно, что

    эта цепь не может привести к гамильтонову циклу. Тогда цепь модифицируется

    некоторым систематическим способом (который гарантирует, что в конце концов

    будут исчерпаны все возможности), после чего продолжается поиск

    гамильтонова цикла. В этом способе для поиска требуется очень небольшой

    объем памяти и за один раз находится один гамильтонов цикл.

    Следующая схема перебора, использующая обычную технику возвращения,

    была первоначально предложена Робертсом и Флоресом. Начинают с построения

    (kЧn)-матрицы M=[mij], где элемент mij есть i-я вершина (скажем xq), для

    которой в графе G(X,Г) существует дуга (xj,xq). Вершины xq во множестве

    Г(xj) можно упорядочить произвольно, образовав элементы j-го столбца

    матрицы M. Число строк k матрицы M будет равно наибольшей полустепени

    исхода вершины.

    Метод состоит в следующем. Некоторая начальная вершина (скажем, x1)

    выбирается в качестве отправной и образует первый элемент множества S,

    которое каждый раз будет хранить уже найденные вершины строящейся цепи. К S

    добавляется первая вершина (например, вершина a) в столбце x1. Затем к

    множеству S добавляется первая возможная вершина (например, вершина b) в

    столбце a, потом добавляется к S первая возможная вершина (например,

    вершина c) в столбце b и т.д. Под «возможной» вершиной мы понимаем вершину,

    еще не принадлежащую S. Существуют две причины, препятствующие включению

    некоторой вершины на шаге r во множество S = {x1,a,b,c, … ,xr-1,xr}:

    В столбце xr нет возможной вершины.

    Цепь, определяемая последовательностью вершин в S, имеет длину n-1, т.е.

    является гамильтоновой цепью.

    В случае 2) возможны следующие случаи:

    В графе G существует дуга (xr,x1), и поэтому найден гамильтонов цикл.

    Дуга (xr,x1) не существует и не может быть получен никакой гамильтонов

    цикл.

    В случаях (1) и (2b) следует прибегнуть к возвращению, в то время как

    в случае (2a) можно прекратить поиск и напечатать результат (если требуется

    найти только один гамильтонов цикл), или (если нужны все такие циклы)

    произвести печать и прибегнуть к возвращению.

    Возвращение состоит в удалении последней включенной вершины xr из S,

    после чего остается множество S = {x1,a,b,c, … ,xr-1}, и добавлении к S

    первой возможной вершины, следующей за xr, в столбце xr-1 матрицы M. Если

    не существует никакой возможной вершины, делается следующий шаг возвращения

    и т.д.

    Поиск заканчивается в том случае, когда множество S состоит только из

    вершины x1 и не существует никакой возможной вершины, которую можно

    добавить к S, так что шаг возвращения делает множество S пустым.

    Гамильтоновы циклы, найденные к этому моменту, являются тогда всеми

    гамильтоновыми циклами, существующими в графе.

    Рассмотрим пример поиска гамильтонова цикла в графе переборным методом

    Робертса и Флореса.

    Пример:

    [pic]

    "2"

    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>5

    6) S = {1, 2, 3, 4}

    7) S = {1, 2, 3} 3>1 3>2 3>4

    8) S = {1, 2}

    9) S = {1}

    "3"

    10) S = {1, 3} 3>2

    11) S = {1, 3, 2} 2>1

    12) S = {1, 3} 2>3

    13) S = {1, 3, 4} 3>4 4>5

    14) S = {1, 3, 4, 5, 4} 5>нет

    15) S = {1, 3, 4}

    16) S = {1, 3}

    17) S = {1}

    "5"

    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 = Ш

    §8. Улучшение метода Робертса и Флореса

    Рассмотрим улучшение основного переборного метода Робертса и Флореса.

    Допустим, что на некотором этапе поиска построенная цепь задается

    множеством S = {x1,x2, … ,xr} и что следующей вершиной, которую

    предполагается добавить к S, является x*[pic]S. Рассмотрим теперь две

    следующие ситуации, в которых вершина является изолированной в подграфе,

    остающемся после удаления из G(X,Г) всех вершин, образующих построенную до

    этого цепь.

    Если существует такая вершина x[pic]X\S, что x[pic]Г(xr) и Г-1(x)[pic] S,

    то, добавляя к S любую вершину x*, отличную от x, мы не сможем в

    последующем достигнуть вершины x ни из какой конечной вершины построенной

    цепи, и, значит, эта цепь не сможет привести нас к построению гамильтонова

    цикла. Таким образом, в этом случае x является единственной вершиной,

    которую можно добавить к S для продолжения цепи.

    Если существует такая вершина x[pic]X\S, что x[pic]Г-1(x1) и Г(x)[pic]

    S[pic]{x*} для некоторой другой вершины x*, то x* не может быть добавлена к

    S, так как тогда в остающемся подграфе не может существовать никакой цепи

    между x и x1. Цепь, определяемая множеством S [pic] {x*}, не может поэтому

    привести к гамильтонову циклу, а в качестве кандидата на добавление к

    множеству S следует рассмотреть другую вершину, отличную от x*.

    Проверка условий (a) и (b) будет, конечно, замедлять итеративную

    процедуру, и для небольших графов (менее чем с 20 вершинами) не получается

    никакого улучшения первоначального алгоритма Робертса и Флореса. Но для

    больших графов эта проверка приводит к заметному сокращению необходимого

    времени вычислений, уменьшая его обычно в 2 или более раз.

    §9. Мультицепной метод

    После внимательного изучения операций алгоритма перебора Робертса и

    Флореса становится очевидным, что даже после сделанного улучшения не

    слишком много внимания уделяется оставшейся части графа, в которой берется

    последовательность вершин, продолжающих построенную цепь. Обычно построение

    цепи S0 в процессе поиска (S0 рассматривается и как упорядоченное множество

    вершин, и как обычное множество) подразумевает существование еще каких-то

    цепей в других частях графа. Эти предполагаемые цепи либо помогают быстрее

    построить гамильтонов цикл, либо указывают на отсутствие такого цикла,

    содержащего цепь S0, что позволяет сразу прибегнуть к возвращению.

    Метод, описанный ниже, был предложен первоначально для

    неориентированных графов; здесь дается его небольшое видоизменение для

    ориентированных графов. Метод состоит в следующем.

    Допустим, что на некотором этапе поиска построена цепь S0 и возможны

    цепи S1, S2, … . Рассмотрим какую-либо «среднюю» вершину одной из этих

    цепей (слово «средняя» здесь означает любую вершину, отличную от начальной

    и конечной). Поскольку эта вершина уже включена в цепь с помощью двух дуг,

    то очевидно, что все другие дуги, входящие или выходящие из такой вершины,

    могут быть удалены из графа. Для любой начальной вершины вышеуказанных

    цепей можно удалить все дуги, исходящие из нее (за исключением дуги,

    включающей эту вершину в цепь), а для любой конечной вершины можно удалить

    все дуги, оканчивающиеся в ней (опять-таки за исключением дуги, включающей

    ее в цепь). Кроме того, за исключением случая, когда существует только одна

    цепь (скажем, S0), проходящая через все вершины графа G (т.е когда S0 —

    гамильтонова цепь), любая имеющаяся дуга, ведущая из конца любой цепи в

    начальную вершину этой же цепи, может быть удалена, так как такая дуга

    замыкает не гамильтоновы циклы.

    Удаление всех этих дуг даст граф — со всеми «средними» вершинами

    цепей, в котором только одна дуга оканчивается в каждой вершине и только

    одна дуга исходит из нее. Все эти «средние» вершины и дуги, инцидентные им,

    удаляются из G, а вместо них для каждой цепи вводится единственная дуга,

    идущая от начальной вершины цепи до ее конечной вершины. В результате всего

    этого получается редуцированный граф Gk(Xk,Гk), где k — индекс,

    показывающий номер шага поиска.

    Рассмотрим теперь продолжение цепи S0 (сформированной в результате

    поиска), осуществляемое путем добавления вершины xj, которая является

    возможной в смысле алгоритма Робертса и Флореса, т.е. в Gk существует дуга,

    исходящая из конечной вершины цепи S0 — обозначим эту вершину e(S0) — и

    входящая в вершину xj. Добавление xj к S0 осуществляется так:

    Сначала удаляются из Gk все необходимые дуги, т.е.

    a) все дуги, оканчивающиеся в xj или исходящие из e(S0), за исключением

    дуги (e(S0), xj);

    b) все дуги, выходящие из xj в начальную вершину пути S0;

    c) если окажется, что xj является начальной вершиной другой цепи Sj, то

    следует удалить также любую дугу, идущую из конечной вершины цепи Sj в

    начальную вершину цепи S0.

    Обозначим граф, оставшийся после удаления всех дуг, через G’k(Xk,Гk’).

    Если существует вершина x в графе G’k, не являющаяся конечной ни для

    одной из цепей S0, S1, … и которая после удаления дуг имеет полустепень

    захода, равную единице, т.е. |Г-1k’(x)|=1, то выкинуть все дуги, исходящие

    из вершины v= Г-1k’(x), за исключением дуги (v, x).

    Если существует вершина x графа G’k, не являющаяся начальной ни для

    какой цепи и которая после удаления дуг имеет полустепень исхода, равную

    единице, т.е. |Гk’(x)|=1, то выкинуть все дуги, исходящие из вершины x, за

    исключением дуги (x, Гk’(x)).

    Перестроить все цепи и удалить дуги, ведущие из конечных в начальные

    вершины.

    Повторить шаг 2 до тех пор, пока можно удалять дуги.

    Удалить из оставшегося графа G’k все вершины, полустепени захода и исхода

    которых равны единице, т.е. вершины, которые стали теперь «средними»

    вершинами цепей. Это удаление производится так, как это было описано выше,

    в результате чего получается новый редуцированный граф Gk+1, заменяющий

    предыдущий граф Gk.

    Совершенно очевидно, что если добавление вершины xj к цепи S0 делает

    полустепень захода или полустепень исхода (или обе) некоторой вершины x в

    конце шага 2 равной нулю, то не существует никакого гамильтонова цикла. В

    этом случае вершина xj удаляется из множества S0 и в качестве другой

    вершины xj, позволяющей продолжить цепь S0, выбирается некоторая другая

    вершина из множества Гk’[e(S0)]. И так до тех пор, пока не будет исчерпано

    все множество Гk’[e(S0)] и придется прибегнуть к возвращению (т.е. e(S0)

    удаляется из S0 и заменяется другой вершиной и т.д.). Отметим, что операция

    возвращения предполагает хранение достаточной информации об удаленных дугах

    в шагах 1 и 2 на каждом этапе k, чтобы можно было по графу Gk+1

    восстановить граф Gk при любых k, если приходится прибегать к возвращению.

    Если (на некотором этапе) в конце шага 2 установлено, что только одна

    цепь проходит далее через все вершины, то в этом случае существование

    гамильтонова цикла может быть выявлено непосредственно. Если цикл при этом

    не найден (или если он найден, но надо найти все гамильтоновы циклы), то

    нужно прибегнуть к возвращению.

    Лучший вычислительный путь состоит в том, чтобы при каждой итерации

    шага 2 (за исключением последней) проверять отличие от нуля полустепеней

    захода и исхода всех вершин графа G’k. Поэтому как только одна из них

    станет равной нулю, сразу же применяется операция возвращения, и если

    найдена гамильтонова цепь, то получается и гамильтонов цикл без проверки

    существования дуги возврата.

    Если не возникает ни один из вышеупомянутых случаев, т.е. если (на

    некотором этапе k) в конце шага 2 остается более чем одна цепь и все

    полустепени являются ненулевыми, то нельзя еще сделать никаких выводов.

    Тогда вершина xj добавляется к S0 и выбирается другая вершина для

    дальнейшего продолжения цепи. Шаги 1, 2, 3 повторяются, начиная с нового

    редуцированного графа.

    §10. Сравнение методов поиска гамильтоновых циклов

    В этом параграфе сравниваются первоначальный вариант алгоритма

    Робертса и Флореса, его улучшенный вариант и мультицепной метод. Эти три

    метода мы будем сравнивать по необходимому времени вычислений для

    нахождения одного гамильтонова цикла, если таковой существует, или

    доказательства его отсутствия. Проверка была проведена на случайно

    выбранных графах, степени вершин которых лежат в предписанных границах.

    Всего было использовано около 200 графов, для которых приводятся средние

    результаты. Во всех графах оказались гамильтоновы циклы.

    Ниже на рисунке 1 показана зависимость требуемого алгоритмом Робертса

    и Флореса времени вычисления от числа вершин графа; степени вершин лежат в

    пределах 3 — 5. Ввиду сильных вариаций требуемого времени для графов

    одинаковых размеров приводятся три ломанные, характеризующие среднее,

    максимальное и минимальное время, полученное для различных графов с

    одинаковым числом вершин. Следует заметить, что на рисунке 1 применен

    полулогарифмический масштаб, что говорит об экспоненциальном характере

    зависимости. Формула, дающая приближенную зависимость времени T от числа

    вершин n графа со степенями вершин в пределах 3 — 5, такова:

    T = 0.85·10-4 · 100.155n (секунд на CDC6600).

    Улучшенный вариант алгоритма Робертса и Флореса не намного лучше

    первоначального алгоритма. Необходимое время вычисления в нем все еще

    зависит (более или менее) экспоненциально от n. Зависимость отношения

    времен вычисления при использовании этих двух алгоритмов для

    неориентированных графов со степенями вершин 3 — 5 приведена на рисунке 2.

    Из этого рисунка видно, что «улучшенный» вариант в действительности хуже

    для графов малых размеров, хотя для больших графов (с более чем 20

    вершинами) он позволяет сэкономить более 50% времени вычисления.

    По отношению к тому же вышеупомянутому множеству графов мультицепной

    алгоритм оказался очень эффективным. Это видно из рисунка 3, на котором

    показано необходимое для этого алгоритма время вычисления (здесь применен

    линейный масштаб). График показывает, что время растет очень медленно в

    зависимости от числа вершин и поэтому алгоритм применим для очень бльших

    графов.

    Другим преимуществом этого метода является очень слабая вариация

    времени для различных графов одинакового размера, и поэтому можно оценит с

    разумной степенью доверительности время вычисления, необходимое для

    различных задач.

    Кроме того, эксперименты показывают, что для графов, степени вершин

    которых лежат в вышеприведенных пределах 3 — 5, метод по существу не

    чувствителен к степеням вершин. Вычислительные результаты, показанные на

    рисунках 1-3, относятся к поиску одного гамильтонова цикла в графе.

    Небезынтересно сказать несколько слов о вычислениях с тремя

    алгоритмами, когда искались все гамильтоновы циклы. Так, для

    неориентированного графа с 20 вершинами со степенями вершин 3 — 5,

    потребовалось 2 сек, чтобы найти все гамильтоновы циклы, следуя [pic]

    Рис.1 Вычислительная реализация алгоритма Робертса и Флореса

    [pic]

    Рис.2 Реализация улучшенного алгоритма Робертса и Флореса

    Время вычисления: T0-основной алгоритм, T1-улучшенный алгоритм

    [pic]

    алгоритму Робертса и Флореса (этих циклов оказалось 18). Улучшенный вариант

    того же алгоритма потребовал 1.2 сек, а мультицепной алгоритм — 0.07 сек.

    Вычисления проводились на ЭВМ CDC6600.

    Глава 3. Задача коммивояжера

    Задача коммивояжера (в дальнейшем сокращённо - ЗК) является одной из

    знаменитых задач теории комбинаторики. Она была поставлена в 1934 году, и

    об неё, как об Великую теорему Ферма обламывали зубы лучшие математики. В

    своей области (оптимизации дискретных задач) ЗК служит своеобразным

    полигоном, на котором испытываются всё новые методы. Ниже будет показано,

    что решение ЗК методом полного перебора оказывается практически

    неосуществимым даже для сравнительно небольших задач. Более того, известно,

    что ЗК принадлежит к числу NP-полных задач.

    §1. Общее описание

    Постановка задачи следующая.

    Коммивояжер (бродячий торговец) должен выйти из первого города,

    посетить по одному разу в неизвестном порядке города 1,2,3..n и вернуться в

    первый город. Расстояния между городами известны. В каком порядке следует

    обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

    Чтобы привести задачу к научному виду, введём некоторые термины. Итак,

    города перенумерованы числами j(Т=(1,2,…,n). Тур коммивояжера может быть

    описан циклической перестановкой t=(j1,…,jn, j1), причём все j1,…,jn –

    разные номера; повторяющийся в начале и в конце j1, показывает, что

    перестановка зациклена. Расстояния между парами вершин Сij образуют матрицу

    С. Далее введем n2 альтернативных переменных xij, принимающих значение 0,

    если переход из i-го пункта в j-ый не входит в маршрут и 1 в противном

    случае. Условия прибытия в каждый пункт и выхода из каждого пункта только

    по одному разу выражаются равенствами (1) и (2).

    [pic] (1)

    [pic] (2)

    Для обеспечения непрерывности маршрута вводятся дополнительно n

    переменных [pic] и n2 дополнительных ограничений (3).

    [pic] (3)

    Задача состоит в том, чтобы найти такой тур t, чтобы минимизировать

    суммарную протяженность маршрута F, которая запишется в следующем виде:

    [pic] (4)

    Относительно математической формулировки ЗК уместно сделать два

    замечания. Первое, в постановке Сij означали расстояния, поэтому должны

    выполняться следующие условия:

    . неотрицательными, т.е. для всех j(Т:

    Cij ( 0;

    Cjj = ? (5)

    (последнее равенство означает запрет на петли в туре),

    . симметричными, т.е. для всех i, j:

    Сij = Сji (6)

    . удовлетворять неравенству треугольника, т.е. для всех:

    Cij + Cjk ( Cik (7)

    В математической постановке говорится о произвольной матрице. Сделано

    это потому, что имеется много прикладных задач, которые описываются

    основной моделью, но всем условиям (5)-(7) не удовлетворяют. Особенно часто

    Страницы: 1, 2, 3, 4


    Приглашения

    09.12.2013 - 16.12.2013

    Международный конкурс хореографического искусства в рамках Международного фестиваля искусств «РОЖДЕСТВЕНСКАЯ АНДОРРА»

    09.12.2013 - 16.12.2013

    Международный конкурс хорового искусства в АНДОРРЕ «РОЖДЕСТВЕНСКАЯ АНДОРРА»




    Copyright © 2012 г.
    При использовании материалов - ссылка на сайт обязательна.