Математическая логика и теория алгоритмов. Стенюшкина В.А. - 81 стр.

роим также как и А(х). В позиции х величина В(х) есть адрес α первый от нача-
ла строки в µ с дугой (у, х). Если перейти на этот адрес α в µ, то затем можно
воспользоваться массивом С(х), в котором по адресу α хранится адрес следую-
щей дуги с тем же х. Символ ∅ в В(х) используется для указания отсутствия
входов в х, а в С(х) – для отсутствия очередного входа в х (то есть как метка за-
вершения соответствующего подмассива входов). Итак, проблема поиска всех
входов в х решается выборкой сначала адреса В(х) и затем последовательных
адресов из С. Формирование массивов В и С приводит, можно сказать, к адрес-
ному кодированию µ, или осуществляется адресная сортировка µ по у.

       4.4 Алгоритмы перебора

                             4.4.1 Полный перебор

       Рассмотрим задачу генерации перестановок (ГП).
       Постановка задачи Дано множество n попарно различных действитель-
ных чисел: S = {a1, …, an}. Требуется перечислить все N = n! перестановок эле-
ментов ак, к = 1…n этого массива.
       Алгоритм ГП
       Шаг 1 Производится сортировка массива по убыванию его элементов.
Полученная перестановка считается начальной и выводится. Далее идет работа
с индексами элементов i ∈ {1… n}.
       Шаг 2 Находится наименьший индекс i∈{2… n}, для которого аi - 1 > аi.
       Шаг 3 Находится наименьший индекс j∈{1…(n - 1)}, для которого аj > аi.
       Шаг 4 Обмен значениями аi и аj.
       Шаг 5 Обмениваем значениями компоненты в парах: (а1,аi - 1),…,(ак,аi - к ),
к = [(i - 1) / 2].
       Шаг 6 Вывод полученной перестановки. Если число выведенных пере-
становок < N, переход на шаг 2, в противном случае задача решена.
       Алгоритм требует осторожности при работе с большими n, так как N = n!
растет очень быстро. Например, 10! = 3628800.
       Пример – Для начальной перестановки (3, 2, 1) следующими выводами
перестановками будут: (2,3,1), (3,1,2), (1,3,2), (2,1,3), (1,2,3). (Имеется множест-
во других алгоритмов).



                          4.4.2 Метод ветвей и границ

     Рассмотрим задачу о коммивояжере.
     Постановка задачи Дано множество пунктов S = {1 … n} и сеть сообще-
ний между ними. Конкретный пример дан рисунком 4.4 (граф) и матрицей A.
Элемент aij, i,j∈ {1…n}, матрицы А показывает некоторую характеристику дуги
(стоимость проезда) из пункта i (номер строки) в пункт j (номер столбца). Тре-