7.3. Программирование с отходом назад

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

З адача о восьми ферзях. Найти все способы расстановки на шахматной доске восьми ферзей так, чтобы они не угрожали друг другу, т.е. чтобы на доске 88 никакие два ферзя не стояли на одной вертикали, горизонтали или диагонали. Очевидно, больше 8 ферзей на доске не расставить, так как все они должны стоять на разных горизонталях и вертикалях, а их всего по 8. Покажем, что 8 ферзей расставить можно, например, так как показано на рисунке справа. Однако значительно труднее определить общее число таких расстановок, в чем и состоит задача.

М ножество всех расстановок ферзей, среди которых требуется найти нужное подмножество, представим с помощью ориентированного дерева. На нем организуем поиск нужного варианта. Ориентированное дерево – это связный граф без циклов с выделенной вершиной (корнем), в котором между корнем и любой вершиной существует единственный путь. У дерева 9 уровней, номер уровня i определяет номер вертикали, на которую устанавливается i-ый ферзь. Восемь ветвей, выходящих из каждой вершины i–го уровня, соответствует восьми горизонтальным позициям ферзя, устанавливаемого на (i+1)–ой вертикали (см. рис.).

По условию задачи ферзи не должны бить друг друга, поэтому из рассмотрения исключаются вершины дерева, соответствующие уже занятым горизонталям и диагоналям. Тогда алгоритм перебора вариантов сводится к прохождению всех связных вершин дерева, начиная, например, с левой ветви, двигаясь вниз по нему до тех пор, пока не достигнута вершина последнего уровня. Если попытка установить (i+1)-го ферзя неудачна, то отходим назад на один уровень и проверяем, можем ли спуститься вниз по другой ветви. Если спуск возможен, то проводим его опять по самой левой из не пройденных ветвей (отход в бок), иначе отходим назад еще на один уровень и пытаемся спуститься по следующей из не пройденных ветвей и т.д., пока не переберем все 8 горизонтальных полей для (i+1)–й вертикали. Если вершина последнего уровня достигнута, то найден очередной вариант расстановки ферзей. Возвращаемся к корню и начинаем движение вниз по следующей из не пройденных ветвей и т.д. до тех пор, пока не останется не пройденных ветвей.

При такой организации перебора возможно не более 8⁸=2²⁴ вариантов, что примерно равно 10⁶. На самом деле их будет гораздо меньше в силу условия, что ферзи не бьют друг друга.

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

Д етализируем блок-схему задачи. Для этого возьмем доску размером nn и положим n=8. Будем ставить i-го ферзя на i–ую вертикаль. Для записи положения i–го ферзя заведем массив позиция[n] размерности n. Тогда в блоке прописка вариантов будет заноситься такое j, что i-ый ферзь, стоящий на пересечении i–й вертикали и j–ой горизонтали, не бьется ранее установленными (i-1) ферзями. Блок запись решения и его номера реализует печать номера расстановки и массива позиция[n], содержащего искомую расстановку. При движении назад надо установить номер последнего варианта предыдущего хода. Эта задача решается автоматически, так как последний вариант из позиция[n] будет занесен в j.

Д ля установки первого ферзя потребуется записать вертикаль и горизонталь, предшествующие 1-ой вертикали и горизонтали. Используем для этого фиктивную вертикаль i=0 и горизонталь j=0. При установке i–го ферзя необходима проверка, бьется ли поле i–го ферзя предыдущими, уже установленными ферзями. Для этого требуется проверить, стоят ли ферзи на одной горизонтали, на одной восходящей диагонали (слева снизу - направо вверх) и на одной заходящей диагонали (слева сверху – направо вниз). Для организации проверки вводим три логических массива: горизонт[n] – список горизонталей, восход[2n] – список восходящих диагоналей, заход[2n] – список заходящих диагоналей. Тогда полю (i,j), где 0  i  n, 0  j  n, соответствует вертикаль i, горизонталь j, восходящая диагональ n+j-i (n+j-i=const - уравнения линий с углом наклона 45), заходящая диагональ i+j (i+j=const – уравнения линий с углом наклона -45) (см. рис.). В блоке прописка варианта надо заносить в массивы горизонт, восход, заход отметку о том, что заняты горизонталь и две соответствующие диагонали того поля, куда установлен новый ферзь (горизонт[j]=true, восход[n+j-i]=true, заход[i+j]=true). В блоке выписка последнего варианта, наоборот – убрать отметки о занятости этого поля (горизонт[j]=false, восход[n+j-i]=false, заход[i+j]=false). Это легко осуществить, так как на одной горизонтали и диагонали может находиться только один ферзь.

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

Sub Ферзи()

Dim позиция() As Integer, горизонт() As Boolean, восход() As Boolean, заход() As Boolean

Dim i As Integer, j As Integer, k As Integer, m As Integer, var As String

Const n As Integer = 8, n2 As Integer = 16

ReDim позиция(1 To n), горизонт(1 To n), восход(1 To n2), заход(1 To n2)

i = 0: k = 0: For m = 1 To n: горизонт(m) = False: Next m

For m = 1 To n2: восход(m) = False: заход(m) = False: Next m

вперед: i =i +1: j = 0

If i > n Then GoTo резул

вбок: j = j + 1: If j > n Then GoTo назад

If (горизонт(j) = True) Or (восход(n + j - i) = True) Or (заход(j + i) = True) Then GoTo вбок

горизонт(j) = True: восход(n + j - i) = True: заход(j + i) = True: позиция(i) = j: GoTo вперед

резул: k = k + 1: var = "Ход " & Str(k) & ". Решение:"

For m = 1 To n: var = var & " " & Str(позиция (m)) & ",": Next m: MsgBox var

назад: i = i – 1: If I =0 Then GoTo конец

j = позиция(i): горизонт(j) = False: восход(n + j - i) = False: заход(j + i) = False: GoTo вбок

конец: MsgBox "Только " & Str(k) & " вариантов"

End Sub

7

Dim позиция() As Integer, горизонт() As Boolean, восход() As Boolean, заход() As Boolean

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

Задача о коммивояжере. Дано множество городов, пронумерованных от 0 до N. Варианты проезда задаются графом. Пути между парами городов характеризуются некоторой величиной, например, стоимостью или временем проезда, расходом горючего и т.д. Требуется проложить замкнутый путь – тур, который проходит через все города, двигаясь по которому каждый город проходится только раз, и при этом суммарная характеристика тура минимальна, например, минимальна стоимость проезда по всему туру.

Рассмотрим задачу на примере пяти городов с заданной матрицей стоимостей проезда.

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

Множество туров таково:

1. 123451 2. 123541 3. 124351

4. 124531 5. 125341 6. 125431

7. 132451 8. 132541 9. 134251

10. 134521 11. 135421 12. 135241

13. 142351 14. 142531 15. 143251

16. 143521 17. 145231 18. 145321

19. 152341 20. 152431 21. 153241

22. 153421 23. 154231 24. 154321

Для полносвязной сети-графа (каждый связан с каждым) количество всевозможных туров равно (N-1)! (для N=5 число туров 24). При больших N быстро растет и число туров и потребуется огромное количество вычислений, если использовать схему полного перебора всех вариантов. Поэтому важен алгоритм, позволяющий сократить число переборов. Но прежде рассмотрим способ организации полного перебора туров. Для этого воспользуемся алгоритмом с отходом назад из предыдущего параграфа. Рассматриваемый способ полного перебора позволяет произвести перебор вариантов и в случае неполносвязной сети, когда некоторые недиагональные элементы матрицы стоимостей равны бесконечности или отсутствует соответствующий переезд.

В исходной матрице (матрица X – см. дерево полного перебора) выбирается стоимость, не равная бесконечности, которая принимается за базу ветвления. База ищется по следующему правилу. В матрице стоимостей ищется строка i, имеющая не менее двух стоимостей < , и среди них за базу берется та стоимость C_ij, у которой наименьший индекс j. В нашем примере – это C₁₂. Затем производится ветвление, которое заключается в построении по исходной матрице двух новых матриц стоимостей. Суть ветвления заключается в разбиении исходной задачи на две подзадачи. В первой подзадаче, соответствующей первой матрице, фиксируется базовый переезд. Любой тур в этой подзадаче будет содержать фиксированный переезд (i,j), что означает переезд из города i только в город j и более ни в какой, а также переезд в город j только из города i. Это отражается в матрице приравниванием элементов строки и столбца, содержащих базу, бесконечности. Также посредством приравнивания бесконечности симметричного базе элемента запрещается обратный переезд из города j в город i, так как в противном случае не будет полного тура. Во второй подзадаче, соответствующей второй матрице, наоборот запрещается базовый переезд, что отражается приравниванием бесконечности базового элемента. Таким образом, ветвление от базы приводит к построению двух матриц, в каждой из которых затем вновь устанавливается база, и задача опять разбивается на две подзадачи.

Первая матрица (матрица A). Приравниваются бесконечности стоимости, находящиеся в строке и столбце базы C₁₂ (C₁₃=C₁₄=C₁₅=, C₃₂=C₄₂=C₅₂=), и симметричная базе стоимость C₂₁=. Значение базы не изменяется. Производится предотвращение циклов (описание ниже) и проверка полученной матрицы на наличие элемента, являющегося единственным не равным бесконечности элементом строки (столбца), и в то же время не являющегося таковым в столбце (строке). Если такого элемента нет, то матрица построена. В противном случае найденный элемент выбирается за базу и повторяется процедура ветвления от новой базы.

Вторая матрица (матрица B). Замена базового элемента на бесконечность (C₁₂=). Выбор нового базового элемента и повторение процедуры, аналогичной построению первой матрицы.

Предотвращение циклов. Для пояснения смысла этой операции рассмотрим процесс построения матрицы C из матрицы A. Базовым элементом является C₂₃. Тогда полагаем C₂₄=C₂₅=C₄₃=C₅₃=, остальные уже равны бесконечности. При этом фиксировано два переезда 12 и 23. Переезд из 3 в 2 запрещен (C₃₂=), но осталась еще одна возможность возникновения цикла переезд 31, при использовании которого получим цикл 1231, что противоречит условию задачи – тур должен быть полным. Поэтому следует положить C₃₁=. Формализуя процесс предотвращения циклов, получим. Пусть C_ij - база. Приравниваем ее бесконечности (C_ij=). Проверяем столбец i, если найден элемент C_ki такой, что является единственным, не равным бесконечности в строке, то полагаем C_kj=. Таким же образом обрабатываем столбец k и, если соответствующий элемент не найден, завершаем процесс предотвращения циклов. Иначе продолжаем проверку.

Матрицы, полученные в результате ветвления, на следующих шагах рассматриваются в качестве исходных, и с ними производятся описанные выше операции, что приводит к построению дерева (см. рис.), листьями которого являются матрицы, описывающие все 24 тура. Стоимости туров определяются суммой конечных элементов матрицы.

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

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

2. С умма констант приведения ( ) есть нижняя граница стоимости любого тура задачи. На ветвление процесс приведения практически не влияет за исключением выбора базовых элементов. В качестве кандидатов на роль базовых элементов рассматриваются элементы равные нулю (C₁₂, C₂₁, C₃₄, C₃₅, C₄₁, C₅₃, C₅₄). Среди них за базовый принимается элемент, имеющий максимальную сумму минимальных элементов по строке и столбцу, в которых он расположен. Так, для нашей приведенной матрицы имеем.

Для C₁₂: C₁₄=MinC_1j=4, j2; C₅₂=MinC_i2=6, i1. =10.

Для C₂₁: C₂₃=MinC_2j=8, j1; C₄₁=MinC_i1=0, i2. =8.

Для C₃₄: C₃₄=MinC_3j=0, j4; C₄₅=MinC_i4=1, i3. =0.

Для C₃₅: C₃₅=MinC_3j=0, j5; C₅₄=MinC_i5=0, i3. =1.

Для C₄₁: C₄₅=MinC_4j=1, j1; C₂₁=MinC_i1=0, i3. =1.

Для C₅₃: C₅₄=MinC_5j=0, j3; C₂₃=MinC_i3=8, i3. =8.

Для C₅₄: C₅₃=MinC_5j=0, j4; C₃₄=MinC_i4=0, i3. =0.

Максимальная сумма соответствует элементу C₁₂, он и принимается как базовый. Далее производится ветвление (см. рис. "Ветвление").

Строится первая матрица ветвления, производится ее приведение, и сумма констант приведения суммируется к уже имеющейся нижней границе, равной 48, что дает 56 как нижнюю границу стоимости любого тура в данной подзадаче. Этот процесс продолжается до получения первого тура и его стоимости, после чего производится возврат на шаг вверх по дереву и исследование ветвей, порождаемых движением вниз, т.е. ветвей порождаемых вторыми матрицами процесса ветвления (на данном рисунке в отличие от предыдущего первые матрицы ветвления изображаются справа от порождающей матрицы). Ветвь не имеет смысла исследовать, если нижняя граница для туров в данной подзадаче превышает стоимость наилучшего пути, найденного в данный момент. Как видно из рисунка, все ветви в дереве, идущие вниз, имеют нижние границы, превышающие стоимость тура 123541, равную 56. Следовательно, это и есть искомый тур задачи. Рассмотренный пример показывает, как много вариантов в ряде случаев удается исключить из рассмотрения.

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