9.3. Поиск в сети

П усть задана ориентированная сеть (см. рис.), где P –множество вершин, R – множество дуг, d – функция, определенная на множестве R со значениями во множестве действующих чисел. Иногда интерпретируют как длину дуги . В алгоритмах оптимизации на сетях во внутренних циклах многократно приходится решать две задачи.

1). Для фиксированной вершины определить все дуги сети вида – выходы из x.

	Дуги		d
	x	y
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	7 3 5 9 4 8 3 7 1 1 6 1 6 6 6	8 4 9 5 5 9 6 6 3 7 4 6 8 5 9	3 4 1 3 2 1 1 1 3 2 2 5 3 5 2

2). Для фиксированной вершины определить все дуги сети вида – входы в x.

В больших сетях алгоритмы с простым перебором всех элементов из R, для поиска дуг, выходящих или входящих из/в x, естественно, не эффективны. Рассмотрим один из способов ускорения поиска в сети. Будем считать, что сеть представлена в оперативной памяти в виде массива дуг , как это показано в таблице, и что записями являются отдельные строки.

П усть вначале решается первая задача. Отсортируем -файл по ключу x. Ясно, что среднее время нахождения всех дуг даже при последовательном поиске сократится примерно наполовину. Кроме того, становится возможна организация более эффективного бинарного поиска. Однако рассмотрим иной подход. Пусть имеется некоторый вспомогательный массив A, в позициях x которого записан адрес расположения в -файле начальной дуги вида . В этом случае поиск всех дуг сводится к выборке адреса . Если, например, требуется найти в -файле все дуги вида , то получив , сразу попадаем на требуемое подмножество выходов из вершины 6 (рис. справа) в массиве. Описанный способ решения задачи предполагает, что – это натуральные числа. При этом для минимизации объема дополнительной памяти, т.е. величины , желательно иметь последовательную нумерацию вершин, начиная с 1. Символ  указывает на отсутствие вершины с данным номером.

П ерейдем ко второй задаче. Если отсортировать -файл по y, то аналогично строится простой механизм поиска входов в вершины. Однако при этом теряется возможность эффективно решать первую задачу. Вводим в рассмотрение два вспомогательных одномерных массива и . Пусть устроен так же, как и . В позиции x массива указывается адрес  первой от начала строки в -файле с дугой . Далее, если по некоторому адресу  записана дуга , то в указывается адрес в -файле следующей такой дуги. Символ  в массиве используется для указания отсутствия входов в вершину x, а в массиве – как метка завершения соответствующего множества входов. При такой организации и поиск всех входов в x сводится к выборкам сначала адреса , а затем последовательных адресов из массива C (рис. слева).

Формирование массивов B и C приводит к адресному кодированию -файла, т.е. проводится адресная сортировка -файле по y. Для рассмотренной ранее схемы поиска выходов дуг из вершин можно было бы отказаться от начальной сортировки -файла по x, заменив ее подобным адресным кодированием. Но при этом пришлось бы добавить еще один вспомогательный массив, устроенный аналогично C и используемый для хранения последующих адресов. Массивы A, B и C называются справочниками, а их совокупность – справочной -файла. Таким образом, чтобы адресовать записи -файла, необходимо построить справочники: 1) A, 2) B и C, 3) A, B и C. Сделать это несложно, при этом после сортировки все организуется за один просмотр -файла. Ниже приводятся три программы, формирующие три указанные типы справочной -файла.

С

Dim S() As Integer, A() As Integer: Const n As Integer = 15, m As Integer = 9

Sub Справочник_A() 'Отладочный вариант

Dim i As Integer, var As String

ReDim S(1 To n, 2), A(1 To m)

S(1,0)=1: S(2,0)=1: S(3,0)=1: S(4,0)=3: S(5,0)=3: S(6,0)=4: S(7,0)=5: S(8,0)=6

S(9,0)=6: S(10,0)=6: S(11,0)=6: S(12,0)=7: S(13,0)=7: S(14,0)=8: S(15,0)=9

For i = n To 1 Step -1: A(S(i,0)) = i: Next i

var = "Справочник A:": For i = 1 To m: var = var & " " & Str(A(i)): Next i: MsgBox var

End Sub

правочник A. Адреса выходов из вершин.

С

Dim S() As Integer, B() As Integer, C() As Integer: Const n As Integer = 15, m As Integer = 9

Sub Справочники_B_C() 'Отладочный вариант

Dim i As Integer, var As String: ReDim S(1 To n, 2), B(1 To m), C(1 To n)

S(1,0)=1: S(2,0)=1: S(3,0)=1: S(4,0)=3: S(5,0)=3: S(6,0)=4: S(7,0)=5: S(8,0)=6

S(9,0)=6: S(10,0)=6: S(11,0)=6: S(12,0)=7: S(13,0)=7: S(14,0)=8: S(15,0)=9

S(1,1)=3: S(2,1)=7: S(3,1)=6: S(4,1)=4: S(5,1)=6: S(6,1)=5: S(7,1)=9: S(8,1)=4

S(9,1)=8: S(10,1)=5: S(11,1)=9: S(12,1)=8: S(13,1)=6: S(14,1)=9: S(15,1)=5

For i = n To 1 Step -1: C(i) = B(S(i,1)): B(S(i,1)) = i: Next i

var = "Справочник B:": For i = 1 To m: var = var & " " & Str(B(i)): Next i: MsgBox var

var = "Справочник C:": For i = 1 To n: var = var & " " & Str(C(i)): Next i: MsgBox var

End Sub

правочники B и C. Адреса входов в вершины.

Справочники A, B и C. Адреса входов и выходов в/из вершин.

9

Dim S() As Integer, A() As Integer, B() As Integer, C() As Integer

Const n As Integer = 15, m As Integer = 9

Sub Справочники_A_B_C() 'Отладочный вариант

Dim i As Integer, var As String

ReDim S(1 To n, 2), A(1 To m), B(1 To m), C(1 To n)

S(1,0)=1: S(2,0)=1: S(3,0)=1: S(4,0)=3: S(5,0)=3: S(6,0)=4: S(7,0)=5: S(8,0)=6

S(9,0)=6: S(10,0)=6: S(11,0)=6: S(12,0)=7: S(13,0)=7: S(14,0)=8: S(15,0)=9

S(1,1)=3: S(2,1)=7: S(3,1)=6: S(4,1)=4: S(5,1)=6: S(6,1)=5: S(7,1)=9: S(8,1)=4

S(9,1)=8: S(10,1)=5: S(11,1)=9: S(12,1)=8: S(13,1)=6: S(14,1)=9: S(15,1)=5

For i = n To 1 Step -1: C(i) = B(S(i,1)): A(S(i,0)) = i: B(S(i,1)) = i: Next i

var = "Справочник A:": For i = 1 To m: var = var & " " & Str(A(i)): Next i: MsgBox var

var = "Справочник B:": For i = 1 To m: var = var & " " & Str(B(i)): Next i: MsgBox var

var = "Справочник C:": For i = 1 To n: var = var & " " & Str(C(i)): Next i: MsgBox var

End Sub

.4. Генератор перестановок

Иногда задачу приходиться решать полным перебором всех вариантов, если нет иного пути. В подобных случаях полезен алгоритм получения всех n! перестановок из множества , где – попарно различные действительные числа. Пошаговый алгоритм выглядит так.

Шаг 1. Отсортируем последовательность в порядке убывания и полученную перестановку считаем начальной.

Шаг 2. Находим наименьший индекс , при котором .

Шаг 3. Находим наименьший индекс , при котором .

Шаг 4. Обмениваем значениями и .

Шаг 5. Обмениваем значениями компоненты в парах , где .

Шаг 6. Фиксируем очередную перестановку и если их количество меньше n!, то переходим к шагу 2. В противном случае останавливаемся.

Покажем, что, используя приведенный алгоритм, получим все n! различных перестановок. Не ограничивая общность, полагаем, что последовательность состоит из натуральных чисел 1, 2, , n. Зафиксируем и рассмотрим t-ричную систему счисления с цифрами 0, 1, 2, , n, , t-1. Во множестве B n-значных t-ричных чисел выделим подмножество B₀ чисел, у которых цифры попарно различны и являются элементами последовательности S. Перестановки из последовательности S и элементы подмножества B₀ можно поставить во взаимно однозначное соответствие по правилу

.

Следовательно, проблема получения всех перестановок из последовательности S является задачей выделения во множестве B подмножества B₀. Пусть элементы подмножества B₀ выписаны в порядке возрастания . Тогда шаг 1 алгоритма определяет первоначальную перестановку , соответствующую числу . Если уже сгенерирована перестановка , то совокупность шагов 3-6 формирует перестановку, соответствующую числу . Этим доказывается, что будут получены все n! перестановок из последовательности S.

Функция n! растет очень быстро. Например, число различных списков из десяти различных фамилий равно 3628800, поэтому практическое использование алгоритма перестановок весьма ограничено. Ниже приводится программа генератора перестановок.

П

Dim S() As Integer

Const n As Integer = 4

Sub Генератор_перестановок() 'Отладочный вариант

Dim i As Integer, j As Integer, z As Integer, y As Integer, l As Integer, var As String: ReDim S(1 To n)

For i = 1 To n: S(i) = n + 1 - i: Next i: z = 1: For i = 1 To n: z = z * i: Next i: Фиксация(1)

For y = 2 To z

i = 2: j = 1:While S(i-1)<=S(i): i = i + 1: Wend: While S(j)<=S(i): j = j + 1: Wend: Swap S(i), S(j)

If i <> 2 Then

For l = 1 To (i-1)/2: Swap S(l), S(i-l): Next l

End If

Фиксация(y)

Next y

End Sub

Sub Фиксация(k As Integer)

Dim i As Integer, var As String

var = "Перестановка " & Str(k) & ":": For i = 1 To n: var = var & " " & Str(S(i)): Next i: MsgBox var

End Sub

Sub Swap(ByRef x As Integer, ByRef y As Integer) 'Обмен значениями

Dim m As Integer

m = x: x = y: y = m

End Sub

родемонстрируем работу генератора перестановок на типичной задаче коммивояжера, которая была рассмотрена в алгоритме ветвей и границ. Вновь приведем ее формулировку. Коммивояжер (агент по сбыту), отправляясь из своего города, должен кратчайшим маршрутом посетить по одному разу n-1 заданных городов и вернуться назад. Естественно, для больших n необходимо использовать эффективный метод ветвей и границ. Для небольших n будем решать эту задачу перебором всех возможных замкнутых маршрутов, проходящих по одному разу через каждый из городов. Будем называть такие маршруты допустимыми. Пусть города пронумерованы числами 1, 2, , n, расстояния между ними равны , причем значения и могут не совпадать. При отсутствии маршрута (дороги) между пунктами i и j можно считать, что . Всякая перестановка из элементов 1, 2, , n определяет допустимый маршрут: Тогда для решения задачи коммивояжера, перебирая все возможные перестановки , достаточно вычислить длины соответствующих маршрутов и запомнить лучшие из них. Причем учитываются только те перестановки, в которых , ввиду замкнутости маршрутов. Таким образом, для n городов просматриваются и анализируются (n-1) маршрутов. Ниже приведена программа задачи коммивояжера.

Dim S() As Integer, Q() As Integer, P() As Integer

Const n As Integer = 7 'Количество пунктов

Sub Генератор_перестановок() 'Отладочный вариант

Dim i As Integer, j As Integer, z As Integer, y As Integer, l As Integer, b As Integer, d As Integer, h As Integer

ReDim S(1 To n, 1 To n), Q(1 To 30, 1 To n), P(1 To n)

S(1,1)=0: S(1,2)=5: S(1,3)=9: S(1,4)=6: S(1,5)=3: S(1,6)=5: S(1,7)=9: S(2,1)=8: S(2,2)=0: S(2,3)=8: S(2,4)=8

S(2,5)=5: S(2,6)=9: S(2,7)=2: S(3,1)=6: S(3,2)=9: S(3,3)=0: S(3,4)=1: S(3,5)=6: S(3,6)=7: S(3,7)=3

S(4,1)=7: S(4,2)=11: S(4,3)=4: S(4,4)=0: S(4,5)=4: S(4,6)=2: S(4,7)=9: S(5,1)=4: S(5,2)=6: S(5,3)=3: S(5,4)=2

S(5,5)=0: S(5,6)=2: S(5,7)=8: S(6,1)=5: S(6,2)=2: S(6,3)=2: S(6,4)=8: S(6,5)=4: S(6,6)=0: S(6,7)=3

S(7,1)=8: S(7,2)=1: S(7,3)=3: S(7,4)=16: S(7,5)=5: S(7,6)=3: S(7,7)=0: b = 1000

For i = 1 To n: P(i) = n + 1 - i: Next i: z = 1: For i = 1 To n - 1: z = z * i: Next i

For y = 1 To z

If y <> 1 Then

i = 2: j = 1: While P(i-1)<=P(i): i = i + 1: Wend: While P(j)<=P(i): j = j + 1: Wend: Swap P(i), P(j)

If i <> 2 Then

For l = 1 To (i-1)/2: Swap P(l), P(i-l): Next l

End If

End If

d = S(P(n),P(1)): For l = 1 To n-1: d = d +S( P(l), P(l+1)): Next l

If d <= b Then

If d < b Then h = 1: b = d: For l = 1 To n: Q(h,l) = P(l): Next l: h = h + 1: Фиксация h b

End If

Next y

End Sub

Sub Фиксация(k As Integer, d As Integer)

Dim i As Integer, var As String

var = "Маршрут " & Str(k) & ":": For i = 1 To n: var = var & " " & Str(P(i)): Next i

var = var & ". Длина: " & Str(d): MsgBox var

End Sub

Sub Swap(ByRef x As Integer, ByRef y As Integer) 'Обмен значениями

Dim m As Integer

m = x: x = y: y = m

End Sub