Пример.
На рис.2 показаны граф и дерево, иллюстрирующее процесс нахождения всех гамильтоновых циклов с помощью алгоритма с возвратом.
Гамильтоновы циклы – 123541, 125341, 143521, 145321.
Напомним, что перестановкой n-элементного множества X называется упорядоченный набор длины n, составленный из попарно различных элементов множества X. Опишем некоторые методы генерирования последовательности всех n! перестановок n-элементного множества. Не нарушая общности будем рассматривать не исходное множество Х, а множество А={1,2,…n} – множество индексов элементов, т.к. между множеством элементов из Х и множеством индексов из А существует взаимно однозначное соответствие, которое задается в виде: xi « i.
Будем предполагать, что элементы множества запоминаются в виде элементов массива Р[1],…, Р[n]. Во всех методах элементарной операцией, которая применяется к массиву Р, является поэлементная транспозиция, т.е. обмен значениями переменных Р[i] и Р[j], где 1£i, j£n. Эту операцию будем обозначать Р[i] :=: Р[j]. Очевидно, что она эквивалентна последовательности команд: а := Р[i] ; Р[i] := Р[j]; Р[j] := а, где а – некоторая вспомогательная переменная.
Генерирование всех перестановок заданного множества в лексикографическом порядке
Данный метод легче всего понять, если в качестве переставляемых элементов взять числа 1,…,n. На множестве всех перестановок определим лексикографический порядок:
<x1,x2,…xn> < <y1,y2,…,yn> Û существует k³1, такое что xk < yk и xp= yp для каждого p < k.
Заметим, что если вместо чисел 1,2,…, n взять буквы а,б,…,р с естественным порядком а<б<в<…<р, то лексикографический порядок определяет стандартную последовательность, в которой слова длины n появляются в словаре.
Для примера приведем перестановки множества X = {1,2,3} в лексикографическом порядке:
123, 132, 213, 231, 312, 321.
Начиная с перестановки (1,2,…,n), переход от текущей перестановки P=(p1,p2,…,pn) к перестановке, следующей за текущей в смысле лексикографического порядка, осуществляется последовательным выполнением следующих действий:
1) просмотр Р справа налево в поисках самой правой позиции k, в которой pk<pk+1 (если такой позиции k нет, то текущая перестановка является последней и следует закончить генерацию);
2) просмотр P от pk слева направо в поисках наименьшего из таких элементов pm, что k<m и pk<pm; транспозиция элементов pk и pm и обращение отрезка pk+1,…, pn путем транспозиции симметрично расположенных элементов (заметим, что элементы обращаемого отрезка расположены в порядке убывания).
Например, для п=8 и Р=(2,6,5,8,7,4,3,1) имеем pk =5 и pm=7, результат транспозиции pk и pm - (2,6,7,8,5,4,3,1), результат обращения отрезка pk+1,…, pn переводит Р в перестановку (2,6,7,1,3,4,5,8), которая следует за Р в лексикографическом порядке.
Рекурсивный алгоритм генерирования всех перестановок заданного множества в лексикографическом порядке
Рассмотрим рекурсивный алгоритм генерирования перестановок в лексикографическом порядке. Заметим, что последовательность перестановок множества {1,2,…, n} в этом случае имеет следующие свойства, вытекающие непосредственно из определения:
В качестве примера рассмотрим генерирование всех перестановок для п=4. Таких перестановок будет 4!=24. Эти перестановки можно разбить на четыре блока, каждый из которых содержит 3!=6 перестановок, по значению элемента в первой позиции. В первом блоке на первом месте стоит 1, во втором – 2, в третьем – 3, в четвертом – 4. Далее рассмотрим блок с 1 на первом месте, для остальных аналогично. Для генерации всех перестановок оставшегося множества Х={2,3,4} выполним следующее: разобъем все перестановки на 3 блока по 2!=2 перестановки, соответствующих возрастающим значениям элемента в первой позиции, в первом блоке – 2, во втором – 3, в третьем – 4. Далее в каждом блоке генерируем все перестановки из оставшихся двух элементов в лексикографическом порядке (в первой из перестановок последние два элемента расположены в порядке возрастания). В результате получаем:
| 1 | 2 | 3 | 4 | 2 | 1 | 3 | 4 | 3 | 1 | 2 | 4 | 4 | 1 | 2 | 3 |
| 1 | 2 | 4 | 3 | 2 | 1 | 4 | 3 | 3 | 1 | 4 | 2 | 4 | 1 | 3 | 2 |
| 1 | 3 | 2 | 4 | 2 | 3 | 1 | 4 | 3 | 2 | 1 | 4 | 4 | 2 | 1 | 3 |
| 1 | 3 | 4 | 2 | 2 | 3 | 4 | 1 | 3 | 2 | 4 | 1 | 4 | 2 | 3 | 1 |
| 1 | 4 | 2 | 3 | 2 | 4 | 1 | 3 | 3 | 4 | 1 | 2 | 4 | 3 | 1 | 2 |
| 1 | 4 | 3 | 2 | 2 | 4 | 3 | 1 | 3 | 4 | 2 | 1 | 4 | 3 | 2 | 1 |
Генерирование всех перестановок заданного множества в антилексикографическом порядке
Антилексикографический порядок (обозначим <¢ ) определяется следующим образом:
<x1,x2,…xn> <¢ <y1,y2,…,y n> Û существует такое k£n, что xk > yk и xp = yp для каждого p > k..
Для примера приведем перестановки множества X = {1,2,3} в антилексикографическом порядке: 123, 213, 132, 312, 231, 321.
Алгоритм генерирования перестановок в антилексикографическом порядке сформулировать удобнее. Заметим, что последовательность перестановок множества {1,2,…, n} в этом случае имеет следующие свойства, вытекающие непосредственно из определения:
1) в первой перестановке элементы идут в растущей последовательности, в последней – в убывающей; другими словами, последняя перестановка – обращение первой,
2) последовательность всех перестановок можно разделить на n блоков длины (n-1)!, соответствующих убывающим значениям элемента в последней позиции. Первые n-1 позиций блока, содержащего элемент р в последней позиции, определяют последовательность перестановок множества {1,2,…, n}\{р} в антилексикографическом порядке.
Сгенерируем в антилексикографическом порядке все перестановки для n=4, получим
| 1 | 2 | 3 | 4 | 1 | 2 | 4 | 3 | 1 | 3 | 4 | 2 | 2 | 3 | 4 | 1 |
| 2 | 1 | 3 | 4 | 2 | 1 | 4 | 3 | 3 | 1 | 4 | 2 | 3 | 2 | 4 | 1 |
| 1 | 3 | 2 | 4 | 1 | 4 | 2 | 3 | 1 | 4 | 3 | 2 | 4 | 2 | 3 | 1 |
| 3 | 1 | 2 | 4 | 4 | 1 | 2 | 3 | 4 | 1 | 3 | 2 | 2 | 4 | 3 | 1 |
| 2 | 3 | 1 | 4 | 2 | 4 | 1 | 3 | 3 | 4 | 1 | 2 | 3 | 4 | 2 | 1 |
| 3 | 2 | 1 | 4 | 4 | 2 | 1 | 3 | 4 | 3 | 1 | 2 | 4 | 3 | 2 | 1 |
1.4. Построение остова минимального веса
Граф G называется деревом, если он является связным и не имеет циклов.
Остовом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.
Остовное дерево связного нагруженного графа G с минимальной суммой длин содержащихся в нем ребер, будем называть остовом минимального веса или минимальным остовным деревом (МОД).
Рассмотрим граф G = (V,X), где V={v1,…,vn}.
А л г о р и т м К р а с к а л а