Предыдущая страница реферата | 3  4  5  6  7  8  9  10  11  12  13 | Следующая страница реферата

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]XS, что x[pic]Г(xr) и Г-1(x)[pic] S, то, добавляя к S любую вершину x*, отличную от x, мы не сможем в последующем достигнуть вершины x ни из какой конечной вершины построенной цепи, и, значит, эта цепь не сможет привести нас к построению гамильтонова цикла. Таким образом, в этом случае x является единственной вершиной, которую можно добавить к S для продолжения цепи.
Если существует такая вершина x[pic]XS, что 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, если приходится прибегать к возвращению.

Рекомендуем скачать другие рефераты по теме: доклад на тему культура, реферат н.





Предыдущая страница реферата | 3  4  5  6  7  8  9  10  11  12  13 | Следующая страница реферата