Переборные алгоритмы. Перебор вариантов, Backtracking

Перебор

Очень часто можно слышать фразу «ЭВМ проанализировала огромное количество вариантов и выдала наилучший» [4]. Так обычно говорят о тех задачах, которые требуют при поиске решения перебора вариантов.

Простейшие задачи на перебор – это задачи на поиск решения в одномерном массиве (например, найти элемент с заданным свойством). Сложность таких задач пропорциональна количеству элементов в массиве $N$.
Следующие задачи на перебор – поиск пар элементов либо из одного массива, либо из двух разных массивов. При решении таких задач, как правило, используется вложенный цикл, то есть их сложность пропорциональна $N^2$.
Далее идет перебор троек элементов. Рассмотрим, например, следующую задачу.

Пример 6.1. На плоскости разбросаны $N$ точек с координатами ($x^1$, $y^1$), ($x^2$, $y^2$), …,
($x^N$, $y^N$). Найти тройку точек, которые образуют треугольник с максимальной площадью.

Ясно, что при решении этой задачи необходимо использовать три вложенных цикла, таким образом, задача решается за $N^3$ шагов.

Для задания координат точек используем датчик случайных чисел.

Программа (QBasic):

INPUT "введите количество точек $N$>2 ", $N$

DIM x(1 TO n), y(1 TO n)

SCREEN 12

RANDOMIZE TIMER

FOR i = 1 TO $N$ 'Задание экранных координат точек случайным образом

x(i) = INT(RND * 640)

y(i) = INT(RND * 480)

CIRCLE (x(i), y(i)), 2 'Рисуем “точки”

NEXT i

‘Начинаем перебор

FOR i = 1 TO n

FOR j = 1 TO n

FOR k = 1 TO n

a = SQR((x(i) -x(j)) ^ 2 + (y(i) - y(j)) ^ 2) 'Длины сторон

b = SQR((x(i) -x(k)) ^ 2 + (y(i) - y(k)) ^ 2)

c = SQR((x(k) - x(j)) ^ 2 + (y(k) - y(j)) ^ 2)

p = (a + b + c) / 2 'Полупериметр

s = SQR(p * (p - a) * (p - b) * (p - c)) 'Формула Герона

IF s > smax THEN smax = s: im = i: jm = j: km = k

NEXT k, j, i

'Рисуем треугольник с максимальной площадью

LINE (x(im), y(im))-(x(jm), y(jm)), 2

LINE (x(im), y(im))-(x(km), y(km)), 2

LINE (x(km), y(km))-(x(jm), y(jm)), 2

PRINT "Площадь = "; smax

PRINT "Номера точек "; im; jm; km

Однако этот перебор можно существенно сократить, если не повторять лишних проходов по циклам.

FOR i=1 TO n-2

FOR j=i+1 TO n-1

FOR k=j+1 TO n

………………………..

NEXT k, j, i

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

2.3.1. Перебор с отсечениями

Пример 6.2. Решить уравнение в целых числах: $x^1$⁴ + $x^2$⁴ + … + x₁₅⁴ = 2000

Программа (QBasic):

DEFINT A-Z

DIM SHARED p4(1 TO 6) ‘массив четвертых степеней

DIM SHARED x(1 TO 15) ‘значения переменных $x^1$, …, $x^15$

DIM SHARED $N$‘номер переменной, значения которой перебираются в процедуре Find

FOR i = 1 TO 6: p4(i) = i ^ 4: NEXT ‘высчитываем один раз четвертые степени

PRINT "Поиск решения:" ‘запускаем поиск решения

CALL Find(2000, 6) ‘набираем сумму 2000, начиная с x1=6

‘-------------------------- рекурсивная процедура ---------------------------------------------

SUB Find (sum, start) ‘основная процедура поиска решения

‘sum – сумма, которую осталось набрать

‘start – значение, с которого начинать перебор

IF $N$ = 15 THEN ‘если значения всех 15 переменных заданы, то

IF sum = 0 THEN ‘если набрана нужная сумма,

FOR i = 1 TO 15: PRINT x(i); : NEXT ‘печатаем решение

ELSE

EXIT SUB ‘иначе возвращаемся к предыдущему шагу

END IF

IF sum > 0 THEN ‘если сумма 4x степеней предыдущих

‘переменных не превосходит 2000,

$N$ = $N$ + 1

FOR i = start TO 1 STEP –1 ‘перебираем значения очередной переменной

x($N$) = I ‘фиксируем значение $N$-ой переменной и

CALL Find(sum - p4(i), i) ‘переходим к перебору значений $N$+1-ой

n = n - 1

END IF

END SUB

Приведенная программа ищет решения уравнения $x^1$⁴ + $x^2$⁴ + … + $x^15$⁴= 2000 в натуральных числах методом перебора. Перебор является, пожалуй, одним из самых простых (по реализации), но, вместе с тем, самым трудоемким (по времени выполнения) из всех алгоритмов, поэтому при решении каждой конкретной задачи перебором возникает другая задача – сократить и оптимизировать перебор, иными словами, максимально уменьшить время, затрачиваемое компьютером на поиск решения.

Познакомимся с некоторыми возможными приемами сокращения перебора на данной конкретной задаче.

1) В первую очередь, надо правильно выбрать границы значений перебираемых величин. По условию задачи все переменные принимают натуральные значения, но ведь натуральных чисел бесконечно много! Однако, в данном примере совершенно очевидно, что, если решение уравнения существует, то все $x^1$, …, x₁₅лежат в промежутке от 1 до 6, поскольку натуральные числа, большие 6, в четвертой степени дают значение уже превосходящее 2000 (7⁴ = 2401 > 2000). Итак, в алгоритме все переменные перебираются в пределах от 1 до 6, что видно из вызова процедуры Find (2000, 6).

2) Далее, важным моментом при оптимизации является отсечение заведомо неверных ветвей перебора. Например, в данном примере, не имеет смысла продолжать поиск, если на некотором шаге сумма $x^1$⁴ + … + x_n⁴ уже превысила 2000. В приведенной программе это условие проверяется в строке if sum>0 then, т.е. дальнейший перебор осуществляется лишь в том случае, когда разность 2000 и ранее полученной суммы $x^1$⁴ + … + x_n⁴ положительна.

3) Следует избегать многократного выполнения одних и тех же операций в циклах и рекурсивных процедурах, если данные, используемые в этих циклах, могут быть подготовлены заранее. Так, в приведенном примере значения четвертых степеней чисел 1, 2, …, 6 вычислены один раз и занесены в массив констант: p4 = (1, 16, 81, 256, 625, 1296). Подобный прием часто помогает избавиться от лишних вычислений, например, в алгоритмах, работающих с простыми числами, полезно бывает включить заранее найденные простые числа в текст программы, так же, в виде массива констант.

4) Кроме того, можно существенно ускорить перебор, если не рассматривать варианты, аналогичные (либо похожие) ранее рассмотренным. Так, в данной задаче решения уравнения определены с точностью до перестановки слагаемых, т.е., если найдено одно решение, то любая перестановка переменных в нем тоже будет являться решением. Поэтому, чтобы сократить поиск, не перебирая варианты, отличающиеся только перестановкой слагаемых, в процедуру Find был введен дополнительный параметр start – максимальное значение, которое может принимать очередная ($N$-ая) переменная. Благодаря этому гарантируется, что алгоритм будет рассматривать только те значения переменных, при которых $x^1$ ³ $x^2$ ³ … ³ $x^15$.

5) Наконец, если задача предполагает поиск какого-либо одного решения, а не всех, можно добиться более быстрого получения результата путем выбора хорошего начального приближения, либо перебором с предпочтением (так называемыми эвристическими методами). Эти методы различны для каждого конкретного случая, но, как правило, заключаются в том или ином способе реализации «жадного» алгоритма. В указанной программе эвристика заключается в том, что перебор осуществляется от большего значения к меньшему, а не наоборот: for i=start to 1 step -1. Интуитивно понятно, что, начиная перебор с больших значений переменных (6, 5, 4), мы быстрее «доберемся» до решения нежели, чем «пробуя» меньшие значения.

Пример 6.3. Найти все решения уравнения в целых числах
МУХА+МУХА+МУХА=СЛОН

Используем факт, что C £ 9 и число не начинается с 0, тогда 1 £ M £ 3. Если М = 3, то У £ 2 (иначе имели бы справа от знака равенства четырехзначное число). Следовательно, число МУХА возможно из диапазона [1023, 3210]. Начинаем перебор.

Программа (QBasic):

DIM SHARED $N$(1 TO 4) 'цифры для слова "МУХА"

CLS

$N$(1) = 1: $N$(2) = 0: $N$(3) = 2: $N$(4) = 3 'начальный набор цифр слова "МУХА"

Add1

i = Test% 'число, соответствующее набору цифр слова "МУХА"

LOOP UNTIL i >= 3210 'максимально возможный набор

SUB Add1 'увеличить число на единицу (поразрядное сложение)

n(4) = n(4) + 1

FOR i = 4 TO 2 STEP -1

IF n(i) = 10 THEN

n(i) = 0

n(i - 1) = n(i - 1) + 1

ELSE

EXIT SUB

END IF

END SUB

FUNCTION Test%

DIM L(1 TO 4)

Number = n(1) * 1000 + n(2) * 100 + n(3) * 10 + n(4)

Test% = Number

k = Number 'число соответствует слову "МУХА"

Number = Number * 3 '

FOR i = 4 TO 1 STEP -1

L(i) = Number MOD 10 'цифры соответствуют слову "СЛОН"

Number = Number \ 10

FOR i = 1 TO 3 'проверка: разным буквам - разные цифры

FOR j = i + 1 TO 4

IF (L(i) = L(j)) OR (n(i) = n(j)) THEN EXIT FUNCTION

NEXT j, i

FOR i = 1 TO 4

FOR j = 1 TO 4

IF L(i) = n(j) THEN EXIT FUNCTION

NEXT j, i

PRINT k; "∙ 3 ="; k * 3 'печать, если комбинация цифр - удачная

END FUNCTION

С перебором связаны и комбинаторные задачи.

Следует освоить алгоритмы создания лексикографического упорядочения и всевозможных перестановок из $n$ элементов.

Пример 6.4. В языке государства Икнатсо всего семь букв А, И, К, Н, О, С, Т. Составлен полный словарь семибуквенных слов (все буквы в словах различны), и первым словом в словаре является слово ИКНАТСО. По заданному слову вывести следующее за ним слово в лексикографическом (словарном) порядке.

Например, за словом СКОАТНИ следует слово СКОТИНА.

Программа (QBasic):

DIM A(1 TO 7)

First$ = "ИКНАТСО" ‘Первое слово в словаре

INPUT "Введите слово: ", s$

n = LEN(s$)

FOR i = 1 TO $N$ ‘Представляем исходное слово в виде

A(i) = INSTR(First$, MID$(s$, i, 1)) ‘массива из семи чисел

FOR i = $N$ - 1 TO 1 STEP –1 ‘Ищем первую с конца пару элементов,

IF A(i) < A(i + 1) THEN ‘упорядоченную по возрастанию

FOR j = $N$ TO i + 1 STEP –1 ‘Среди ранее рассмотренных элементов

IF A(j) > A(i) THEN ‘ищем наименьший, который больше A(i)

t = A(i): A(i) = A(j): A(j) = t ‘Ставим его на i ое место

FOR k = i + 1 TO $N$ – 1 ‘Оставшиеся элементы упорядочиваем

min = k ‘по возрастанию методом поиска

FOR l = k + 1 TO $N$ ‘последовательных минимумов

IF A(l) < A(min) THEN min = l

t = A(k): A(k) = A(min): A(min) = t

FOR i = 1 TO $N$ ‘Переводим массив чисел обратно в слово

PRINT MID$(First$, A(i), 1); ‘из алфавита Икнатсо

END ‘Печатаем ответ и завершаем программу

END IF

'Если же все пары соседних элементов были упорядочены по убыванию, то

PRINT "Это слово было в словаре последним"

Данную задачу на математический язык можно перефразировать так: по заданной перестановке из семи элементов требуется сгенерировать следующую за ней в лексикографическом порядке. Так как порядок букв в алфавите Икнатсо отличен от обычного, лучше оперировать не с буквами, а с числами от 1 до 7. Сопоставим буквам И, К, Н, А, Т, С, О их порядок в алфавите: букву «И» обозначим единицей, «К» - двойкой, и т. д., таким образом, исходное слово представим в виде массива из семи чисел. Далее вместо слова из алфавита Икнатсо будем говорить об этом массиве.

Проще всего получить следующую по порядку перестановку, когда последний (седьмой) элемент массива больше предпоследнего. В этом случае, чтобы получить ответ, достаточно поменять местами эти два последних элемента. В противном случае, надо рассмотреть два предпоследних элемента (пятый и шестой). Если пятый оказался меньше, на его место нужно поставить тот из двух последних, который должен следовать за ним (т.е. тот, который больше него, но, в то же время, меньше всех остальных). Так, например, в массиве (…, 3, 6, 5) нужно поменять местами тройку с пятеркой, а в массиве (…, 4, 6, 2) – четверку с шестеркой. После этого два последних элемента нужно записать в порядке возрастания (т.е. по алфавиту). Таким образом, после этой операции первый массив преобразуется в (…, 5, 3, 6), а второй – в (…, 6, 2, 4). Если же пятый элемент оказался больше шестого, потребуется рассмотреть предыдущую пару (четвертый с пятым). И так далее, до самого первого элемента.

Итак, весь алгоритм заключается в следующем:

1. Запишем исходное слово в виде массива чисел от 1 до 7. Назовем его A.

2. Будем последовательно рассматривать пары элементов A_i, A_i₊₁ (i = 6, 5, …, 1), пока не найдем такую пару, где A_i < A_i₊₁. Если такой пары не найдется, это означает, что весь массив отсортирован в порядке убывания, т.е. следующей перестановки не существует, а введенное слово является в словаре Икнатсо последним.

3. Пусть оказалось, что A_i < A_i₊₁. Среди элементов A_i₊₁, A_i_+2, …, $A^7$ найдем наибольшй A_j, такой что A_j > A_i. Поменяем элементы A_i и A_j местами.

4. Упорядочим элементы A_i₊₁, A_i_+2, …, $A^7$ по возрастанию.

5. Полученный массив преобразуем обратно в слово. Числу 1 сопоставим букву «И», числу 2 – «К», и т.д. Полученное слово – искомое.

Пример 6.5. Образовать все перестановки из $n$ элементов, каждая из которых содержит все эти элементы по одному разу, и которые отличаются друг от друга лишь порядком элементов.

Число таких перестановок будет $n$! (факториал). Сопоставим каждому элементу натуральное число от 1 до $n$ и запускаем перебор.

Программа (QBasic):

DIM SHARED $N$ '$N$ - количество элементов

INPUT "$N$ = ", $N$ 'num(k) - число на k-ой позиции

DIM SHARED num($N$), used($N$) 'used(i) - использовано ли число i (1-да, 0-нет)

CALL Permute(1) 'начинаем перестановки с первого элемента

SUB Permute (k%) 'перебирает все числа, которые можно поставить в ‘k-ую позицию

IF k% > n THEN 'если все n чисел уже расставлены,

FOR i = 1 TO n 'выводим результат очередной перестановки

PRINT num(i);

ELSE

FOR i = 1 TO n 'иначе просматриваем по порядку числа от 1 до n

IF used(i) = 0 THEN 'и, если очередное число i еще не использовано,

used(i) = 1 'помечаем его как использованное,

num(k%) = i 'ставим на k-ое место и

'продолжаем построение перестановки с k+1 позиции

CALL Permute(k% + 1)

used(i) = 0 'по возвращении, помечаем i как неиспользованное

END IF

END SUB

Идея данного алгоритма в том, что используется дополнительный массив (used), в котором хранится информация о том, какие целые числа из интервала 1..$n$ мы уже использовали при рекурсивном построении перестановки. Рекурсия состоит в том, что для построения цепочки длины k+1 из $n$ чисел сначала строим цепочку длины k.

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

2.3.2. Перебор с возвратом (backtracking)

Любая задача, к которой применим алгоритм перебора с возвратом (бектрекинг), может быть описана в общем случае следующим образом: требуется построить к данной задаче вектор решения ($a^1$, $a^2$, …, a_n), удовлетворяющий множеству условий и ограничений. Такой вектор строится покомпонентно слева направо. Предположим, что уже найдены значения первых k-1 компонент, а выбор следующей компоненты a_kзависит от некоторых ограничений и условий. Если условия и ограничения выполнимы, то выбираем a_kи переходим к рассмотрению компоненты a_k₊₁, затем a_k₊₂и так далее, если же оказалось невозможным выбрать компоненту a_k, то необходимо вернуться к предыдущему этапу, выбросить (k-1)-й элемент и выбрать другой a_k_-1, перейдя после этого снова к выбору k-й компоненты. Такой перебор может возвращать назад на несколько шагов, вплоть до выбора самой первой компоненты.

Решаемые бектрекингом задачи, как правило, принадлежат одному из трех классов – требуется найти либо произвольное из решений, либо перечислить все возможные решения, либо найти решение оптимальное по заданному критерию [2].

Одной из классических задач на бектрекинг является задача о рюкзаке.

Пример 6.6. «Рюкзак».

Имеется m различных предметов, известны веса предметов p₁, …, p_m и их стоимости - c₁, …, c_m. Определить, какие предметы надо положить в рюкзак, чтобы общий вес не превышал P, а общая стоимость была максимальна.

Предполагаем, что входные данные считываются из файла данных bag.dat по строкам:

m {количество предметов}

P {максимальный вес}

p_i, c_i {вес и стоимость i-го предмета, i = 1,…m}

Программа (QBasic):

DIM SHARED Items, BagSize, TotalCost, TotalWeight, MaxCost, MaxWeight

OPEN "bag.dat" FOR INPUT AS #1

INPUT #1, Items 'Количество предметов

INPUT #1, BagSize 'Вместимость рюкзака

DIM SHARED Weight(1 TO Items), Cost(1 TO Items) 'Вес и стоимость предметов

DIM SHARED Used(1 TO Items), MaxUsed(1 TO Items)

'Used(i)=1, если предмет i использован и 0 в противном случае

FOR i = 1 TO Items 'Считываем из файла характеристики предметов

INPUT #1, Weight(i), Cost(i)

CLOSE #1

MaxCost = 0: TotalCost = 0: TotalWeight = 0

CALL AddNew(0)

PRINT "Max weight:"; MaxWeight

PRINT "Max cost:"; MaxCost

PRINT "Items in the bag:";

FOR i = 1 TO Items

IF MaxUsed(i) = 1 THEN PRINT i;

SUB AddNew (Last) 'Добавление в рюкзак очередного предмета

'Last - номер последнего предмета, положенного в рюкзак

FOR i = Last+1 TO Items 'Пробуем добавить преметы с номерами больше Last

'Если предмет i еще не в рюкзаке и общий вес предметов не превысит вместимость

IF Used(i) = 0 AND TotalWeight + Weight(i) <= BagSize THEN

Used(i) = 1 'Тогда добавляем в рюкзак предмет i

'Высчитываем получившуюся стоимость и вес

TotalCost = TotalCost + Cost(i): TotalWeight = TotalWeight + Weight(i)

IF TotalCost > MaxCost THEN 'Если получившаяся стоимость больше ‘ранее найденной максимальной стоимости, то запоминаем новый набор ‘предметов

FOR j = 1 TO Items

MaxUsed(j) = Used(j)

'и обновляем значение максимальной стоимости

MaxCost = TotalCost: MaxWeight = TotalWeight

END IF

CALL AddNew(i) 'Рассматриваем рюкзак с новым предметом

'Затем убираем предмет i из рюкзака и переходим к новому i

TotalCost = TotalCost - Cost(i): TotalWeight = TotalWeight - Weight(i)

Used(i) = 0

END IF

END SUB

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

В данной задаче под «состоянием перебора» подразумевается множество собранных в рюкзак предметов (Used), их суммарная стоимость (TotalCost) и общий вес (TotalWeight). Алгоритм перебора представлен рекурсивной процедурой, в которую в качестве параметра (Last) передается порядковый номер последнего добавленного в рюкзак предмета (либо 0 в самом начале, пока рюкзак пустой). Процедура перебирает предметы с номерами, большими Last, и, если i-ый предмет может поместиться в рюкзак (т.е. его вес Weight(i) вместе с текущим весом рюкзака TotalWeight не превысит максимальную вместимость BagSize), то выполняет над ним следующие операции:

1. «помещает» i-ый предмет в рюкзак, т.е. помечает в массиве Used этот предмет как использованный;

2. пересчитывает общий вес и суммарную стоимость предметов рюкзака с учетом добавленного i-го предмета;

3. в случае, когда общая стоимость оказалась больше ранее найденной максимальной стоимости предметов, текущий вариант заполнения рюкзака запоминается как наилучший;

4. эта же процедура вызывается рекурсивно для рассмотрения оставшихся предметов с новым значением параметра Last, равным i;

5. по возвращении из рекурсивной процедуры i-ый предмет «вынимается» из рюкзака (помечается как неиспользованный), и снова пересчитывается общая стоимость и вес предметов (восстанавливаются прежние значения, не учитывающие i-ый предмет);

6. продолжается перебор вариантов с рассмотрения следующего, (i+1)-го предмета.

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

Пример 6.7. Обойти шахматную доску ходом коня, побывав в каждой клетке по одному разу.

Программа (QBasic):

DECLARE SUB pr (y, x)

CLEAR , , 20000 'Увеличим стандартный размер стека

DIM SHARED $N$, m, k

CLS

INPUT "$N$,m=", $N$, m 'Задать размер доски $N$´m клеток

DIM SHARED a(n, m)

CALL pr(1, 1) 'Начнем обход с клетки (1,1)

PRINT "no" 'В случае, когда обход всех клеток невозможен

SUB pr (y, x) 'Возможность хода конем в клетку (x,y)

IF x < 1 OR x > m OR y < 1 OR y > n THEN EXIT SUB 'Выход за пределы доски

IF k = $N$ * m THEN 'Удачный обход всех клеток, печать результата обхода

FOR i = 1 TO n

FOR j = 1 TO m

PRINT USING "####"; a(i, j); 'каждой клетке сопоставлен номер шага

NEXT j

NEXT i

END

END IF

IF a(y, x) = 0 THEN 'на данном поле еще не были

k = k + 1 'очередной номер шага

a(y, x) = k 'сопоставим пройденной клетке номер шага

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

'если не удачно, то в следующую по порядку

CALL pr(y + 2, x - 1)

CALL pr(y - 1, x + 2)

CALL pr(y + 1, x - 2)

CALL pr(y - 1, x - 2)

CALL pr(y + 1, x + 2)

CALL pr(y - 2, x + 1)

CALL pr(y + 2, x + 1)

CALL pr(y - 2, x - 1)

'Если все попытки шагнуть из клетки(x,y) в другие – неудачны, то

'освобождаем клетку и возвращаемся к предыдущему шагу

k = k - 1

a(y, x) = 0

END IF

END SUB

В задачах на бектрекинг обычно используются рекурсивные процедуры для формирования вариантов перебора, поэтому следует позаботиться об увеличении размера стека (с помощью оператора CLEAR), если возможен вариант достаточно длинный (по количеству вложенных вызовов рекурсивной процедуры).

Отметим, что по быстродействию программа перебора на Qbasic значительно уступает аналогичной программе, написанной на языке Pascal. В частности, в данной задаче уже для реальной шахматной доски (8´8) перебор занимает достаточно много времени, поэтому рекомендуется ограничивать бектрекинг. Можно и даже нужно применять симметрию, зеркальное отображение, выполняя задание для половины или меньшей части шахматной доски (переход коня на другую выделенную часть доски учитывается заданием начального поля).

Рис.

Разбивая доску (рис. ) на три части: (5´4), (5´4), (8´3), решаем задачу последовательно для каждой части доски с начальными положениями H₁(1,1), H₂(3,1), H₃(3,1), соответственно получим обход коня с конечными полями в К₁, К₂, К₃, а в целом – обход всей доски за приемлемое время расчета. Данный пример разбиения задачи на ряд подзадач (каждая для своей подобласти данных) следует рассматривать как один из принципов упрощения сложной задачи.

Освоены алгоритмы и приемы программирования огромного класса олимпиадных задач - задач перебора. Эти алгоритмы послужат нам в следующем разделе путеводной нитью, указывающей выход из лабиринта вариантов.

2.3.3. Лабиринты

Практически ни одна олимпиада областного и Российского уровня не обходится без использования какого-либо алгоритма на графах. Замечательно эта тема рассматривается в книге [5], в журнале [6]. Там вводятся понятие графа через вершины и ребра, понятие ориентированных или неориентированных графов, разбираются методы представления графов в виде матрицы смежности, матрицы инциденций, списка связей. Разбираются основные алгоритмы на графах:

· поиск в глубину (иными словами “бектрекинг” или перебор с возвратом);

· поиск в ширину (или метод заливки);

· Алгоритм Дейкстры для поиска кратчайших путей в графе из заданной вершины во все остальные;

· алгоритм Флойда для поиска кратчайших путей в графе между всеми парами вершин.

Ограничимся разбором задач, являющихся по своей сути, хотя и обширным, но все же частным случаем данного класса задач – задачами на лабиринты.

Для работы с лабиринтами нужны сами лабиринты. Приведем алгоритм генерации простейшего лабиринта.

На плоскости чертится прямоугольник, задающий границы лабиринта. Внутри прямоугольника выбирается точка (координаты которой задаются случайным образом), не лежащая на ранее построенных границах. От точки в случайном направлении (вправо, влево, вверх, вниз) рисуется линия границы до пересечения с какой-либо другой линией. Чтобы проходы в лабиринте были одинаковой ширины, координаты точки задаются с заранее выбранным шагом (например, на целочисленной сетке). Построение лабиринта прекращается по нажатию клавиши <ESC> или когда выбраны все допустимые точки. Такой алгоритм построения не дает циклических путей в лабиринте и, следовательно, в нем всегда можно найти выход. На рис. приведен вариант сгенерированного лабиринта, в котором необходимо отыскать путь, например, из левого верхнего поля – в правое нижнее.

Пример 7.1. Построить лабиринт, используя приведенный выше алгоритм.

Программа (QBasic):

SCREEN 12

RANDOMIZE TIMER

DIM SHARED x1, x2, y1, y2, h

DIM SHARED ix, iy

x1 = 100: y1 = 100

x2 = 500: y2 = 420

LINE (x1, y1)-(x2, y2), , B 'очертим границы лабиринта

h = 20 'шаг сетки

i = INT(RND * 20): j = INT(RND * 16)

'i и j - номера линий на плоскости, по которым строятся стены

' лабиринта, т.о. учитывается шаг

x = x1 + i * h

y = y1 + j * h

IF POINT(x, y) <> 15 THEN 'нашли случайную точку не на стене

PSET (x, y)

Рис.

napr = INT(RND * 4 + 1)

SELECT CASE napr

CASE 1

ix = 1: iy = 0

CASE 2

ix = 0: iy = 1

CASE 3

ix = -1: iy = 0

CASE 4

ix = 0: iy = -1

END SELECT

CALL r(x, y)

END IF

LOOP UNTIL INKEY$ = CHR$(27)

SUB r (x, y)

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

'оператор POINT(X,Y)определяет цвет точки, т.е. границу

x = x + ix * h

y = y + iy * h

IF POINT(x, y) <> 15 THEN LINE -(x, y) ELSE LINE -(x, y): EXIT DO

LOOP

END SUB

Преобразуйте алгоритм для построения лабиринта на квадратной сетке, где квадрат – есть часть стены (1) или коридора (0). Выведите матрицу лабиринта в файл, который можно использовать далее в задачах.

Пример 7.2. Лабиринт состоит из квадратных клеток и задается двумерным массивом A размерности 20 на 20, в котором если A[i, j]=0, то клетка [i, j] проходима. Если A[i, j]=1, то клетка [i, j] непроходима.

Начальное положение путника задается в проходимой клетке [k, m]. Путник может перемещаться из одной проходимой клетки в другую, если они имеют общую сторону. Путник выходит из лабиринта, когда попадает в граничную клетку, то есть клетку [i, j], где i и j равны 1 или 20. Выдать путь из лабиринта от выхода до начального положения путника либо фразу «Выхода нет».

Указание 1: Поиск пути в лабиринте осуществляется с помощью алгоритма, известного как перебор с возвратом (см. предыдущий раздел), но при решении задач на лабиринты (в общем случае, на графы) он носит название «поиска в глубину». Реализуется данный алгоритм чаще всего с помощью рекурсивной процедуры и организации данных в виде стека (LIFO – last in, first out – последним вошел, первым вышел).

Программа (QBasic):

'Поиск в глубину

DEFINT A-Z

TYPE TPoint

x AS INTEGER

y AS INTEGER

END TYPE

DIM SHARED a(1 TO 20, 1 TO 20), Stack(1 TO 400) AS TPoint

DIM SHARED p 'Указатель на вершину стека

'Чтение входного файла

OPEN "lab.dat" FOR INPUT AS #1

FOR i = 1 TO 20

FOR j = 1 TO 20

INPUT #1, a(i, j)

NEXT j

NEXT i

INPUT #1, k, m

CLOSE #1

CALL Search(k, m) 'Начинаем искать путь к выходу из текущей клетки

'Если выход не найден, выдаем соответствующий результат

PRINT "Выхода нет"

SUB Search (k, m)

a(k, m) = 1 'Помечаем текущую клетку как непроходимую

p = p + 1 '(т.к. здесь уже побывали)

Stack(p).x = k 'и сохраняем в стеке текущие координаты

Stack(p).y = m

IF k = 1 OR k = 20 OR m = 1 OR m = 20 THEN 'Если дошли до граничной клетки,

FOR i = p TO 1 STEP -1 'то печатаем результат с конца

PRINT "("; Stack(i).x; ","; Stack(i).y; ") "

END 'и завершаем программу

END IF

IF a(k + 1, m) = 0 THEN CALL Search(k + 1, m) 'Если соседние клетки свободны,

IF a(k - 1, m) = 0 THEN CALL Search(k - 1, m) 'пробуем продолжить поиск из них

IF a(k, m + 1) = 0 THEN CALL Search(k, m + 1)

IF a(k, m - 1) = 0 THEN CALL Search(k, m - 1)

p = p – 1 'Вынимаем из стека сохраненное текущее положение

END SUB

1) Данные по структуре лабиринта считываются из входного файла и заносятся в двумерный массив a размерности 20 на 20, где проходимые клетки принимают значение 0, а непроходимые – 1. Из файла также считываются координаты клетки, задающей начальное положение путника, - k и m.

2) Поиск пути в лабиринте начинается с исходной клетки с координатами [k, m]. Поиск осуществляется вызовом рекурсивной процедуры Search с параметрами - координатами данной клетки.

3) Если выход из лабиринта не найден, то управление из рекурсивной процедуры будет возвращено в головную программу, которая выведет соответствующее сообщение.

4) Работа рекурсивной процедуры заключается в следующем:

· Пометить текущую клетку как непроходимую, то есть в данной клетке путник уже побывал, а это означает присвоить соответствующему элементу массива единицу, a(k, m) = 1.

· Запомнить текущие координаты и номер клетки в пути. Номер текущей клетки в пути будет храниться в переменной p, координаты клетки будут храниться в стеке. Stack – это специальный массив, в котором будут последовательно запоминаться координаты клеток, входящих в путь (размерность данного массива равна максимальной длине пути 20х20 = 400).

· Проверить, не достигнут ли выход из лабиринта, то есть, не равны ли координаты текущей клетки (граничной клетки) 1 или 20, и при достижении выхода вывести весь путь (а именно, координаты клеток) с конечного (значение p) до начального положения (значение 1), после чего завершить программу.

· Если выход еще пока не достигнут, то проверить, свободны ли соседние клетки, и, если свободны, вызвать рекурсивную процедуру с параметрами-координатами этих клеток.

· Если произошел выход из рекурсивной процедуры, то есть оказалось, что в данном направлении нет пути, вернуться на шаг назад, уменьшив номер на единицу
p = p – 1.

5) Для того чтобы данная программа находила и печатала все возможные пути выхода из лабиринта, необходимо не завершать программу оператором END внутри процедуры Search, а ввести признак того, что какой-либо путь найден.

Указание 2: В тех случаях, когда необходимо найти кратчайший путь, используется другой алгоритм, называемый «поиском в ширину» или «волной на графе», или алгоритмом «заливки». Этот алгоритм может быть реализован как рекурсивно, так и без рекурсии. Но более быстрым, а значит и более предпочтительным, считается не рекурсивный алгоритм с использованием организации данных в виде очереди (FIFO – first in, first out – первым вошел, первым вышел).

Программа (QBasic):

'Поиск в ширину

DEFINT A-Z

TYPE TPoint

x AS INTEGER

y AS INTEGER

END TYPE

DIM SHARED a(0 TO 21, 0 TO 21), Queue(1 TO 400) AS TPoint

DIM SHARED p, q 'Указатели на начало и конец очереди

'Чтение входного файла

OPEN "lab.dat" FOR INPUT AS #1

FOR i = 1 TO 20

FOR j = 1 TO 20

INPUT #1, a(i, j)

NEXT j

NEXT i

INPUT #1, k, m

CLOSE #1

CALL Push(k, m, 2) 'Присваиваем начальной клетке ранг 2 и начинаем поиск с нее

WHILE p <> q

CALL Pop(k, m, r)

IF k = 1 OR k = 20 OR m = 1 OR m = 20 THEN 'Если дошли до граничной клетки,

FOR i = r - 1 TO 1 STEP –1 'то печатаем результат с конца

PRINT "("; k; ","; m; ") "

IF a(k, m - 1) = i THEN 'Для этого совершаем обратный проход,

m = m – 1 'т.е. ищем соседние клетки

ELSEIF a(k, m + 1) = i THEN 'с последовательно убывающими рангами

m = m + 1

ELSEIF a(k - 1, m) = i THEN

k = k - 1

ELSEIF a(k + 1, m) = i THEN

k = k + 1

END IF

END 'и завершаем программу

END IF

IF a(k + 1, m) = 0 THEN CALL Push(k + 1, m, r + 1) 'Если соседние клетки свободны,

IF a(k - 1, m) = 0 THEN CALL Push(k - 1, m, r + 1) 'заносим их в очередь

IF a(k, m + 1) = 0 THEN CALL Push(k, m + 1, r + 1) 'для дальнейшего просмотра

IF a(k, m - 1) = 0 THEN CALL Push(k, m - 1, r + 1) 'с рангом, увеличенным на 1

WEND

'Если выход не найден, выдаем соответствующий результат

PRINT "Выхода нет"

SUB Push (k, m, r)

a(k, m) = r 'Присваиваем клетке ранг r, т.е. это означает,

q = q + 1 'что до этой клетки можно добраться за r-1 ходов,

Queue(q).x = k 'и помещаем ее координаты в очередь

Queue(q).y = m

END SUB

SUB Pop (k, m, r)

p = p + 1 'Достаем координаты очередной рассматриваемой клетки из очереди

k = Queue(p).x

m = Queue(p).y

r = a(k, m) 'Вычисляем ее ранг

END SUB

2) Поиск пути в лабиринте начинается с исходной клетки с координатами [k, m] с помощью процедуры Push (поместить) с параметрами - координатами данной клетки и ее рангом – числом, обозначающим, за сколько шагов можно добраться до этой клетки.

3) Процедура Push в самом начале присваивает исходной клетке ее ранг a(k, m) = 2, увеличивает номер очереди на 1: q = q + 1, а затем помещает координаты текущей клетки в очередь – массив Queue (очередь) размерности 400: Queue(q).x = k и Queue(q).y = m.

4) В цикле, пока очередь не пуста, вызывается процедура Pop (извлечь) с такими же параметрами, что и процедура Push, которая достает из очереди координаты очередной рассматриваемой клетки и определяет ее ранг (первый раз он равен 2):

p = p + 1
k = Queue(p).x
m = Queue(p).y
r = a(k, m)

5) Далее в этом же цикле проводится проверка, свободны ли соседние клетки, чтобы передать управление процедуре Push уже для этих соседних клеток, чтобы поместить туда ранг 3 и т.д.

6) Это выполняется до тех пор, пока не будет достигнута граничная клетка, то есть пока не найдется выход, после чего остается распечатать весь путь, начиная с конца, и завершить программу.